On a criterion for matchability in hypergraphs
type: Item
instance of: scholarly article
title: On a criterion for matchability in hypergraphs
zbMATH Open document ID: 0781.05035
DOI: 10.1007/BF02988309
author: Ron Aharoni
published in: Graphs and Combinatorics
publication date: 1993-10-28T00:00:00Z
review text: A hypergraph \(H=(V,E)\) is bipartite, if there is some partition \(V=A \cup B\) of its vertex set such that every edge contains exactly one element of \(A\). It is called \(n\)-uniform if every edge contains exactly \(n\) vertices. For \(C \subseteq A\), let \(H_ C\) denote the hypergraph with \(B\) as vertex set, and an \((n-1)\)-element subset \(e\) of \(B\) forming an edge in \(H_ C\) if \(e \cup \{a\} \in E\) for some \(a \in A\). The matching number \(\nu(H)\) is the maximal size of a set of pairwise disjoint edges of \(H\). The fractional matching number \(\nu^*(H)\) is the maximum of \(\sum_{e\in E}f(e)\), over all mappings \(f:E\to\mathbb{R}^ +\) with \(\sum_{v\in e}f(e)\leq 1\) for every vertex \(v\in V\). Surely \(\nu(H) \leq \nu^*(H)\leq | A |\). The following sufficient condition for equality of \(\nu^*(H)\) and \(| A|\) is the main result of the paper: If \(H=(A\cup B,E)\) is a bipartite \(n\)-uniform hypergraph obeying \(\nu^*(H_ C)>(n-1)(| C |-1)\) for every \(C \subseteq A\), then \(\nu^*(H)=| A|\). The author conjectures that \(\nu^*\) could be replaced by \(\nu\) in the conclusion of the above theorem, and proves this conjecture for \(| A|=2\).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 436557
zbMATH Keywords: matchability
zbMATH Keywords: hypergraph
zbMATH Keywords: fractional matching number
reviewed by: Erich Prisner
MaRDI profile type: Publication
cites work: Matchings in n-partite n-graphs
cites work: On a possible extension of Hall's theorem to bipartite hypergraphs
description: scientific article; zbMATH DE number 436557