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

DOI10.1007/S00440-009-0200-3MaRDI QIDQ2380761zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad, Malwina Luczak

Publication date 12 April 2010

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.1607

zbMATH Keywords

giant component Hamming graph percolation random graph supercritical

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study random subgraphs of the 2-dimensional Hamming graph H(2,n), which is the Cartesian product of two complete graphs on

n

vertices. Let

p

be the edge probability, and write

p = f r a c 1 + v e p 2 (n - 1)

for some

v e p i n R

. In Borgs et al., Random subgraphs of finite graphs: I. The scaling window under the triangle condition, Rand. Struct. Alg. (2005), and in Borgs et al., Random subgraphs of finite graphs: II. The lace expansion and the triangle condition, Ann. Probab. (2005), the size of the largest connected component was estimated precisely for a large class of graphs including H(2,n) for

v e p l e q L a m b d a V^{- 1 / 3}

, where

L a m b d a > 0

is a constant and

V = n^{2}

denotes the number of vertices in H(2,n). Until now, no matching lower bound on the size in the supercritical regime has been obtained. In this paper we prove that, when

v e p g g (l o g V)^{1 / 3} V^{- 1 / 3}

, then the largest connected component has size close to

2 v e p V

with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of

p

are supercritical. Barring the factor

(l o g c h s V)^{1 / 3}

, this identifies the size of the largest connected component all the way down to the critical

p

window.

Review text

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.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Random subgraphs of the 2D Hamming graph: The supercritical phase

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380761)