Prof.Eberhard Triesch,Lehrstuhl II fuer Mathematik RWTH Aachen, Germany
Matchings in balanced hypergraphs
Time & Venue:
|2012.9.11 TUE 10:00am S712(思源楼)|
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.