The polylogarithmic susceptibility conjecture for bounded-degree graphs

About 10 years old · traced to

Fix a maximum degree dd. Let (Gn)n≥1(G_n)_{n\geq1} be a sequence of finite connected graphs, with Gn=(Vn,En)G_n=(V_n,E_n), ∣Vn∣→∞|V_n|\to\infty, and maximum degree at most dd. The polylogarithmic susceptibility conjecture. There exist constants Cd,λ>0C_{d,\lambda}>0 and ℓ>0\ell>0 such that

lim⁡n→∞Pλ[S(Gn)≤Cd,λlog⁡ℓ∣Vn∣]=1.\lim_{n\to\infty}\mathbb{P}_{\lambda}\left[\mathcal{S}(G_n)\leq C_{d,\lambda}\log^{\ell}|V_n|\right]=1.

The conjecture asserts a uniform polylogarithmic upper bound on susceptibility for bounded-degree graph sequences. The source further speculates on particular values of ℓ\ell and the dependence of the constant, but those stronger speculations are not included in this row because they are presented as suspicions rather than the stated conjecture.

References

Primary source

Itai Benjamini, Luiz Renato Fontes, Jonathan Hermon and Fabio Prates Machado, “On an epidemic model on finite graphs”, arXiv:1610.04301 (2025).

Additional references

2 papers in this index state this conjecture (2016). The statement above is taken from the most recent of them; the others are arXiv:1609.08738.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.