Mean-field approximation conjecture for upper tails of strictly balanced subgraph counts

Let HH be a strictly balanced graph, with vHv_H vertices, eHe_H edges, maximum degree Δ\Delta, and parameter αH\alpha_H^*. Let Ψp,H(δ)\Psi_{p,H}(\delta) denote the mean-field variational problem for the upper tail of the number N(H,G(n,p))N(H,\mathbb{G}(n,p)) of copies of HH in the Erdős–Rényi random graph. Mean-field approximation conjecture. For every ε(0,1)\varepsilon\in(0,1), δ>0\delta>0, and pp satisfying

pn1/Δ,nvHpeH(logn)αH/(αH1),p\ll n^{-1/\Delta},\qquad n^{v_H}p^{e_H}\gg (\log n)^{\alpha_H^*/(\alpha_H^*-1)},

for all sufficiently large nn,

(1ε)Ψp,H(δ(1ε))logP(N(H,G(n,p))(1+δ)nvHpeH)(1+ε)Ψp,H(δ(1+ε)).(1-\varepsilon)\Psi_{p,H}\left(\delta(1-\varepsilon)\right)\leqslant -\log\mathbb{P}\left(N(H,\mathbb{G}(n,p))\geqslant(1+\delta)n^{v_H}p^{e_H}\right)\leqslant(1+\varepsilon)\Psi_{p,H}\left(\delta(1+\varepsilon)\right).

The theorem immediately preceding this conjecture establishes the analogous mean-field approximation for stars H=K1,rH=K_{1,r} in a different sparsity regime. The conjecture proposes that the same approximation holds for every strictly balanced graph in the stated regime, extending the known result for irregular subgraph counts and identifying the variational problem as the correct logarithmic upper-tail scale.

Sources & referencesView supporting material

Primary source

Anirban Basak and Shaibal Karmakar, “Upper tail bounds for irregular graphs”, arXiv:2503.05311 (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.