## EE Student Information

### The Department of Electrical Engineering supports Black Lives Matter. Read more.

• • • • •

Updates will be posted on this page, as well as emailed to the EE student mail list.

As always, use your best judgement and consider your own and others' well-being at all times.

# Probability Seminar presents "On the edge-statistics conjecture" Topic:
On the edge-statistics conjecture
Monday, February 24, 2020 - 4:00pm
Venue:
Sequoia Hall Room 200
Speaker:
Lisa Sauermann (Stanford Mathematics)
Abstract / Description:

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