We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Multipartite Hypergraphs Achieving Equality in Ryser's Conjecture.
- Authors
Aharoni, Ron; Barát, János; Wanless, Ian
- Abstract
A famous conjecture of Ryser () is that in an $$r$$ -partite hypergraph the covering number is at most $$r-1$$ times the matching number. If true, this is known to be sharp for $$r$$ for which there exists a projective plane of order $$r-1$$ . We show that the conjecture, if true, is also sharp for the smallest previously open value, namely $$r=7$$ . For $$r\in \{6,7\}$$ , we find the minimal number $$f(r)$$ of edges in an intersecting $$r$$ -partite hypergraph that has covering number at least $$r-1$$ . We find that $$f(r)$$ is achieved only by linear hypergraphs for $$r\le 5$$ , but that this is not the case for $$r\in \{6,7\}$$ . We also improve the general lower bound on $$f(r)$$ , showing that $$f(r)\ge 3.052r+O(1)$$ . We show that a stronger form of Ryser's conjecture that was used to prove the $$r=3$$ case fails for all $$r>3$$ . We also prove a fractional version of the following stronger form of Ryser's conjecture: in an $$r$$ -partite hypergraph there exists a set $$S$$ of size at most $$r-1$$ , contained either in one side of the hypergraph or in an edge, whose removal reduces the matching number by 1.
- Subjects
HYPERGRAPHS; GRAPH theory; LOGICAL prediction; NUMBER theory; SET theory; MATHEMATICAL bounds
- Publication
Graphs & Combinatorics, 2016, Vol 32, Issue 1, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-015-1575-9