数学科学学院 math

Prof.Eberhard Triesch,Lehrstuhl II fuer Mathematik RWTH Aachen, Germany

Matchings in balanced hypergraphs

In 1970, C.Berge introduced the notion of a balanced hypergraph in order to generalize bipartite graphs. Balanced hypergraphs are defined as hypergraphs without a (certain type of) odd cycles and share indeed many properties of bipartite graphs, e.g. the analogues of K?nig's Theorem hold. In 1996, Conforti et al. proved an analogue of Hall's Theorem in balanced hypergraphs which can be stated as follows: We say that a hypergraph H satisfies the Hall property if the following condition holds: If a subset of the vertices of H is coloured red and blue and if there are more red than blue vertices in total, then there is a hyperedge which contains more red than blue vertices.
Theorem(Conforti et al, 1996): H satiefies the Hall property if and only if it has a perfect matching, i.e., the vertex set can be partitioned by some hyperedges.
In the talk, we discuss a recent combinatorial approach to understand the structure of matchings in balanced hypergraphs by developing an analogue of the Gallai-Edmonds decomposition for graphs. This yields a new proof of the analogue of Hall's theorem mentioned above (joint work with R.Scheidweiler).