The CRT is the scaling limit of random dissections

Abstract–We study the graph structure of large random dissections of polygons sampled according to Boltzmann weights, which encompasses the case of uniform dissections or uniform p‐angulations. As their number of vertices n goes to infinity, we show that these random graphs, rescaled by , converge in the Gromov–Hausdorff sense towards a multiple of Aldous' Brownian tree when the weights decrease sufficiently fast. The scaling constant depends on the Boltzmann weights in a rather amusing and intriguing way, and is computed by making use of a Markov chain which compares the length of geodesics in dissections with the length of geodesics in their dual trees. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 304–327, 2015     

On the structure of random plane-oriented recursive trees and their branches

This paper is an investigation of the structural properties of random plane-oriented recursive trees and their branches. We begin by an enumeration of these trees and some general properties related to the outdegrees of nodes. Using generalized Pólya urn models we study the exact and limiting distributions of the size and the number of leaves in the branches of the tree. The exact distribution for the leaves in the branches is given by formulas involving second-order Eulerian numbers. A martingale central limit theorem for a linear combination of the number of leaves and the number of internal nodes is derived. The distribution of that linear combination is a mixture of normals with a beta distribution as its mixing density. The martingale central limit theorem allows easy determination of the limit laws governing the leaves in the branches. Furthermore, the asymptotic joint distribution of the number of nodes of outdegree 0, 1 and 2 is shown to be trivariate normal. © 1993 John Wiley & Sons, Inc.     

The continuum random tree is the scaling limit of unlabeled unrooted trees

We show that the uniform unlabeled unrooted tree with n vertices and vertex degrees in a fixed set converges in the Gromov‐Hausdorff sense after a suitable rescaling to the Brownian continuum random tree. This confirms a conjecture by Aldous (1991). We also establish Benjamini‐Schramm convergence of this model of random trees and provide a general approximation result, that allows for a transfer of a wide range of asymptotic properties of extremal and additive graph parameters from Pólya trees to unrooted trees.     

The cut‐tree of large trees with small heights

We destroy a finite tree of size n by cutting its edges one after the other and in uniform random order. Informally, the associated cut‐tree describes the genealogy of the connected components created by this destruction process. We provide a general criterion for the convergence of the rescaled cut‐tree in the Gromov‐Prohorov topology to an interval endowed with the Euclidean distance and a certain probability measure, when the underlying tree has branching points close to the root and height of order . In particular, we consider uniform random recursive trees, binary search trees, scale‐free random trees and a mixture of regular trees. This yields extensions of a result in Bertoin (Probab Stat 5 (2015), 478–488) for the cut‐tree of uniform random recursive trees and also allows us to generalize some results of Kuba and Panholzer (Online J Anal Combin (2014), 26) on the multiple isolation of vertices. The approach relies in the close relationship between the destruction process and Bernoulli bond percolation, which may be useful for studying the cut‐tree of other classes of trees. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 404–427, 2017     

Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees

We study the joint probability distribution of the number of nodes of outdegree 0, 1, and 2 in a random recursive tree. We complete the known partial list of exact means and variances for outdegrees up to two by obtaining exact combinatorial expressions for the remaining means, variances, and covariances. The joint probability distribution of the number of nodes of outdegree 0, 1, and 2 is shown to be asymptotically trivariate normal and the asymptotic covariance structure is explicitly determined. It is also shown how to extend the results (at least in principle) to obtain a limiting multivariate normal distribution for nodes of outdegree 0, 1, …, k.     

On the allocation of binary trees to secondary storage

Two paging techniques proposed by Muntz and Uzgalis to store a binary tree in secondary storage are considered. The first method (sequential allocation) is the basic allocation technique and here an exact formula is given, to be considered as a touchstone for every other method. Then a modification to the second method (grouped allocation) is proposed which gains control on storage utilization. This allows the structure to maintain both a high loading factor and a low retrieving time.     

On asymmetry of the future and the past for limit self-joinings

Let be an off-diagonal joining of a transformation . We construct a non-typical transformation having asymmetry between limit sets of for positive and negative powers of . It follows from a correspondence between subpolymorphisms and positive operators, and from the structure of limit polynomial operators. We apply this technique to find all polynomial operators of degree in the weak closure (in the space of positive operators on ) of powers of Chacon's automorphism and its generalizations.

     

On the covariance of the level sizes in random recursive trees

