Talk information

Date: Sunday, December 04, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Ilay Hoshen (TAU)
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.