Projects per year
Abstract
Ryser conjectured that τ ⩽ (r − 1)ν for rpartite hypergraphs, where τ is the covering number and ν is the matching number. We prove this conjecture for r ⩽ 9 in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex.
Aharoni formulated a stronger version of Ryser's conjecture which specified that each rpartite hypergraph should have a cover of size (r−1)ν of a particular form. We provide a counterexample to Aharoni's conjecture with r=13 and ν=1.
We also report a number of computational results. For r=7, we find that there is no linear intersecting hypergraph that achieves the equality τ = r−1 in Ryser's conjecture, although nonlinear examples are known. We exhibit intersecting nonlinear examples achieving equality for r ∈ {9,13,17}. Also, we find that r = 8 is the smallest value of r for which there exists a linear intersecting rpartite hypergraph that achieves τ = r−1 and is not isomorphic to a subhypergraph of a projective plane.
Original language  English 

Pages (fromto)  91105 
Number of pages  15 
Journal  European Journal of Combinatorics 
Volume  61 
DOIs  
Publication status  Published  1 Mar 2017 
Projects
 2 Finished

Matchings in Combinatorial Structures
Wanless, I., Bryant, D. & Horsley, D.
Australian Research Council (ARC), Monash University, University of Queensland , University of Melbourne
1/01/15 → 10/10/20
Project: Research

Extremal Problems in Hypergraph Matchings
Wanless, I., Greenhill, C. & Aharoni, R.
Australian Research Council (ARC), University of New South Wales
3/01/12 → 31/12/14
Project: Research