TAU Combinatorics Seminar 2022/23

When: Sunday, December 4, 10am
Where: Schreiber 309
Speaker: Ilay Hoshen, Tel Aviv University
Title: Simonovits's theorem for random graphs

Abstract:

Let $H$ be a graph with $\chi(H) = r+1$. Simonovits's theorem states that the unique largest $H$-free subgraph of $K_n$ is its largest $r$-partite subgraph if and only if $H$ is edge-critical. We show that the same holds with $K_n$ replaced by $G_{n,p}$ whenever $H$ is also strictly 2-balanced and \begin{align*} p \geq C n^{-1/m_2(H)} \log(n)^{1/(e(H)-1)}, \end{align*} for some constant $C > 0$. This is best possible up to the choice of the constant $C$. This (partially) resolves a conjecture of DeMarco and Kahn, who proved the result in the case where $H$ is a complete graph. Moreover, we prove the result with explicit constant $C = C(H)$ that we believe to be optimal.

Joint work with Wojciech Samotij.