Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph \(G\) is called \(F\)-saturated if \(G\) does not contain a subgraph isomorphic to \(F\), but the addition of any edge creates a copy of \(F\). We resolve the most fundamental question of minimizing the number of cliques of size \(r\) in a \(K_s\)-saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait and Timmons. We further prove a corresponding stability result. Joint work with Po-Shen Loh.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2019–2020)