Alon–Hefetz–Krivelevich–Tyomkyn edge-statistics conjecture
Statement
Given a graph and a uniformly random -vertex subset , let be the number of edges induced by . Define
and
Edge-statistics conjecture. For all with , we have
The quantity measures the largest asymptotic fraction of -vertex subsets inducing exactly edges. The paper proves this bound in the range , 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.