Expansion of percolation critical points for Hamming graphs
Preprint
Abstract
The Hamming graph $H(d,n)$ is the Cartesian product of $d$ complete graphs on $n$ vertices. Let $m=d(n-1)$ be the degree and $V = n^d$ be the number of vertices of $H(d,n)$. Let $p_c^{(d)}$ be the critical point for bond percolation on $H(d,n)$. We show that, for $d \in \mathbb N$ fixed and $n \to \infty$, \begin{equation*} p_c^{(d)}= \dfrac{1}{m} + \dfrac{2d^2-1}{2(d-1)^2}\dfrac{1}{m^2} + O(m^{-3}) + O(m^{-1}V^{-1/3}), \end{equation*} which extends the asymptotics found in \cite{BorChaHofSlaSpe05b} by one order. The term $O(m^{-1}V^{-1/3})$ is the width of the critical window. For $d=4,5,6$ we have $m^{-3} = O(m^{-1}V^{-1/3})$, and so the above formula represents the full asymptotic expansion of $p_c^{(d)}$. In \cite{FedHofHolHul16a} \st{we show that} this formula is a crucial ingredient in the study of critical bond percolation on $H(d,n)$ for $d=2,3,4$. The proof uses a lace expansion for the upper bound and a novel comparison with a branching random walk for the lower bound. The proof of the lower bound also yields a refined asymptotics for the susceptibility of a subcritical Erd\H{o}s-R\'enyi random graph.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- The second largest component in the supercritical 2D Hamming graphRandom Structures & Algorithms, 2009
- Critical percolation on random regular graphsRandom Structures & Algorithms, 2009
- Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-CubeCombinatorica, 2006
- Random subgraphs of finite graphs: I. The scaling window under the triangle conditionRandom Structures & Algorithms, 2005
- On the Largest Component of the Random Graph at a Nearcritical StageJournal of Combinatorial Theory, Series B, 2001
- The birth of the giant componentRandom Structures & Algorithms, 1993
- Mean-field critical behaviour for percolation in high dimensionsCommunications in Mathematical Physics, 1990
- Sharpness of the phase transition in percolation modelsCommunications in Mathematical Physics, 1987
- Tree graph inequalities and critical behavior in percolation modelsJournal of Statistical Physics, 1984
- On the critical percolation probabilitiesProbability Theory and Related Fields, 1981