Perfect matchings in balanced hypergraphs---a combinatorial approach
type: Item
instance of: scholarly article
title: Perfect matchings in balanced hypergraphs---a combinatorial approach
zbMATH Open document ID: 1012.05118
author: Andreas Huck
author: Eberhard Triesch
published in: Combinatorica
publication date: 2003-05-18T00:00:00Z
review text: 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.
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1912034
zbMATH Keywords: Hall condition
zbMATH Keywords: perfect
zbMATH Keywords: matching
zbMATH Keywords: hypergraph
MaRDI profile type: Publication
full work available at URL: s004930200020
OpenAlex ID: W1978371952
DOI: 10.1007/S004930200020
description: scientific article; zbMATH DE number 1912034