Improved bounds on a generalization of Tuza’s conjecture

Abdul Basit, Daniel McGinnis, Henry Simmons, Matt Sinnwell, Shira Zerbib

Research output: Contribution to journalArticleResearchpeer-review

Abstract

For an r-uniform hypergraph H, let ν(m)(H) denote the maximum size of a set M of edges in H such that every two edges in M intersect in less than m vertices, and let τ(m)(H) denote the minimum size of a collection C of m-sets of vertices such that every edge in H contains an element of C. The fractional analogues of these parameters are denoted by ν∗(m)(H) and τ∗(m)(H), respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every r-uniform hypergraph (Formula Presented). In this paper we prove bounds on the ratio between the parameters τ(m) and ν(m), and their fractional analogues. Our main result is that, for every r-uniform hypergraph (Formula Presented). This improves the known bound of r−1. We also prove that, for every r-uniform hypergraph (Formula Presented), where the Turán number exr (n, k) is the maximum number of edges in an r-uniform hypergraph on n vertices that does not contain a copy of the complete r-uniform hypergraph on k vertices. Finally, we prove further bounds in the special cases (r, m) = (4, 2) and (r, m) = (4, 3).

Original languageEnglish
Article numberP4.14
Number of pages23
JournalThe Electronic Journal of Combinatorics
Volume29
Issue number4
DOIs
Publication statusPublished - 21 Oct 2022
Externally publishedYes

Cite this