UCL Discovery Stage
UCL home » Library Services » Electronic resources » UCL Discovery Stage

A family of extremal hypergraphs for Ryser's conjecture

Abu-Khazneh, A; Barat, J; Pokrovskiy, A; Szabo, T; (2019) A family of extremal hypergraphs for Ryser's conjecture. Journal of Combinatorial Theory, Series A , 161 pp. 164-177. 10.1016/j.jcta.2018.07.011. Green open access

[thumbnail of 1605.06361v2.pdf]
Preview
Text
1605.06361v2.pdf - Accepted Version

Download (430kB) | Preview

Abstract

Ryser’s Conjecture states that for any r-partite r-uniform hypergraph, the vertex cover number is at most r−1 times the matching number. This conjecture is only known to be true for r ≤ 3 in general and for r ≤ 5 if the hypergraph is intersecting. There has also been considerable effort made for finding hypergraphs that are extremal for Ryser’s Conjecture, i.e. r-partite hypergraphs whose cover number is r − 1 times its matching number. Aside from a few sporadic examples, the set of uniformities r for which Ryser’s Conjecture is known to be tight is limited to those integers for which a projective plane of order r − 1 exists. We produce a new infinite family of r-uniform hypergraphs extremal to Ryser’s Conjecture, which exists whenever a projective plane of order r − 2 exists. Our construction is flexible enough to produce a large number of non-isomorphic extremal hypergraphs. In particular, we define what we call the Ryser poset of extremal intersecting r-partite r-uniform hypergraphs and show that the number of maximal and minimal elements is exponential in √ r. This provides further evidence for the difficulty of Ryser’s Conjecture

Type: Article
Title: A family of extremal hypergraphs for Ryser's conjecture
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jcta.2018.07.011
Publisher version: https://doi.org/10.1016/j.jcta.2018.07.011
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Hypergraph Matching, Ryser’s Conjecture, Extremal Structure
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery-pp.ucl.ac.uk/id/eprint/10112649
Downloads since deposit
1,190Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item