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.     

The longest path in a random graph

A random graph with (1+ε)n/2 edges contains a path of lengthcn. A random directed graph with (1+ε)n edges contains a directed path of lengthcn. This settles a conjecture of Erdõs.     

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).     

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).     

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.     

Hammersley's interacting particle process and longest increasing subsequences

Summary In a famous paper [8] Hammersley investigated the lengthL _n of the longest increasing subsequence of a randomn-permutation. Implicit in that paper is a certain one-dimensional continuous-space interacting particle process. By studying a hydrodynamical limit for Hammersley's process we show by fairly “soft” arguments that limn ^′1/2 EL _n =2. This is a known result, but previous proofs [14, 11] relied on hard analysis of combinatorial asymptotics. Research supported by NSF Grant MCS 92-24857 and the Miller Institute for Basic Research in Science Research supported by NSF Grant DMS92-04864     

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.     

The random-cluster model on a homogeneous tree

Summary The random-cluster model on a homogeneous tree is defined and studied. It is shown that for 1q2, the percolation probability in the maximal random-cluster measure is continuous inp, while forq>2 it has a discontinuity at the critical valuep=p _c (q). It is also shown that forq>2, there is nonuniqueness of random-cluster measures for an entire interval of values ofp. The latter result is in sharp contrast to what happens on the integer lattice Z ^d .Research partially supported by a grant from the Royal Swedish Academy of Sciences     

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.     

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.     

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$.     

Fundamental solutions, transition densities and the integration of Lie symmetries

In this paper we present some new applications of Lie symmetry analysis to problems in stochastic calculus. The major focus is on using Lie symmetries of parabolic PDEs to obtain fundamental solutions and transition densities. The method we use relies upon the fact that Lie symmetries can be integrated with respect to the group parameter. We obtain new results which show that for PDEs with nontrivial Lie symmetry algebras, the Lie symmetries naturally yield Fourier and Laplace transforms of fundamental solutions, and we derive explicit formulas for such transforms in terms of the coefficients of the PDE.     

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.     

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^∗.     

Rescaled Lévy-Loewner hulls and random growth

We consider radial Loewner evolution driven by unimodular Lévy processes. We rescale the hulls of the evolution by capacity, and prove that the weak limit of the rescaled hulls exists. We then study a random growth model obtained by driving the Loewner equation with a compound Poisson process. The process involves two real parameters: the intensity of the underlying Poisson process and a localization parameter of the Poisson kernel which determines the jumps. A particular choice of parameters yields a growth process similar to the Hastings-Levitov HL(0) model. We describe the asymptotic behavior of the hulls with respect to the parameters, showing that growth tends to become localized as the jump parameter increases. We obtain deterministic evolutions in one limiting case, and Loewner evolution driven by a unimodular Cauchy process in another. We show that the Hausdorff dimension of the limiting rescaled hulls is equal to 1. Using a different type of compound Poisson process, where the Poisson kernel is replaced by the heat kernel, as driving function, we recover one case of the aforementioned model and SLE(κ) as limits.     

Stationary states of random Hamiltonian systems

Summary We investigate the ergodic properties of Hamiltonian systems subjected to local random, energy conserving perturbations. We prove for some cases, e.g. anharmonic crystals with random nearest neighbor exchanges (or independent random reflections) of velocities, that all translation invariant stationary states with finite entropy per unit volume are microcanonical Gibbs states. The results can be utilized in proving hydrodynamic behavior of such systems.Hill Center for Mathematical Sciences, Rutgers University, New Brunswick, NJ 08903, USAJF was supported in parts by Japan Society for Promotion of Science (JSPS) and by NSF Grant DMR89-18903