Ryser's conjecture for t-intersecting hypergraphs

DOI10.1016/J.JCTA.2020.105366MaRDI QIDQ2221906zbMATH OpenOpenAlexWikidataFDO

Authors Anurag Bishnoi, Shagnik Das, Patrick Morris, Tibor Szabó

Publication date 3 February 2021

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2001.04132

zbMATH Keywords

intersecting hypergraphsRyser's conjecturevertex cover

Mathematics Subject Classification ID

Hypergraphs (05C65)

Abstract: 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'{a}ly and T'{o}thm'{e}r'{e}sz considered the problem under the assumption that the hypergraph is $t$-intersecting, conjecturing that the cover number $au(mathcalH)$ of such a hypergraph $mathcalH$ is at most $r-t$. In these papers, it was proven that the conjecture is true for $rleq4t-1$, but also that it need not be sharp; when $r=5$ and $t=2$, one has $au(mathcalH)leq2$. We extend these results in two directions. First, for all $tgeq2$ and $rleq3t-1$, we prove a tight upper bound on the cover number of these hypergraphs, showing that they in fact satisfy $au(mathcalH)leqlfloor(r-t)/2floor+1$. Second, we extend the range of $t$ for which the conjecture is known to be true, showing that it holds for all $rleqfrac367t-5$. 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 $kgeq3$ and $tgeq1$. We further give bounds on the cover numbers of strictly $t$-intersecting hypergraphs and the $s$-cover numbers of $t$-intersecting hypergraphs.

Recommendations

• A comment on Ryser's conjecture for intersecting hypergraphs
• On Ryser's conjecture for t-intersecting and degree-bounded hypergraphs
• Coverings and matchings in r-partite hypergraphs
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• Nonintersecting Ryser Hypergraphs

Cites work

• A family of extremal hypergraphs for Ryser's conjecture
• A note on intersecting hypergraphs with large cover number
• Almost all Steiner triple systems are almost resolvable
• Exact \(k\)-wise intersection theorems
• Extremal hypergraphs for Ryser's conjecture
• Extremal set systems with restricted \(k\)-wise intersections.
• Extremal set systems with weakly restricted intersections
• Extremal systems with upper-bounded odd intersections
• Finite projective spaces and intersecting hypergraphs
• scientific article; zbMATH DE number 3884213 (Why is no real title available?)
• scientific article; zbMATH DE number 3561362 (Why is no real title available?)
• scientific article; zbMATH DE number 3430675 (Why is no real title available?)
• scientific article; zbMATH DE number 3392464 (Why is no real title available?)
• Monochromatic components in edge-colored complete uniform hypergraphs
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs
• Nonintersecting Ryser Hypergraphs
• On \(k\)-wise set-intersections and \(k\)-wise Hamming-distances
• On finite set-systems whose every intersection is a kernel of a star
• On Ryser's conjecture for t-intersecting and degree-bounded hypergraphs
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• On Sperner families satisfying an additional condition
• Ryser's conjecture for tripartite 3-graphs
• Set-systems with restricted multiple intersections
• Symmetric designs as the solution of an extremal problem in combinatorial set theory

Cited in

(5)

• A comment on Ryser's conjecture for intersecting hypergraphs
• On Ryser's conjecture for t-intersecting and degree-bounded hypergraphs
• Generalizations and strengthenings of Ryser's conjecture
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Nonintersecting Ryser Hypergraphs

This page was built for publication: Ryser's conjecture for \(t\)-intersecting hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2221906)