We prove local convergence results for rerooted conditioned multi-type Galton–Watson trees. The limit objects are multitype variants of the random sin-tree constructed by Aldous (1991), and differ ...according to which types recur infinitely often along the backwards growing spine.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Stephenson (2018) established annealed local convergence of Boltzmann planar maps conditioned to be large. The present work uses results on rerooted multi-type branching trees to prove a quenched ...version of this limit.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
We study the uniform random graph Cn with n vertices drawn from a subcriticai class of connected graphs. Our main result is that the rescaled graph On ${C_n}/\sqrt n $ converges to the Brownian ...continuum random tree Te multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide sub-Gaussian tail bounds for the diameter D(Cn) and height $H\left( {C_n^*} \right)$ of the rooted random graph ${C_n^*}$. We give analytic expressions for the scaling factor in several cases, including for example the class of outerplanar graphs. Our methods also enable us to study first passage percolation on Cn, where we also show the convergence to Te under an appropriate rescaling.
Full text
Available for:
BFBNIB, INZLJ, NMLJ, NUK, PNG, SAZU, UL, UM, UPUK, ZRSKP
The mathematical analysis of random phylogenetic networks via analytic and algorithmic methods has received increasing attention in the past years. In the present work we introduce branching process ...methods to their study. This approach appears to be new in this context. Our main results focus on random level‐k networks with n labeled leaves. Although the number of reticulation vertices in such networks is typically linear in n, we prove that their asymptotic global and local shape is tree‐like in a well‐defined sense. We show that the depth process of vertices in a large network converges towards a Brownian excursion after rescaling by n−1/2. We also establish Benjamini–Schramm convergence of large random level‐k networks towards a novel random infinite network.
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
The uniform infinite cubic planar graph Stufler, Benedikt
Bernoulli : official journal of the Bernoulli Society for Mathematical Statistics and Probability,
11/2023, Volume:
29, Issue:
4
Journal Article
Graphon convergence of random cographs Stufler, Benedikt
Random structures & algorithms,
October 2021, 2021-10-00, 20211001, Volume:
59, Issue:
3
Journal Article
Peer reviewed
Open access
We study the behavior of random labeled and unlabeled cographs with n vertices as n tends to infinity. We show that both models admit a novel random graphon W1/2 as distributional limit. Our main ...tool is an enhanced skeleton decomposition of the random Pólya An tree with n leaves and no internal vertices having only one child. As a byproduct, we obtain limits describing the asymptotic shape of this model of random trees.
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
Gibbs partitions: The convergent case Stufler, Benedikt
Random structures & algorithms,
October 2018, 2018-10-00, 20181001, Volume:
53, Issue:
3
Journal Article
Peer reviewed
Open access
We study Gibbs partitions that typically form a unique giant component. The remainder is shown to converge in total variation toward a Boltzmann‐distributed limit structure. We demonstrate how this ...setting encompasses arbitrary weighted assemblies of tree‐like combinatorial structures. As an application, we establish smooth growth along lattices for small block‐stable classes of graphs. Random graphs with n vertices from such classes are shown to form a giant connected component. The small fragments may converge toward different Poisson Boltzmann limit graphs, depending along which lattice we let n tend to infinity. Since proper addable minor‐closed classes of graphs belong to the more general family of small block‐stable classes, this recovers and generalizes results by McDiarmid (2009).
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK