Expansion of percolation critical points for hamming graphs

Lorenzo Federico (Corresponding author), Remco W. van der Hofstad, Frank den Hollander, Tim Hulshof

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let be the degree and be the number of vertices of H(d, n). Let pc(d) be the critical point for bond percolation on H(d, n). We show that, for d ∈ ℕ fixed and n → ∞, pc(d) = 1/m + 2d2 - 1/2(d -1)2 1/m2 + O (m-3)+O (m-1V-1/3), which extends the asymptotics found in [10] by one order. The term O(m-1V-1/3) is the width of the critical window. For d=4,5,6 we have & m-3 = O(m-1V-1/3), and so the above formula represents the full asymptotic expansion of pc(d). In [16] we show that this formula is a crucial ingredient in the study of critical bond percolation on H(d, n) for. 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.

Original languageEnglish
Pages (from-to)68-100
JournalCombinatorics, Probability and Computing
Volume29
Issue number1
Early online date5 Aug 2019
DOIs
Publication statusPublished - 1 Jan 2020

Fingerprint

Hamming Graph
Critical point
Lace Expansion
Lower bound
Branching Random Walk
Cartesian product
Random Graphs
Complete Graph
Susceptibility
Asymptotic Expansion
Upper bound
Term

Keywords

  • 2010 MSC Codes:
  • 82B43
  • Primary 60K35
  • Secondary 60K37

Cite this

@article{55a1c4a5be5d464baab1a99591b7f391,
title = "Expansion of percolation critical points for hamming graphs",
abstract = "The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let be the degree and be the number of vertices of H(d, n). Let pc(d) be the critical point for bond percolation on H(d, n). We show that, for d ∈ ℕ fixed and n → ∞, pc(d) = 1/m + 2d2 - 1/2(d -1)2 1/m2 + O (m-3)+O (m-1V-1/3), which extends the asymptotics found in [10] by one order. The term O(m-1V-1/3) is the width of the critical window. For d=4,5,6 we have & m-3 = O(m-1V-1/3), and so the above formula represents the full asymptotic expansion of pc(d). In [16] we show that this formula is a crucial ingredient in the study of critical bond percolation on H(d, n) for. 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{\"o}s-R{\'e}nyi random graph.",
keywords = "2010 MSC Codes:, 82B43, Primary 60K35, Secondary 60K37",
author = "Lorenzo Federico and {van der Hofstad}, {Remco W.} and {den Hollander}, Frank and Tim Hulshof",
year = "2020",
month = "1",
day = "1",
doi = "10.1017/S0963548319000208",
language = "English",
volume = "29",
pages = "68--100",
journal = "Combinatorics, Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "1",

}

Expansion of percolation critical points for hamming graphs. / Federico, Lorenzo (Corresponding author); van der Hofstad, Remco W.; den Hollander, Frank; Hulshof, Tim.

In: Combinatorics, Probability and Computing, Vol. 29, No. 1, 01.01.2020, p. 68-100.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Expansion of percolation critical points for hamming graphs

AU - Federico, Lorenzo

AU - van der Hofstad, Remco W.

AU - den Hollander, Frank

AU - Hulshof, Tim

PY - 2020/1/1

Y1 - 2020/1/1

N2 - The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let be the degree and be the number of vertices of H(d, n). Let pc(d) be the critical point for bond percolation on H(d, n). We show that, for d ∈ ℕ fixed and n → ∞, pc(d) = 1/m + 2d2 - 1/2(d -1)2 1/m2 + O (m-3)+O (m-1V-1/3), which extends the asymptotics found in [10] by one order. The term O(m-1V-1/3) is the width of the critical window. For d=4,5,6 we have & m-3 = O(m-1V-1/3), and so the above formula represents the full asymptotic expansion of pc(d). In [16] we show that this formula is a crucial ingredient in the study of critical bond percolation on H(d, n) for. 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.

AB - The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let be the degree and be the number of vertices of H(d, n). Let pc(d) be the critical point for bond percolation on H(d, n). We show that, for d ∈ ℕ fixed and n → ∞, pc(d) = 1/m + 2d2 - 1/2(d -1)2 1/m2 + O (m-3)+O (m-1V-1/3), which extends the asymptotics found in [10] by one order. The term O(m-1V-1/3) is the width of the critical window. For d=4,5,6 we have & m-3 = O(m-1V-1/3), and so the above formula represents the full asymptotic expansion of pc(d). In [16] we show that this formula is a crucial ingredient in the study of critical bond percolation on H(d, n) for. 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.

KW - 2010 MSC Codes:

KW - 82B43

KW - Primary 60K35

KW - Secondary 60K37

UR - http://www.scopus.com/inward/record.url?scp=85070364860&partnerID=8YFLogxK

U2 - 10.1017/S0963548319000208

DO - 10.1017/S0963548319000208

M3 - Article

AN - SCOPUS:85070364860

VL - 29

SP - 68

EP - 100

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 1

ER -