ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Given a graph GG and a uniformly random kk-vertex subset AA, let XG,kX_{G,k} be the number of edges induced by AA. 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\},

and

ind⁡(k,ℓ):=lim⁡n→∞I(n,k,ℓ).\operatorname{ind}(k,\ell):=\lim_{n\to\infty}I(n,k,\ell).

Edge-statistics conjecture. For all k,ℓ∈Nk,\ell\in\mathbb{N} with 0<ℓ<(k2)0<\ell<\binom{k}{2}, we have

ind⁡(k,ℓ)⩽1/e+ok(1).\operatorname{ind}(k,\ell)\leqslant 1/e+o_k(1).

The quantity ind⁡(k,ℓ)\operatorname{ind}(k,\ell) measures the largest asymptotic fraction of kk-vertex subsets inducing exactly ℓ\ell edges. The paper proves this bound in the range 1⩽ℓ⩽ok(k6/5)1\leqslant\ell\leqslant o_k(k^{6/5}), while the general assertion is presented as a conjecture originating with Alon, Hefetz, Krivelevich, and Tyomkyn.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.