Back to Search Start Over

Weakly saturated hypergraphs and a conjecture of Tuza

Authors :
Shapira, Asaf
Tyomkyn, Mykhaylo
Publication Year :
2021

Abstract

Given a fixed hypergraph $H$, let $\mbox{wsat}(n,H)$ denote the smallest number of edges in an $n$-vertex hypergraph $G$, with the property that one can sequentially add the edges missing from $G$, so that whenever an edge is added, a new copy of $H$ is created. The study of $\mbox{wsat}(n,H)$ was introduced by Bollob\'as in 1968, and turned out to be one of the most influential topics in extremal combinatorics. While for most $H$ very little is known regarding $\mbox{wsat}(n,H)$, Alon proved in 1985 that for every graph $H$ there is a limiting constant $C_H$ so that $\mbox{wsat}(n,H)=(C_H+o(1))n$. Tuza conjectured in 1992 that Alon's theorem can be (appropriately) extended to arbitrary $r$-uniform hypergraphs. In this paper we prove this conjecture.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2111.02373
Document Type :
Working Paper