Publication at Faculty of Mathematics and Physics |
2023
Abstract
Given a fixed hypergraph H, let 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 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 wsat(n, H), Alon proved in 1985 that for every graph H there is a limiting constant CH so that wsat(n, H) = (CH + 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.