Projects per year
Abstract
A famous conjecture of Ryser (1967) 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 ∈ {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 ≤ 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 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.
Original language | English |
---|---|
Pages (from-to) | 1-15 |
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