32 citations · 57 across the 7 of their papers we have counts for
15 papers · 1 filter
Dynamical Models for Random Simplicial Complexes
Nikolaos Fountoulakis, Tejas Iyer, Cécile Mailler +1
We study a general model of random dynamical simplicial complexes and derive a formula for the asymptotic degree distribution. This asymptotic formula encompasses results for a num…
A limit field for orthogonal range searches in two-dimensional random point search trees
Nicolas Broutin, Henning Sulzbach
We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the…
On weighted depths in random binary search trees
Rafik Aguech, Anis Amri, Henning Sulzbach
Following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133-141], the weighted depth of a node in a labelled rooted tree is the sum of a…
The heavy path approach to Galton-Watson trees with an application to Apollonian networks
Luc Devroye, Cecilia Holmgren, Henning Sulzbach
We study the heavy path decomposition of conditional Galton-Watson trees. In a standard Galton-Watson tree conditional on its size , we order all children by their subtree sizes…
Self-similar real trees defined as fixed-points and their geometric properties
Nicolas Broutin, Henning Sulzbach
We consider fixed-point equations for probability measures charging measured compact metric spaces that naturally yield continuum random trees. On the one hand, we study the existe…
Mode and Edgeworth expansion for the Ewens distribution and the Stirling numbers
Zakhar Kabluchko, Alexander Marynych, Henning Sulzbach
We provide asymptotic expansions for the Stirling numbers of the first kind and, more generally, the Ewens (or Karamata-Stirling) distribution. Based on these expansions, we obtain…
General Edgeworth expansions with applications to profiles of random trees
Zakhar Kabluchko, Alexander Marynych, Henning Sulzbach
We prove an asymptotic Edgeworth expansion for the profiles of certain random trees including binary search trees, random recursive trees and plane-oriented random trees, as the si…
Process convergence for the complexity of Radix Selection on Markov sources
Kevin Leckey, Ralph Neininger, Henning Sulzbach
A fundamental algorithm for selecting ranks from a finite subset of an ordered set is Radix Selection. This algorithm requires the data to be given as strings of symbols over an or…
On martingale tail sums in affine two-color urn models with multiple drawings
Markus Kuba, Henning Sulzbach
In two recent works, Kuba and Mahmoud (arXiv:1503.090691 and arXiv:1509.09053) introduced the family of two-color affine balanced Polya urn schemes with multiple drawings. We show…
On martingale tail sums for the path length in random trees
Henning Sulzbach
For a martingale converging almost surely to a random variable , the sequence is called martingale tail sum. Recently, Neininger [Random Structures Algorithm…
Analysis of radix selection on Markov sources
Kevin Leckey, Ralph Neininger, Henning Sulzbach
The complexity of the algorithm Radix Selection is considered for independent data generated from a Markov source. The complexity is measured by the number of bucket operations req…
The dual tree of a recursive triangulation of the disk
Nicolas Broutin, Henning Sulzbach
In the recursive lamination of the disk, one tries to add chords one after another at random; a chord is kept and inserted if it does not intersect any of the previously inserted o…
On a functional contraction method
Ralph Neininger, Henning Sulzbach
Methods for proving functional limit laws are developed for sequences of stochastic processes which allow a recursive distributional decomposition either in time or space. Our appr…
A limit process for partial match queries in random quadtrees and -d trees
Nicolas Broutin, Ralph Neininger, Henning Sulzbach
We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quadtrees and -d trees). We assume the traditional model where the…
Partial match queries in random quadtrees
Nicolas Broutin, Ralph Neininger, Henning Sulzbach
We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the traditional model where the d…