Projects per year
Abstract
A famous conjecture of Ryser (1967) is that in an rpartite 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 ∈ {6, 7}, we find the minimal number f(r) of edges in an intersecting rpartite hypergraph that has covering number at least r  1. We find that f(r) is achieved only by linear hypergraphs for r ≤ 5, but that this is not the case for r ∈ {6, 7}. We also improve the general lower bound on f(r), showing that f(r) ≥ 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 rpartite 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.
Original language  English 

Pages (fromto)  115 
Number of pages  15 
Journal  Graphs and Combinatorics 
Volume  32 
Issue number  1 
DOIs  
Publication status  Published  2016 
Keywords
 Covering number
 Fractional cover
 Intersecting hypergraph
 Ryser’s conjecture
Projects
 1 Finished

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