The Asymptotic Behaviour of $sat(n,\mathcal{F})$

Abstract

For a family $\mathcal{F}$ of graphs, $sat(n,\mathcal{F})$ is the minimum number of edges in a graph~$G$ on $n$ vertices which does not contain any of the graphs in $\mathcal{F}$ but such that adding any new edge to $G$ creates a graph in $\mathcal{F}$. For singleton families $\mathcal{F}$, Tuza conjectured that $sat(n,\mathcal{F})/n$ converges and Truszczynski and Tuza discovered that either $sat(n,\mathcal{F})= \left(1-1/r\right)n+o(n)$ for some integer $r \geq 1$ or $ sat(n,\mathcal{F}) \geq n+o(n) $. This is often cited in the literature as the main progress towards proving Tuza's Conjecture. Unfortunately, the proof is flawed. We give a correct proof, which requires a novel construction. Moreover, for finite families $\mathcal{F}$, we completely determine the possible asymptotic behaviours of $sat(n,\mathcal{F})$ in the sparse regime $sat(n,\mathcal{F}) \leq n+o(n)$. As a result, we obtain many examples of finite families $\mathcal{F}$ such that $sat(n,\mathcal{F})/n$ diverges. Finally, we essentially determine which sequences of integers are of the form $\left(sat(n,\mathcal{F})\right)_{n \geq 0}$ for some (possibly infinite) family $\mathcal{F}$.