校级学术报告
报告题目：Matchings in balanced hypergraphs
报告人： Professor Eberhand Triesch
（德国亚琛工业大学（RWTH Aachen University）数学系）
时间：2012年9月21号（周五）下午3:00-4:00
地点：华东师大闵行校区数学系102报告厅

Abstrast:

In 1970, C.Berger introduced the notation 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 Konig’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 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$ satisfies 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 analogue of Hall’s theorem mentioned above (joint work with R. Scheidweiler).