Random subgraphs of the 2D Hamming graph: The supercritical phase (Q2380761)

This paper deals with random subgraphs of \(H(2,n)\). Writing \([n]=\{1,2,\dots ,n\}\), \(H(2,n)\) has vertex set \([n]\times[n]\) with two vertices adjacent if and only if they differ in exactly one co-ordinate. In particular, it is vertex-transitive with \(V=n^{2}\) vertices and degree \(\Omega=2(n-1)\). A random subgraph of \(H(2,n)\) is formed by saying that each edge is kept with probability \(p=p(n)\) and otherwise discarded, independently of all other edges. As so often in the theory of random graphs, we study the order of the largest component of the resulting random graphs, \(| {\mathcal C}_{max}|\). It has been known for some time that if \(p_{c}\) is defined to be the unique \(p\) such that the expected order of the component containing a given vertex \(v\) (which is independent of \(v\) by vertex-transitivity) is equal to \(\lambda V^{1/3}\) for a suitably small constant \(\lambda >0\), then there is a phase transition near \(p_{c}\), in that the order of the largest component `jumps', in a suitable technical sense. However these earlier results of Borgs, Chayes, van der Hofstad, Slade and Spencer (which work more generally than \(H(2,n)\)) have a weakness for the case \(p=p_{c}+\varepsilon/\Omega\) in that they do not give a good lower bound on the maximum connected component order. The aim of the paper under review is to remedy this deficiency, for random subgraphs of \(H(2,n)\) by giving the asymptotics of \(| {\mathcal C}_{max}|\). More precisely, the main result (Theorem 1.1) is that, provided \(p=p_{c}+\varepsilon/\Omega\) where \(V^{-1/3}\log(V)\ll \varepsilon \ll 1\), we have \[ | {\mathcal C}_{max}|=2\varepsilon n^{2}(1+o_{p}(1)). \] The ideal above would be to have asymptotics for \(| {\mathcal C}_{max}|\) which work for the slightly larger range \(\;V^{-1/3}\ll \varepsilon \ll 1\). Such a result has since been provided by \textit{A. Nachmias} [Geom. Funct. Anal 19, 1171--1194 (2009; Zbl 1182.60025)]. Here is some idea of the proof. We first note that, setting \(Z_{\geq k}=\sum_{v\in V(H(2,n))} I[| C(v)| \geq k]\) where \(C(v)\) is the component of the vertex \(v\), we have \(| {\mathcal C}_{max}| \geq k\) if and only if \(Z_{\geq k}\geq 1\). Thus good concentration of measure results for \(Z_{\geq k}\) lead to bounds on \(| {\mathcal C}_{max}|\). Two cases have to be looked at: first, the smallest \(k\) such that \(P(| C(v)| \geq k)\) is very close to \(2\varepsilon\), where the relevant concentration bound is Proposition 2.2. of the paper, a delicate second-moment argument: this plus information on the tails of the component size distribution lead to an upper bound on \(| {\mathcal C}_{max}|\). A rather more involved lower bound needs to find the largest \(k\) such that \(Z_{\geq k}\) is concentrated round its mean via a two-round process: one first uses branching-process related lower bounds for a \(p_{-}\) slightly less than \(p\) to obtain (weak) lower bounds and then sprinkles a few extra edges to make the probability up to \(p\), showing that in this process all `large', components from the first round are (with probability tending to 1) joined together. Techniques used include various results on the total progeny in a branching process.