On a criterion for matchability in hypergraphs
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\).
- Matchings in n-partite n-graphs
- A condition for matchability in hypergraphs
- Maximum size of a graph with given fractional matching number
- Matching orderable and separable hypergraphs
- Matching critical intersection hypergraphs
- A linear programming perspective on the Frankl?R�dl?Pippenger theorem
- A generalization of Hall's theorem for \(k\)-uniform \(k\)-partite hypergraphs
- A geometric theory for hypergraph matching
- Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
- On the fractional matching polytope of a hypergraph
- On a possible extension of Hall's theorem to bipartite hypergraphs
This page was built for publication: On a criterion for matchability in hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687713)
