The polylogarithmic susceptibility conjecture for bounded-degree graphs

From papers

Fix a maximum degree dd. Let (Gn)n1(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

limnPλ[S(Gn)Cd,λlogVn]=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.

Progress summary

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

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.