TY - JOUR

T1 - Improved bounds on a generalization of Tuza’s conjecture

AU - Basit, Abdul

AU - McGinnis, Daniel

AU - Simmons, Henry

AU - Sinnwell, Matt

AU - Zerbib, Shira

N1 - Funding Information:
∗Supported by NSF grant DMS-1839918 (RTG). †Supported by NSF grant DMS-1953929.
Publisher Copyright:
© The authors.

PY - 2022/10/21

Y1 - 2022/10/21

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85140834107&partnerID=8YFLogxK

U2 - 10.37236/10829

DO - 10.37236/10829

M3 - Article

AN - SCOPUS:85140834107

SN - 1077-8926

VL - 29

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

IS - 4

M1 - P4.14

ER -