Perfect matchings in balanced hypergraphs

DOI10.1007/BF01261318MaRDI QIDQ2563509zbMATH OpenFDO

Authors Michele Conforti, Ajai Kapoor, Kristina Vušković, Gérard Cornuéjols

Publication date 23 January 1997

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01261318

zbMATH Keywords

balanced hypergraphperfect matchingtheorem of Hall

Mathematics Subject Classification ID

Partitions of sets (05A18) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A hypergraph \(H(V,E)\) is balanced if every odd cycle \(C\) of \(H\) has an edge containing at least three nodes of \(C\). The main result of the present paper is the following generalization of a theorem of Hall: A balanced hypergraph \(H(V,E)\) has no perfect matching if and only if there exist disjoint node sets \(R\) and \(B\) such that \(|B|>|R|\) and every edge contains at least as many nodes in \(R\) as in \(B\).

Recommendations

• Perfect matchings in balanced hypergraphs---a combinatorial approach
• A condition for matchability in hypergraphs
• Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs
• A generalization of Hall's theorem for \(k\)-uniform \(k\)-partite hypergraphs

Cites work

• Balanced \(0,\pm 1\)-matrices, bicoloring and total dual integrality
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 3363617 (Why is no real title available?)
• On Representatives of Subsets

Cited in

(14)

• A characterization of totally balanced hypergraphs
• Decomposition of balanced matrices
• Hall's and Kőnig's theorem in graphs and hypergraphs
• \(d\)-matching in 3-uniform hypergraphs
• Perfect matchings in balanced hypergraphs---a combinatorial approach
• A condition for matchability in hypergraphs
• Perfect \(f\)-matchings and \(f\)-factors in hypergraphs -- a combinatorial approach
• Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs
• Existence of a maximum balanced matching in the hypercube
• Balanced matrices
• Binary set systems and totally balanced hypergraphs
• A note on the duality between matchings and vertex covers in balanced hypergraphs
• A hyperedge coloring and application in combinatorial testing
• Perfect, ideal and balanced matrices

This page was built for publication: Perfect matchings in balanced hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2563509)