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

About 8 years old · traced to

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,ℓ)=lim⁡n→∞I(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.

References

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.