PreprintCC BY 4.0arXiv
A Tight Fractional Version of Generalized Tuza's Conjecture
Abstract
For an r-uniform hypergraph H, let ν(H) be the maximum number of edges no two of which share r−1 vertices, and τ(H) the minimum number of (r−1)-sets such that every edge contains one of them. Aharoni and Zerbib conjectured that τ(H)≤⌈(r+1)/2⌉ ν(H), which for r=3 generalizes Tuza's conjecture on triangles. We prove that the fractional relaxation τ*(H) of τ(H) satisfies τ*(H)≤(r+1)/2 ν(H). This constant is best possible for every r, and for r≥4 it improves on the previous bound of roughly 3r/4.
Related
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
- Tuza's Conjecture under an Edge-Count Condition
- Tuza's Ryser-conjecture claim for four-partite hypergraphs with matching number two
- A Bound Below 2.8 for Tuza's Conjecture
- Tight connectivity and shadow densities in generalized Erdős--Rogers problems
BibTeX
@misc{wang2026tight,
title = {{A Tight Fractional Version of Generalized Tuza's Conjecture}},
author = {Sichen Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35836},
eprint = {2609.35836},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35836},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Tight Fractional Version of Generalized Tuza's Conjecture
AU - Sichen Wang
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.35836
UR - https://arxiv.org/abs/2609.35836
AB - For an r-uniform hypergraph H, let ν(H) be the maximum number of edges no two of which share r−1 vertices, and τ(H) the minimum number of (r−1)-sets such that every edge contains one of them. Aharoni and Zerbib conjectured that τ(H)≤⌈(r+1)/2⌉ ν(H), which for r=3 generalizes Tuza's conjecture on triangles. We prove that the fractional relaxation τ^*(H) of τ(H) satisfies τ^*(H)≤(r+1)/2 ν(H). This constant is best possible for every r, and for r≥4 it improves on the previous bound of roughly 3r/4.
ER -