In this paper we study the covariance structure of the number of nodes k and l steps away from the root in random recursive trees. We give an analytic expression valid for all k, l and tree sizes N. The fraction of nodes k steps away from the root is a random probability distribution in k. The expression for the covariances allows us to show that the total variation distance between this (random) probability distribution and its mean converges in probability to zero. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 519–539, 2002     

The Brownian map is the scaling limit of uniform random plane quadrangulations

We prove that uniform random quadrangulations of the sphere with n faces, endowed with the usual graph distance and renormalized by n ^?1/4, converge as n → ∞ in distribution for the Gromov–Hausdorff topology to a limiting metric space. We validate a conjecture by Le Gall, by showing that the limit is (up to a scale constant) the so-called Brownian map, which was introduced by Marckert–Mokkadem and Le Gall as the most natural candidate for the scaling limit of many models of random plane maps. The proof relies strongly on the concept of geodesic stars in the map, which are configurations made of several geodesics that only share a common endpoint and do not meet elsewhere.     

Projections of the Aldous chain on binary trees: Intertwining and consistency

Consider the Aldous Markov chain on the space of rooted binary trees with n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k<n and project the leaf mass onto the subtree spanned by the first k leaves. This yields a binary tree with edge weights that we call a “decorated k‐tree with total mass n.” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated k‐trees evolve as Markov chains themselves, and are projectively consistent over k. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the n→∞ continuum analog of the Aldous chain and will be taken up elsewhere.     

The limit theorems for maxima of stationary Gaussian processes with random Index

Let {X(t), t ≥ 0} be a standard(zero-mean, unit-variance) stationary Gaussian process with correlation function r(·) and continuous sample paths. In this paper, we consider the maxima M(T) = max{X(t), t∈ [0, T ]} with random index TT, where TT /T converges to a non-degenerate distribution or to a positive random variable in probability, and show that the limit distribution of M(TT) exists under some additional conditions related to the correlation function r(·).     

Geometry of the vacant set left by random walk on random graphs,Wright's constants,and critical random graphs with prescribed degrees

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by ?erný and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs.     

A two-dimensional limit theorem for Mellin transforms of the Riemann zeta-function

In this paper, we obtain a two-dimensional limit theorem in the sense of weak convergence of probability measures on the complex plane for Mellin transforms of the square and the fourth power of the Riemann zeta-function. Partially supported by the Lithuanian Foundation of Studies and Science.     

Joint discrete limit theorems in the space of analytic functions for general Dirichlet series

We prove joint discrete limit theorems in the sense of weak convergence of probability measures in the space of analytic functions for general Dirichlet series.__________Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 1, pp. 104–116, January–March, 2005.Translated by R. Macaitien     

The Lusin area function and local admissible convergence of harmonic functions on homogeneous trees

We prove admissible convergence to the boundary of functions that are harmonic on a subset of a homogeneous tree by means of a discrete Green formula and an analogue of the Lusin area function.

     

Almost strict total positivity and a class of Hurwitz polynomials

We establish sufficient conditions for a matrix to be almost totally positive, thus extending a result of Craven and Csordas who proved that the corresponding conditions guarantee that a matrix is strictly totally positive. Then we apply our main result in order to obtain a new criteria for a real algebraic polynomial to be a Hurwitz one. The properties of the corresponding “extremal” Hurwitz polynomials are discussed.     

The scaling limit for a stochastic PDE and the separation of phases

Summary We investigate the problem of singular perturbation for a reaction-diffusion equation with additive noise (or a stochastic partial differential equation of Ginzburg-Landau type) under the situation that the reaction term is determined by a potential with double-wells of equal depth. As the parameter (the temperature of the system) tends to 0, the solution converges to one of the two stable phases and consequently the phase separation is formed in the limit. We derive a stochastic differential equation which describes the random movement of the phase separation point. The proof consists of two main steps. We show that the solution stays near a manifoldM of minimal energy configurations based on a Lyapunov type argument. Then, the limit equation is identified by introducing a nice coordinate system in a neighborhood ofM .Research partially supported by Japan Society for the Promotion of Science     

The mean value of the squared path-difference distance for rooted phylogenetic trees

The path-difference metric is one of the oldest distances for the comparison of fully resolved phylogenetic trees, but its statistical properties are still quite unknown. In this paper we compute the mean value of the square of the path-difference metric between two fully resolved rooted phylogenetic trees with n leaves, under the uniform distribution. This complements previous work by Steel and Penny, who computed this mean value for fully resolved unrooted phylogenetic trees.