A family of extremal hypergraphs for Ryser's conjecture
  • Metaadatok
Tartalom: http://real.mtak.hu/103552/
Archívum: REAL
Gyűjtemény: Status = Published
Type = Article
Subject = Q Science / természettudomány: QA Mathematics / matematika: QA166-QA166.245 Graphs theory / gráfelmélet
Cím:
A family of extremal hypergraphs for Ryser's conjecture
Létrehozó:
Abu-Khazneh, A.
Barát, János
Pokrovskiy, A.
Szabó, Tibor
Dátum:
2019
Téma:
QA166-QA166.245 Graphs theory / gráfelmélet
Tartalmi leírás:
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.
Nyelv:
angol
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Abu-Khazneh, A. and Barát, János and Pokrovskiy, A. and Szabó, Tibor (2019) A family of extremal hypergraphs for Ryser's conjecture. JOURNAL OF COMBINATORIAL THEORY SERIES A, 161. pp. 164-177. ISSN 0097-3165
Kapcsolat:
MTMT:3413557 10.1016/j.jcta.2018.07.011
Létrehozó:
cc_by