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 p. Extension
pith:DTZV7Q5A Add to your LaTeX paper What is a Pith Number?
\usepackage{pith}
\pithnumber{DTZV7Q5A}

Prints a linked pith:DTZV7Q5A badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

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.