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.
Aldous and Pitman have studied the asymptotic behavior of the additive coalescent processes using a nested family random forests derived by logging certain inhomogeneous continuum random trees. Here we propose a different approach based on partitions of the unit interval induced by certain bridges with exchangeable increments. The analysis is made simple by an interpretation in terms of an aggregating server system. Random graph models with limited choice have been studied extensively with the goal of understanding the mechanism of the emergence of the giant component. One of the standard models are the Achlioptas random graph processes on a fixed set of (n ) vertices. Here at each step, one chooses two edges uniformly at random and then decides which one to add to the existing configuration according to some criterion. An important class of such rules are the bounded-size rules where for a fixed (K 1 ), all components of size greater than (K ) are treated equally. While a great deal of work has gone into analyzing the subcritical and supercritical regimes, the nature of the critical scaling window, the size and complexity (deviation from trees) of the components in the critical regime and nature of the merging dynamics has not been well understood. In this work we study such questions for general bounded-size rules. Our first main contribution is the construction of an extension of Aldous’s standard multiplicative coalescent process which describes the asymptotic evolution of the vector of sizes and surplus of all components. We show that this process, referred to as the standard augmented multiplicative coalescent (AMC) is ‘nearly’ Feller with a suitable topology on the state space. Our second main result proves the convergence of suitably scaled component size and surplus vector, for any bounded-size rule, to the standard AMC. This result is new even for the classical Erdős–Renyi setting. The key ingredients here are a precise analysis of the asymptotic behavior of various susceptibility functions near criticality and certain bounds from (The barely subcritical regime. Arxiv preprint, 2012) on the size of the largest component in the barely subcritical regime. The percolation phase transition and the mechanism of the emergence of the giant component through the critical scaling window for random graph models, has been a topic of great interest in many dierent communities ranging from statistical physics, combinatorics, computer science, social networks and probability theory. The last few years have witnessed an explosion of models which couple random aggregation rules, that specify how one adds edges to existing congurations, and choice, wherein one selects from a ‘limited’ set of edges at random to use in the conguration. These models exhibit fascinating new phenomenon, ranging from delaying or speeding up the emergence of the giant component, to percolation", where the diameter of the scaling window is several orders of magnitude smaller than that for standard random graph models. While an intense study of such models has ensued, understanding the actual emergence of the giant component and merging dynamics in the critical scaling window has remained impenetrable to a rigorous analysis. In this work we take an important step in the analysis of such models by studying one of the standard examples of such processes, namely the Bohman-Frieze model, and provide rst results on the asymptotic dynamics, through the critical scaling window, that lead to the emergence of the giant component for such models. We identify the scaling window and show that through this window, the component sizes properly rescaled converge to the standard multiplicative coalescent. Proofs hinge on a careful analysis of certain innite-type branching processes with types taking values in the space of RCLL paths, and stochastic analytic techniques to estimate susceptibility functions of the components all the way through the scaling window where these functions explode. Previous approaches for analyzing random graphs at criticality have relied largely on classical breadth-rst search techniques that exploit asymptotic connections with Brownian excursions. For dynamic random graph models evolving via general Markovian rules, such approaches fail and we develop a quite dierent set of tools that can potentially be used for the study of critical dynamics for all bounded size rules. We revisit the discrete additive and multiplicative coalescents, starting with n particles with unit mass. These cases are known to be related to some “combinatorial coalescent processes”: a time reversal of a fragmentation of Cayley trees or a parking scheme in the additive case, and the random graph process ((G(n,p))_p ) in the multiplicative case. Time being fixed, encoding these combinatorial objects in real-valued processes indexed by the line is the key to describing the asymptotic behaviour of the masses as (n + ). We propose to use the Prim order on the vertices instead of the classical breadth-first (or depth-first) traversal to encode the combinatorial coalescent processes. In the additive case, this yields interesting connections between the different representations of the process. In the multiplicative case, it allows one to answer to a stronger version of an open question of Aldous (Ann Probab 25:812–854, 1997): we prove that not only the sequence of (rescaled) masses, seen as a process indexed by the time ( ), converges in distribution to the reordered sequence of lengths of the excursions above the current minimum of a Brownian motion with parabolic drift ((B_t+ t - t^2 2, t 0) ), but we also construct a version of the standard augmented multiplicative coalescent of (Probab Theory Relat, 2013) using an additional Poisson point process. In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n > m), and l = m - n empty places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively pi + 1, pi + 2, until it finds an empty place. Pittel [42] proves that when l m goes to some positive limit β > 1, the size B1m,l1 of the largest block of consecutive cars satisfies 2(β - 1 - log β)B1m,l - 3 log log m + Ξm, where Ξm converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between B1m,l = o(m) and m - B1m,l = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. Let (B s , s≥ 0) be a standard Brownian motion and T1 its first passage time at level 1. For every t≥ 0, we consider ladder time set ℒ (t) of the Brownian motion with drift t, B (t) s = B s + ts, and the decreasing sequence F(t) = (F1(t), F2(t), …) of lengths of the intervals of the random partition of [0, T1] induced by ℒ (t) . The main result of this work is that (F(t), t≥ 0) is a fragmentation process, in the sense that for 0 ≤t < t′, F(t′) is obtained from F(t) by breaking randomly into pieces each component of F(t) according to a law that only depends on the length of this component, and independently of the others. We identify the fragmentation law with the one that appears in the construction of the standard additive coalescent by Aldous and Pitman [3].