Doug Altner

Coverings and Matchings in r-Partite Hypergraphs

Abstract. In this talk, we give an overview of our proofs of a few results pertaining to matchings and coverings in r-partite intersecting hypergraph. First, we give an overview of our proof that the ratio between the cardinality of the maximum fractional r-partite matching and the maximum r-partite matching is at least rk where k is the smallest positive integer such that rk is a prime power. This is an alternate proof of a known result. Second, we give an overview of our proof that finding a minimum vertex cover on an r-partite intersecting hypergraph is NP-hard. The last part of this talk concerns Ryser's conjecture, a long-standing conjecture that postulates τ (r – 1) ≤ ν for any hypergraph where τ is the covering number and ν is the matching number. Ryser's conjecture is easily resolved for intersecting hypergraphs that do not contain a particular sub-hypergraph, which we call a tornado. We give an overview of our proofs of a few upper bounds on the covering number of tornados.

This is joint work with Paul Brooks of VCU.