Expansion of Percolation Critical Points for Hamming Graphs

DOI10.1017/S0963548319000208zbMATH Open1434.60287arXiv1701.02099OpenAlexW2577574236MaRDI QIDQ5222571FDOQ5222571

Authors: Lorenzo Federico, Remco van der Hofstad, Tim Hulshof, F. den Hollander 

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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 $dinmathbbN$ fixed and $noinfty$, �egin{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 ErdH{o}s-R'enyi random graph.

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

Recommendations

• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• Critical percolation on certain nonunimodular graphs
• Random subgraphs of the 2D Hamming graph: The supercritical phase
• The sharp threshold for percolation on expander graphs
• Existence of a phase transition of the interchange process on the Hamming graph
• Vertex percolation on expander graphs
• Partial Hamming graphs and expansion procedures
• Connectivity threshold for random subgraphs of the Hamming graph
• A note about critical percolation on finite graphs
• On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Processes in random environments (60K37) Percolation (82B43)

Cites Work

• Random graphs and complex networks. Volume 1
• Title not available (Why is that?)
• Self-avoiding walk in 5 or more dimensions
• Percolation
• The birth of the giant component
• Evolution of the \(n\)-cube
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Sharpness of the phase transition in percolation models
• On the largest component of the random graph at a nearcritical stage
• Random graphs.
• Random graph dynamics
• Novel scaling limits for critical inhomogeneous random graphs
• Tree graph inequalities and critical behavior in percolation models
• On the critical percolation probabilities
• Connectivity threshold for random subgraphs of the Hamming graph
• Non-backtracking random walk
• Random subgraphs of finite graphs. II: The lace expansion and the triangle condition
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube
• The Evolution of Random Graphs
• Mean-field critical behaviour for percolation in high dimensions
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• Inequalities with applications to percolation and reliability
• On the critical probability in percolation
• The Structure of a Random Graph at the Point of the Phase Transition
• Hypercube percolation
• Critical random graphs: Diameter and mixing time
• Component sizes of the random graph outside the scaling window
• The component sizes of a critical random graph with given degree sequence
• Progress in high-dimensional percolation and random graphs
• Random subgraphs of the 2D Hamming graph: The supercritical phase
• Unlacing hypercube percolation: a survey
• The second largest component in the supercritical 2D Hamming graph
• Critical percolation on random regular graphs
• Expansion in ${\boldsymbol{n^{-1}}}$ for Percolation Critical Values on the $n$-cube and ${\boldsymbol{{\mathbb Z}^n}}$: the First Three Terms
• Some limit theorems for the total progeny of a branching process
• Asymptotic expansions inn−1 for percolation critical values on then-Cube and ℤn
• A moment-generating formula for Erdős-Rényi component sizes
• Existence of a phase transition of the interchange process on the Hamming graph

Cited In (6)

• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• A moment-generating formula for Erdős-Rényi component sizes
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• Expansion for the critical point of site percolation: the first three terms
• Parking on Cayley trees and frozen Erdős-Rényi
• Expansion in ${\boldsymbol{n^{-1}}}$ for Percolation Critical Values on the $n$-cube and ${\boldsymbol{{\mathbb Z}^n}}$: the First Three Terms

This page was built for publication: Expansion of Percolation Critical Points for Hamming Graphs

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