Perfect matchings in balanced hypergraphs---a combinatorial approach
It is possible to generalize the celebrated Hall theorem on perfect matchings of bipartite graphs. The first step of the generalization of bipartite graphs was made by \textit{C. Berge} [Coll. Math. Soc. János Bolyai 4, 119-133 (1970; Zbl 0205.54501)]: a hypergraph is balanced if each odd cycle of it has an edge containing at least three vertices of that cycle. With that \textit{M. Conforti, G. Cornuéjols, A. Kapoor} and \textit{K. Vuskovic} [Combinatorica 16, 325-329 (1996; Zbl 0864.05074)] showed that a balanced hypergraph \(G\) contains perfect matching if and only if for any disjoint sets \(A\) and \(B\) of vertices with \(|A|> |B|\), there is an edge in \(G\) containing more vertices in \(A\) than in \(B\). For graphs it reduces to the Hall condition. The authors here give a combinatorial proof of this result, while the original one is based on linear programming.
scientific article; zbMATH DE number 1912034