Expansion of Percolation Critical Points for Hamming Graphs. (5th January 2020)

• Record Type: Journal Article
• Authors: Federico, Lorenzo; Van Der Hofstad, Remco; Den Hollander, Frank; Hulshof, Tim
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 1(2020)
• Page Start: 68
• Page End: 100
• Publication Date: 2020-01-05
• Subjects: Primary 60K35, -- Secondary 60K37, -- 82B43; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548319000208
• Languages: English
• ISSNs: 0963-5483

Abstract

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$, $$p_c^{(d)} = {1 \over m} + {{2{d^2} - 1} \over {2{{(d - 1)}^2}}}{1 \over {{m^2}}} + O({m^{ - 3}}) + O({m^{ - 1}}{V^{ - 1/3}}), $$ which extends the asymptotics found in [10 ] 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 [16 ] 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ös–Rényi random graph.