TY - JOUR

T1 - Ryser's Conjecture for t-intersecting hypergraphs

AU - Bishnoi, Anurag

AU - Das, Shagnik

AU - Morris, Patrick

AU - Szabó, Tibor

PY - 2021

Y1 - 2021

N2 - A well-known conjecture, often attributed to Ryser, states that the cover number of an r-partite r-uniform hypergraph is at most r−1 times larger than its matching number. Despite considerable effort, particularly in the intersecting case, this conjecture remains wide open, motivating the pursuit of variants of the original conjecture. Recently, Bustamante and Stein and, independently, Király and Tóthmérész considered the problem under the assumption that the hypergraph is t-intersecting, conjecturing that the cover number τ(H) of such a hypergraph H is at most r−t. In these papers, it was proven that the conjecture is true for r≤4t−1, but also that it need not be sharp; when r=5 and t=2, one has τ(H)≤2. We extend these results in two directions. First, for all t≥2 and r≤3t−1, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy τ(H)≤⌊(r−t)/2⌋+1. Second, we extend the range of t for which the conjecture is known to be true, showing that it holds for all [Formula presented]. We also introduce several related variations on this theme. As a consequence of our tight bounds, we resolve the problem for k-wise t-intersecting hypergraphs, for all k≥3 and t≥1. We further give bounds on the cover numbers of strictly t-intersecting hypergraphs and the s-cover numbers of t-intersecting hypergraphs.

AB - A well-known conjecture, often attributed to Ryser, states that the cover number of an r-partite r-uniform hypergraph is at most r−1 times larger than its matching number. Despite considerable effort, particularly in the intersecting case, this conjecture remains wide open, motivating the pursuit of variants of the original conjecture. Recently, Bustamante and Stein and, independently, Király and Tóthmérész considered the problem under the assumption that the hypergraph is t-intersecting, conjecturing that the cover number τ(H) of such a hypergraph H is at most r−t. In these papers, it was proven that the conjecture is true for r≤4t−1, but also that it need not be sharp; when r=5 and t=2, one has τ(H)≤2. We extend these results in two directions. First, for all t≥2 and r≤3t−1, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy τ(H)≤⌊(r−t)/2⌋+1. Second, we extend the range of t for which the conjecture is known to be true, showing that it holds for all [Formula presented]. We also introduce several related variations on this theme. As a consequence of our tight bounds, we resolve the problem for k-wise t-intersecting hypergraphs, for all k≥3 and t≥1. We further give bounds on the cover numbers of strictly t-intersecting hypergraphs and the s-cover numbers of t-intersecting hypergraphs.

KW - Intersecting hypergraphs

KW - Ryser's conjecture

KW - Vertex cover

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

U2 - 10.1016/j.jcta.2020.105366

DO - 10.1016/j.jcta.2020.105366

M3 - Article

AN - SCOPUS:85097769363

SN - 0097-3165

VL - 179

SP - 1

EP - 23

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

M1 - 105366

ER -