Paul Brooks
Ryser's Conjecture and Special Cases

Abstract. A matching of a graph G is a subset of edges such that no two edges share a vertex. A cover C is a set of vertices such that every edge has at least one vertex in C. König's theorem states that for bipartite graphs (graphs with no odd cycles) the size of a maximum matching is equal to the size of a minimum cover. Ryser's conjecture concerns an extension of the theorem to r-uniform r-partite hypergraphs. Matching and covering are presented from a mathematical programming point of view, Ryser's conjecture is presented, and special cases are discussed.