A Tight Fractional Version of Generalized Tuza's Conjecture
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)\le\lceil\frac{r+1}{2}\rceil\,ν(H)$, which for $r=3$ generalizes Tuza's conjecture on triangles. We prove that the fractional relaxation $τ^*(H)$ of $τ(H)$ satisfies $τ^*(H)\le\frac{r+1}{2}\,ν(H)$. This constant is best possible for every $r$, and for $r\ge4$ it improves on the previous bound of roughly $3r/4$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.35836
curl -X POST /api/v1/records/arxiv/2609.35836/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35836/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'