The extremal susceptibility conjecture for regular graphs

Let d2d\geq2 and λ>0\lambda>0. Let G(n,d)\mathfrak{G}(n,d) be the collection of all connected nn-vertex dd-regular graphs, and let Hd,nH_{d,n} be the graph defined in the source by arranging copies of the graph obtained from the complete graph on dd vertices by deleting one edge into a cycle and joining consecutive copies by one edge. The extremal susceptibility conjecture. For fixed dd and λ\lambda,

maxGG(dn/d,d)Eλ[S(G)]=(1+o(1))Eλ[S(Hd,n)].\max_{G\in\mathfrak{G}(d\lceil n/d\rceil,d)}\mathbb{E}_{\lambda}[\mathcal{S}(G)]=(1+o(1))\mathbb{E}_{\lambda}[\mathcal{S}(H_{d,n})].

Moreover, if (dn)nN(d_n)_{n\in\mathbb{N}} diverges with dnnd_n\leq n for every nn, then for every sequence (λn)nN(\lambda_n)_{n\in\mathbb{N}},

maxGG(dnn/dn,dn)Eλn[S(G)]=(1+o(1))Eλn[S(Hdn,n)].\max_{G\in\mathfrak{G}(d_n\lceil n/d_n\rceil,d_n)}\mathbb{E}_{\lambda_n}[\mathcal{S}(G)]=(1+o(1))\mathbb{E}_{\lambda_n}[\mathcal{S}(H_{d_n,n})].

This conjecture identifies the explicitly constructed graphs Hd,nH_{d,n} as asymptotically extremal for expected susceptibility among regular connected graphs with the corresponding number of vertices and degree. The source motivates it with examples showing large susceptibility, but provides no resolution.

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).

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.