ACO The ACO Seminar (2019–2020)

December 5, 3:30pm, Wean 8220
Debsoumya Chakraborti, Carnegie Mellon University
Minimizing the number of copies of \(K_r\) in a \(K_s\)-saturated graph

Abstract:

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.


Back to the ACO home page Back to the ACO Seminar schedule