(2012.9.11 TUE 10:00am S712)Prof.Eberhard Triesch:Matchings in balanced hypergraphs

  • lyshen@gucas.ac.cn
  • Created: 2012-09-07

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

Inviter:闫桂英 研究员

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.
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).