Given graphs $G$ and $H$, we say that $G$ is $H$-free is $G$ does not contain $H$ as a (not necessarily induced) subgraph. For a positive integer $n$, denote by $\mathrm{ex}(n,H)$ the largest number of edges in an $H$-free graph with $n$ vertices (the Turán number of $H$). The classical theorem of Erdős, Kleitman, and Rothschild states that, for every $r \geq 3$, there are $2^{\mathrm{ex}(n,K_r)+o(n^2)}$ many $K_r$-free graphs with vertex set $\{1, \ldots, n\}$.
There exist (at least) three different derivations of this estimate in the literature: an inductive argument based on the Kővári–Sós–Turán theorem, a proof based on Szemerédi's regularity lemma, and an argument based on the hypergraph container theorems. In this talk, we present yet another proof of this bound that exploits connections between entropy and independence.
This is joint work with Gady Kozma, Tom Meyerovitch, and Ron Peled.