Abstract

Let $H$ be a graph with $\chi(H) = r+1$. Simonovits's theorem states that, for every edge-critical graph $H$, the unique largest $H$-free subgraph of $K_n$ is its largest $r$-partite subgraph, provided that $n$ is sufficiently large. We show that the same holds with $K_n$ replaced by $G_{n,p}$ whenever $H$ is also strictly 2-balanced and $p \ge C_H n^{-1/m_2(H)} \log(n)^{1/(e(H)-1)}$ for some explicit constant $C_H > 0$, which we believe to be optimal. This (partially) resolves a conjecture of DeMarco and Kahn, who proved the result in the case where $H$ is a complete graph. This is joint work with Ilay Hoshen.

Speaker Intro

Wojciech Samotij is an associate professor at the School of Mathematical Sciences of Tel Aviv University. He obtained his PhD in 2010 from the University of Illinois at Urbana-Champaign under the supervision of Jozsef Balogh. Before joining the faculty of Tel Aviv University, Wojciech spent two years there as a post-doc; additionally, he held a junior research fellowship at Trinity College, Cambridge for another two years. He received George P\'olya Prize in Combinatorics, D\'enes K\"onig Prize of SIAM, Erd\H{o}s Prize, European Prize in Combinatorics and an ERC Consolidator grant. His primary research interests are extremal and probabilistic combinatorics, but some of his recent work focused on the theory of large deviations.