On a criterion for matchability in hypergraphs (Q687713): Difference between revisions

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\).