Combinatorics: Benny Sudakov (ETH) "Subgraph statistics"

Mon, 24/12/201811:00-13:00
Rothberg CS room B500, Safra campus, Givat Ram
Speaker: Benny Sudakov, ETH, Zurich
Title: Subgraph statistics
Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given
a large graph $G$, what is the fraction of $k$-vertex
subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or
complete, and $\ell$ is zero or $\binom k 2$,
this fraction can be exactly 1. On the other hand if $\ell$ is not one
these extreme values, then by Ramsey's theorem, this
fraction is strictly smaller than 1.
The systematic study of the above question was recently initiated by
Alon, Hefetz, Krivelevich and Tyomkyn who proposed several natural conjectures.
In this talk we discuss a theorem which proves one of their
conjectures and implies an
asymptotic version of another. We also make some first steps towards analogous
question for hypergraphs. Our proofs involve some Ramsey-type arguments, and a
number of different probabilistic tools, such as polynomial anticoncentration
inequalities and hypercontractivity.
Joint work with M. Kwan and T. Tran