On a random graph evolving by degrees

We consider a random (multi)graph growth process {Gm} on a vertex set [n], which is a special case of a more general process proposed by Laci Lovász in 2002. G₀ is empty, and Gm+1 is obtained from Gm by inserting a new edge e at random. Specifically, the conditional probability that e joins two currently disjoint vertices, i and j, is proportional to (di+α)(dj+α), where di, dj are the degrees of i, j in Gm, and α>0 is a fixed parameter. The limiting case α=∞ is the Erd?s-Rényi graph process. We show that whp Gm contains a unique giant component iff c:=2m/n>cα=α/(1+α), and the size of this giant is asymptotic to , where c^∗<cα is the root of . A phase transition window is proved to be contained, essentially, in [cα−An−1/3,cα+Bn−1/4], and we conjecture that 1/4 may be replaced with 1/3. For the multigraph version, {MGm}, we show that MGm is connected whp iff m?mn:=n1+α−1. We conjecture that, for α>1, mn is the threshold for connectedness of Gm itself.     

Sandwiching random graphs: universality between random graph models

The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n,p) and the random regular graph G_d(n). This connection appears to be very useful in deriving properties of one model from the other and explains why many graph invariants are universal. In particular, one obtains one-line proofs of several highly non-trivial and recent results on G_d(n).     

The Markov chain asymptotics of random mapping graphs

In this paper the limit behavior of random mappings with n vertices is investigated. We first compute the asymptotic probability that a fixed class of finite non-intersected subsets of vertices are located in different components and use this result to construct a scheme of allocating particles with a related Markov chain. We then prove that the limit behavior of random mappings is actually embedded in such a scheme in a certain way. As an application, we shall give the asymptotic moments of the size of the largest component.     

Itô’s excursion theory and random trees

We explain how Itô’s excursion theory can be used to understand the asymptotic behavior of large random trees. We provide precise statements showing that the rescaled contour of a large Galton–Watson tree is asymptotically distributed according to Itô’s excursion measure. As an application, we provide a simple derivation of Aldous’ theorem stating that the rescaled contour function of a Galton–Watson tree conditioned to have a fixed large progeny converges to a normalized Brownian excursion. We also establish a similar result for a Galton–Watson tree conditioned to have a fixed large height.     

Central limit theorems for a supercritical branching process in a random environment

For a supercritical branching process (Z_n) in a stationary and ergodic environment ξ, we study the rate of convergence of the normalized population W_n=Z_n/E[Z_n|ξ] to its limit W_∞: we show a central limit theorem for W_∞−W_n with suitable normalization and derive a Berry-Esseen bound for the rate of convergence in the central limit theorem when the environment is independent and identically distributed. Similar results are also shown for W_n+k−W_n for each fixed k∈N^∗.     

Clique coverings of the edges of a random graph

The edges of the random graph (with the edge probabilityp=1/2) can be covered usingO(n ²lnlnn/(lnn)²) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1–)n ²/(2lgn)².Research supported in part by ONR Grant N00014-85K0570 and by NSA/MSP Grant MDA904-90-H-4011.     

Hitting time fork edge-disjoint spanning trees in a random graph

We show that in almost every random graph process, the hitting time for havingk edge-disjoint spanning trees equals the hitting time for having minimum degreek.     

The forest associated with the record process on a Lévy tree

We perform a pruning procedure on a Lévy tree and instead of throwing away the removed sub-tree, we regraft it on a given branch (not related to the Lévy tree). We prove that the tree constructed by regrafting is distributed as the original Lévy tree, generalizing a result of Addario-Berry, Broutin and Holmgren where only Aldous’s tree is considered. As a consequence, we obtain that the “average pruning time” of a leaf is distributed as the height of a leaf picked at random in the Lévy tree.     

How many random edges make a graph hamiltonian?

A threshold for a graph propertyQ in the scale of random graph spacesG _n,p is ap-band across which the asymptotic probability ofQ jumps from 0 to 1. We locate a sharp threshold for the property of having a hamiltonian path.     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

The uniform random tree in a Brownian excursion

Summary To any Brownian excursione with duration (e) and anyt ₁, ...,t _p [0,(e)], we associate a branching tree withp branches denoted byT _p (e, t ₁,...,t _p ), which is closely related to the structure of the minima ofe. Our main theorem states that, ife is chosen according to the Itô measure and (t ₁, ...,t _p ) according to Lebesgue measure on [0,(e)] ^p , the treeT _p (e, t ₁, ...,t _p ) is distributed according to the uniform measure on the set of trees withp branches. The proof of this result yields additional information about the subexcursions ofe corresponding to the different branches of the tree, thus generalizing a well-known representation theorem of Bismut. If we replace the Itô measure by the law of the normalized excursion, a simple conditioning argument leads to another remarkable result originally proved by Aldous with a very different method.     

Estimation of the offspring mean in a controlled branching process with a random control function

Controlled branching processes (CBP) with a random control function provide a useful way to model generation sizes in population dynamics studies, where control on the growth of the population size is necessary at each generation. An important special case of this process is the well known branching process with immigration. Motivated by the work of Wei and Winnicki [C.Z. Wei, J. Winnicki, Estimation of the mean in the branching process with immigration, Ann. Statist. 18 (1990) 1757–1773], we develop a weighted conditional least squares estimator of the offspring mean of the CBP and derive the asymptotic limit distribution of the estimator when the process is subcritical, critical and supercritical. Moreover, we show the strong consistency of this estimator in all the cases. The results obtained here extend those of Wei and Winnicki [C.Z. Wei, J. Winnicki, Estimation of the mean in the branching process with immigration, Ann. Statist. 18 (1990) 1757–1773] for branching processes with immigration and provide a unified limit theory of estimation.     

Asymptotic theory for the multidimensional random on-line nearest-neighbour graph

The on-line nearest-neighbour graph on a sequence of n$n$ uniform random points in (0,1)^d${(0,1)}^d$ (d∈N$d\in \mathbb{N}$) joins each point after the first to its nearest neighbour amongst its predecessors. For the total power-weighted edge-length of this graph, with weight exponent α∈(0,d/2]$\alpha \in (0,d/2]$, we prove O(max{n^1−(2α/d),logn})$O(max\{n^{1-(2\alpha /d)},logn\})$ upper bounds on the variance. On the other hand, we give an n→∞$n\to \infty$ large-sample convergence result for the total power-weighted edge-length when α>d/2$\alpha >d/2$. We prove corresponding results when the underlying point set is a Poisson process of intensity n$n$.     

Shift-coupling and a zero-one law for random walk in random environment

This paper discusses several aspects of shift-coupling for random walk in random environment.     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

The random-cluster model on the complete graph

Summary The random-cluster model of Fortuin and Kasteleyn contains as special cases the percolation, Ising, and Potts models of statistical physics. When the underlying graph is the complete graph onn vertices, then the associated processes are called mean-field. In this study of the mean-field random-cluster model with parametersp=/n andq, we show that its properties for any value ofq(0, ) may be derived from those of an Erds-Rényi random graph. In this way we calculate the critical point _c (q) of the model, and show that the associated phase transition is continuous if and only ifq2. Exact formulae are given for _C (q), the density of the largest component, the density of edges of the model, and the free energy. This work generalizes earlier results valid for the Potts model, whereq is an integer satisfyingq2. Equivalent results are obtained for a fixed edge-number random-cluster model. As a consequence of the results of this paper, one obtains large-deviation theorems for the number of components in the classical random-graph models (whereq=1).     

On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001