Perfect matchings in balanced hypergraphs---a combinatorial approach (Q1872893)

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.