The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs (Q483318)

We start with a set of \(n\) vertices and build a random graph by at each time choosing a pair of vertices uniformly at random from those not already adjacent. Let \(G_{n}(t)\) denote the graph obtained when there are \(\lfloor nt/2\rfloor\) edges in the graph. It is well-known that, if \(t<1\), the large component \textbf{whp} has size \(O(\log(n))\) and, if \(t>1\), there is a single giant component which contains a positive proportion of the vertices. Further, it is known that, if \(t=1+\lambda/n^{1/3}\), then the component orders, divided by \(n^{2/3}\), converge to a certain Markov process called the standard multiplicative coalescent. This result is from [\textit{D. Aldous}, Ann. Probab. 25, No. 2, 812--854 (1997; Zbl 0877.60010)], where it was also shown that there is a similar convergence result for the (normalised) surpluses of the components, where the surplus of a component \(C\) is \(|E(C)| -(|C|-1)\) (note that the surplus is 0 if a component is a tree, so the surplus measures how far from being treelike the component is). The paper under review considers analogous results in the more general context of Achlioptas processes (instead of having a single random edge at each stage and using it, one has two edges selected uniformly at random at each stage, and chooses one of them according to a certain rule). In this paper, the rules are `bounded-size' rules: the essence of this is that for some fixed \(K\geq 1\), the rule is invariant on components of size \(>K\). \textit{J. Spencer} and \textit{N. Wormald} [Combinatorica 27, No. 5, 587--628 (2007; Zbl 1164.05062)] showed that again there is a critical value \(t_{c}\) such that if \(t<t_{c}\) the largest component has order logarithmic in \(n\), but it is a positive proportion of the vertices for \(t>t_{c}\). The main results of the paper are (far from trivial) extensions of the results of Aldous to bounded-size rule. In particular, the joint convergence of the (normalised) components orders and surpluses to a process called the standard augmented multiplicative coalescent. This process is delicate to construct, but has nice features, e.g., it is `close' to being a Feller process in a suitable sense. Careful analysis of susceptibility functions plays an important role in the proofs.