
Suppose we are given integers k ≥ 1 and 0 < ` < k 2 . When sampling a k-vertex subset uniformly at random from a (very large) n-vertex graph G, how large can the probability be that there are exactly ` edges within the sampled k-vertex subset? Let ind(k, `) be the limit of this maximum possible probability as n goes to infinity. Alon, Hefetz, Krivelevich and Tyomkyn conjectured that ind(k, `) ≤ e −1 + o(1) for all k ≥ 1 and 0 < ` < k 2 . The constant e −1 in this conjecture is best-possible, since for ` = 1 and ` = k −1 one can easily show that ind(k, `) ≥ e −1 − o(1). Kwan, Sudakov and Tran proved the conjecture in the case Ω(k) ≤ ` ≤ k 2 − Ω(k). In joint work with Jacob Fox, we solved the remaining cases of the conjecture. This talk will discuss our results, as well as our proof for the case ` = 1 (which is one of the cases in which the conjecture is tigh