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. (Primary Chief Investigator (PCI)), Greenhill, C. (Chief Investigator (CI)) & Aharoni, R. (Partner Investigator (PI))
ARC - Australian Research Council, University of New South Wales (UNSW)
3/01/12 → 31/12/14
Project: Research