Debsoumya Chakraborti, Some classical problems in graph saturation

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$. The function $\mathrm{sat}(n,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph.

In the first half of the talk, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964), which determined the value of $\mathrm{sat}(n,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices, confirming a conjecture of Kritschgau, Methuku, Tait, and Timmons. We further establish a corresponding stability result.

In the second half, we will focus on a central conjecture in graph saturation made by Tuza (1986), which states that for every graph $F$, the limit $\underset{n\to \mathrm{\infty }}{lim}\frac{\mathrm{sat}(n,F)}{n}$ exists. We make progress in the negative direction of this conjecture.

This talk will be based on a joint work with Po-Shen Loh.