EUVIMEDExplore EUVIMED
Crossref

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

Asier Calbet, Andrea Freschi

The Electronic Journal of Combinatorics · 2026-07-03 · 33 (3)

DOI: 10.37236/13055 ↗

At a glance

Journal article in The Electronic Journal of Combinatorics, published online on 2026-07-03. Written by Asier Calbet and 1 co-authors.

AbstractBibliographic detailsCiteRelated studies

Abstract (original language)

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}$.

Cite

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}
}
Start for free →