Alon–Hefetz–Krivelevich–Tyomkyn 1/e inducibility conjecture for graphs

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

I(n,k,)=max{Pr(XG,k=):V(G)=n}I(n,k,\ell)=\max\{\Pr(X_{G,k}=\ell):|V(G)|=n\}

and

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

Alon–Hefetz–Krivelevich–Tyomkyn's 1/e conjecture. For all 0<<(k2)0<\ell<\binom{k}{2} we have

ind(k,)1/e+ok(1).\operatorname{ind}(k,\ell)\le 1/e+o_k(1).

This conjecture concerns the maximum asymptotic point probability for the edge count in a random induced subgraph, and predicts a universal upper bound of 1/e1/e away from the empty and complete cases. Its status is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Matthew Kwan, Benny Sudakov and Tuan Tran, “Anticoncentration for subgraph statistics”, arXiv:1807.05202 (2018).

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.