Minimizing the numbers of cliques and cycles of fixed size in an F-saturated graph
This paper considers two important questions in the well-studied theory of graphs that are F-saturated. 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 first resolve a fundamental question of minimizing the number of cliques of size r in a Ks-saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait, and Timmons. We also go further and prove a corresponding stability result. Next we minimize the number of cycles of length r in a Ks-saturated graph for all sufficiently large numbers of vertices, and classify the extremal graphs for most values of r, answering another question of Kritschgau, Methuku, Tait, and Timmons for most r. We then move on to a central and longstanding conjecture in graph saturation made by Tuza, which states that for every graph F, the limit $\lim_{n \rightarrow \infty} \frac{\sat(n, F)}{n}$ exists, where $\sat(n, F)$ denotes the minimum number of edges in an n-vertex F-saturated graph. Pikhurko made progress in the negative direction by considering families of graphs instead of a single graph, and proved that there exists a graph family F of size 4 for which $\lim_{n \rightarrow \infty} \frac{\sat(n, \mathcal{F})}{n}$ does not exist (for a family of graphs F, a graph G is called F-saturated if G does not contain a copy of any graph in F, but the addition of any edge creates a copy of a graph in F, and $\sat(n, \mathcal{F})$ is defined similarly). We make the first improvement in 15 years by showing that there exist infinitely many graph families of size 3 where this limit does not exist. Our construction also extends to the generalized saturation problem when we minimize the number of fixed-size cliques.
