pith. sign in

arxiv: 1605.06361 · v2 · pith:DTZV7Q5Anew · submitted 2016-05-20 · 🧮 math.CO

A family of extremal hypergraphs for Ryser's conjecture

classification 🧮 math.CO
keywords conjectureryserhypergraphsnumberextremalexistspartiteuniform
0
0 comments X
read the original 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\leq 3$ in general and for $r\leq 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 {\em Ryser poset} of extremal intersecting $r$-partite $r$-uniform hypergraphs and show that the number of maximal and minimal elements is exponential in $\sqrt{r}$. This provides further evidence for the difficulty of Ryser's Conjecture.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.