Alon–Hefetz–Krivelevich–Tyomkyn sparse-edge decay conjecture

For a graph GG, let XG,kX_{G,k} be the number of edges induced by a uniformly random kk-vertex subset, and define

I(n,k,):=max{P[XG,k=]:v(G)=n},I(n,k,\ell):=\max\{\mathbb{P}[X_{G,k}=\ell]:v(G)=n\},

with

ind(k,):=limnI(n,k,).\operatorname{ind}(k,\ell):=\lim_{n\to\infty}I(n,k,\ell).

Sparse-edge decay conjecture. For all k,Nk,\ell\in\mathbb{N} with

min{,(k2)}=ωk(k),\min\left\{\ell,\binom{k}{2}-\ell\right\}=\omega_k(k),

we have

ind(k,)=ok(1).\operatorname{ind}(k,\ell)=o_k(1).

This conjecture predicts that the asymptotic inducibility tends to zero when the induced edge count and its complementary count both grow faster than linearly in kk. The supplied text does not state whether this conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Anders Martinsson, Frank Mousset, Andreas Noever and Miloš Trujić, “The edge-statistics conjecture for k^6/5”, arXiv:1809.02576 (2021).

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.