Matchings in balanced hypergraphs
Robert Scheidweiler, Eberhard Triesch · 2011
The present work deals with the matching and vertex cover problem in balanced hypergraphs. This class of hypergraphs is, according to the definition by Berge in the 70s, one possible generalization of bipartite graphs. In the first chapter we define basic notions about graphs and hypergraphs. The next chapter deals with the class of balanced hypergraphs. At first we state some known coloring properties of balanced hypergraphs and investigate the matching problem in two important subclasses. Then we analyse the connection between regularity and maximum matchings. After that we give a new proof of König's Theorem for balanced hypergraphs and discuss further duality properties between matchings and vertex covers and give several new results, which can be interpreted as combinatorial formulations and strengthenings of the complementary slackness relation. In the following we investigate the associated polyhedra and outline how our ideas can be used to augment matchings algorithmically. The third chapter deals with the main results of this work - a new decomposition theory for balanced hypergraphs. We generalize the classical Gallai Edmonds decomposition of graphs to balanced hypergraphs in several different ways. Based on these decompositions we give a new, short, and combinatorial proof of Hall's theorem in balanced hypergraphs in chapter four. In the last chapter we show several applications of our theory, e.g., we give several new characterizations of balanced hypergraphs, characterize 1-extendability, and investigate several interesting subclasses.