AbuKhazneh, 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 rpartite 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 rpartite intersecting hypergraphs. Moreover, for a given r, the algorithms can also be used to enumerate all rpartite extremal hypergraphs to Ryser’s Conjecture. Extremal hypergraphs are rpartite 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 4partite 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) vertexdisjoint tripartite intersecting extremal hypergraphs.
This result leads to the natural question of whether a similar characterisation of rpartite 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 4partite intersecting extremal hypergraphs. We then present a list of 4partite extremal hypergraphs with matching number equal to two, such that none of them contain two vertexdisjoint 4partite extremal hypergraphs.
Our result shows that a straightforward characterisation of 4partite extremal hypergraphs is not possible in terms of vertexdisjoint 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 rpartite extremal hypergraphs, which comes from finite projective planes. The family contains an rpartite 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 rpartite 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 