Weakly saturated hypergraphs and a conjecture of Tuza

2021/11/03 by A. Shapira, Shapira, Asaf, Mykhaylo Tyomkyn +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2111.02373

openalex publication_date 2021/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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ás 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 C_H so that 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.

Cited by

• When does a tree activate the random graph?

Related

• A short proof of Tuza's conjecture for weak saturation in hypergraphs
• Weak saturation rank: a failure of linear algebraic approach to weak saturation
• Weak saturation in graphs: a combinatorial approach
• A generalization of Tuza's conjecture
• Exact Bounds for Some Hypergraph Saturation Problems