The Asymptotic Behaviour of $sat(n,\mathcal{F})$
The Electronic Journal of Combinatorics · 03.07.2026 · 33 (3)
DOI: 10.37236/13055 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 03.07.2026. Verfasst von Asier Calbet und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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}$.
Zitieren
APA
Calbet, A., & Freschi, A. (2026). The Asymptotic Behaviour of $sat(n,\mathcal{F})$. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/13055
Vancouver
Calbet A, Freschi A. The Asymptotic Behaviour of $sat(n,\mathcal{F})$. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/13055
BibTeX
@article{Calbet2026,
author = {Calbet, Asier and Freschi, Andrea},
title = {The Asymptotic Behaviour of $sat(n,\mathcalF)$},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {3},
doi = {10.37236/13055}
}
EUVIMED