The multiplicative coalescent is a Markov process taking values in ordered @math . It is a mean-field process in which any pair of blocks coalesces at rate proportional to the product of their masses. In Aldous and Limic (1998) each extreme eternal version @math of the multiplicative coalescent was described in three different ways. One of these specifications matches the (marginal) law of @math to that of the ordered excursion lengths above past minima of @math , where @math is a certain Levy-type process which (modulo shift and scaling) has infinitesimal drift @math at time @math . Using a modification of the breadth-first-walk construction from Aldous (1997) and Aldous and Limic (1998), and some new insight from the thesis by Uribe (2007), this work settles an open problem (3) from Aldous (1997), in the more general context of Aldous and Limic (1998). Informally speaking, @math is entirely encoded by @math , and contrary to Aldous' original intuition, the evolution of time for @math does correspond to the linear increase in the constant part of the drift of @math . In the "standard multiplicative coalescent" context of Aldous (1997), this result was first announced by Armendariz in 2001, and obtained in a recent preprint by Broutin and Marckert, who simultaneously account for the process of excess edge counts (or marks). The novel argument presented here is based on a sequence of relatively elementary observations. Some of its components (for example, the new dynamic random graph construction via "simultaneous" breadth-first walks) are of independent interest, and may be useful for obtaining more sophisticated asymptotic results on near critical random graphs and related processes.
The present approach to Theorem is of independent interest even in the standard setting (where Section would simplify further, since @math , and already Lemma 8 from @cite_14 would be sufficient for making conclusions in Section ). In addition, it may prove useful for continued analysis of the s, as well as various other processes in the domain of attraction''.
@cite_14
2056513564
Let (B t (s), 0 ≤ s < ∞) be reflecting inhomogeneous Brownian motion with drift t - s at time s, started with B t (0) = 0. Consider the random graph script G sign(n, n -1 + tn -4 3 ), whose largest components have size of order n 2 3 . Normalizing by n -2 3 , the asymptotic joint distribution of component sizes is the same as the joint distribution of excursion lengths of B t (Corollary 2). The dynamics of merging of components as t increases are abstracted to define the multiplicative coalescent process. The states of this process are vectors x of nonnegative real cluster sizes (x i ), and clusters with sizes x i and x j merge at rate x i x j . The multiplicative coalescent is shown to be a Feller process on l 2 . The random graph limit specifies the standard multiplicative coalescent, which starts from infinitesimally small clusters at time -∞; the existence of such a process is not obvious.