Perfect matchings in balanced hypergraphs (Q2563509)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 958129
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Perfect matchings in balanced hypergraphs |
scientific article; zbMATH DE number 958129 |
Statements
Perfect matchings in balanced hypergraphs (English)
0 references
23 January 1997
0 references
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\).
0 references
theorem of Hall
0 references
balanced hypergraph
0 references
perfect matching
0 references
0.9379717111587524
0 references
0.842262864112854
0 references
0.8293733596801758
0 references
0.8253271579742432
0 references
