Nonintersecting Ryser Hypergraphs

DOI10.1137/19M1241556MaRDI QIDQ5210906zbMATH OpenOpenAlexWikidataFDO

Authors Anurag Bishnoi, Valentina Pepe

Publication date 16 January 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

blocking setsextremal combinatoricsRyser's conjecture

Mathematics Subject Classification ID

Hypergraphs (05C65) Transversal (matching) theory (05D15) Blocking sets, ovals, (k)-arcs (51E21)

Abstract: A famous conjecture of Ryser states that every $r$-partite hypergraph has vertex cover number at most $r-1$ times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as $r$-Ryser hypergraphs, have been studied extensively. It was recently proved by Haxell, Narins and Szab'{o} that all $3$-Ryser hypergraphs with matching number $u>1$ are essentially obtained by taking $u$ disjoint copies of intersecting $3$-Ryser hypergraphs. Abu-Khazneh showed that such a characterisation is false for $r=4$ by giving a computer generated example of a $4$-Ryser hypergraph with $u=2$ whose vertex set cannot be partitioned into two sets such that we have an intersecting $4$-Ryser hypergraph on each of these parts. Here we construct new infinite families of $r$-Ryser hypergraphs, for any given matching number $u>1$, that do not contain two vertex disjoint intersecting $r$-Ryser subhypergraphs.

Recommendations

• Ryser's conjecture for \(t\)-intersecting hypergraphs
• Hypergraphs without non-trivial intersecting subgraphs
• A comment on Ryser's conjecture for intersecting hypergraphs
• Non-uniform hypergraphs
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• On Ryser's conjecture for t-intersecting and degree-bounded hypergraphs
• Extremal hypergraphs for Ryser's conjecture
• On intersecting hypergraphs
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• On randomly generated non-trivially intersecting hypergraphs

Cites work

• A family of extremal hypergraphs for Ryser's conjecture
• A note on intersecting hypergraphs with large cover number
• Blocking sets
• Blocking Sets in Finite Projective Planes
• Extremal hypergraphs for Ryser's conjecture
• scientific article; zbMATH DE number 3884213 (Why is no real title available?)
• scientific article; zbMATH DE number 3651315 (Why is no real title available?)
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• scientific article; zbMATH DE number 878888 (Why is no real title available?)
• Maximal intersecting families and affine regular polygons in PG(2,q)
• Multipartite hypergraphs achieving equality in Ryser's conjecture
• On Ryser's conjecture for linear intersecting multipartite hypergraphs
• On the size of a blocking set in \(\text{PG}(2,p)\)
• Ovals In a Finite Projective Plane
• Ryser's conjecture for tripartite 3-graphs

Cited in

(15)

• An infinite version of Ryser's inequality
• Estimates of the independence number of a hypergraph and the Ryser conjecture
• A note on a conjecture of Ryser
• A family of extremal hypergraphs for Ryser's conjecture
• Generalizations and strengthenings of Ryser's conjecture
• Ryser's conjecture for \(t\)-intersecting hypergraphs
• More non-reconstructible hypergraphs
• The feasible matching problem
• A note on intersecting hypergraphs with large cover number
• Coverings and matchings in r-partite hypergraphs
• scientific article; zbMATH DE number 3884213 (Why is no real title available?)
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Covers in partitioned intersecting hypergraphs
• Extremal hypergraphs for Ryser's conjecture
• On Ryser's conjecture for linear intersecting multipartite hypergraphs

This page was built for publication: Nonintersecting Ryser Hypergraphs

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