Abu-Khazneh, Ahmad
(2016)
Matchings and covers of multipartite hypergraphs.
PhD thesis, London School of Economics and Political Science.
Abstract
Koenig’s theorem is a classic result in combinatorics which states that for every bipartite graph G, the cover number of G (denoted by τ (G)) is equal to its matching number (denoted by ν(G)). The theorem’s importance stems from its many applications in various areas of mathematics, such as optimisation theory and algorithmic analysis.
Ryser’s Conjecture for multipartite hypergraphs is a proposed generalisation of Koenig’s theorem made in the 1970s. It asserts that for every r-partite hypergraph H, we have the following inequality: τ (H) ≤ (r − 1)ν(H). The conjecture is only known to be true for tripartite hypergraphs and a few other special cases.
In the first part of this thesis, we present algorithms that – for a given r – are able to prove or disprove the conjecture in the case of r-partite intersecting hypergraphs. Moreover, for a given r, the algorithms can also be used to enumerate all r-partite extremal hypergraphs to Ryser’s Conjecture. Extremal hypergraphs are r-partite hypergraphs for which the cover number is exactly r − 1 times the matching number.
The second part of this thesis focuses on the case of 4-partite hypergraphs. It is motivated by a recent result on Ryser’s Conjecture for tripartite hypergraphs. The result classifies all tripartite extremal hypergraphs, and implies that if H is a tripartite extremal hypergraph, then it must contain ν(H) vertex-disjoint tripartite intersecting extremal hypergraphs.
This result leads to the natural question of whether a similar characterisation of r-partite extremal hypergraphs is possible for other values of r? In particular, for the first open case of Ryser’s Conjecture, the case of r = 4.
We shed some light on this question, by first classifying all 4-partite intersecting extremal hypergraphs. We then present a list of 4-partite extremal hypergraphs with matching number equal to two, such that none of them contain two vertex-disjoint 4-partite extremal hypergraphs.
Our result shows that a straightforward characterisation of 4-partite extremal hypergraphs is not possible in terms of vertex-disjoint intersecting extremal hypergraphs. However, we still conjecture an analogue to the classification of tripartite extremal hypergraphs, which is not contradicted by our extremal examples.
In the final part of the thesis we focus on intersecting extremal hypergraphs to Ryser’s Conjecture. Apart from a few sporadic constructions in the literature, there is only one known family of r-partite extremal hypergraphs, which comes from finite projective planes. The family contains an r-partite extremal hypergraph to Ryser’s Conjecture, whenever a finite projective plane of order r − 1 exists.
Our contribution is to first calculates bounds on the sparsest possible extremal hypergraphs for small values of r. We then prove the existence of a new family of extremal hypergraphs to Ryser’s Conjecture.
The new family contains an r-partite intersecting extremal hypergraph to Ryser’s Conjecture, whenever a finite projective plane of order r − 2 exists. Moreover we are able to show via a number theoretic argument, that there are infinitely many cases for which our new family contains an extremal hypergraph, when the currently known family of extremal hypergraphs is known not to contain one.
Actions (login required)
 |
Record administration - authorised staff only |
Download statistics
Download statistics