Bipartite bihypergraphs: a survey and new results (Q2495517)

Given two hypergraphs \(\mathcal F\) and \(\mathcal G\) on the underlying set \(X\) is called bipartite if there is a partition \(X= X_f \uplus X_g\) such that \(F\cap X_f\neq \emptyset\) for all \(F \in {\mathcal F}\) and \(G\cap X_g\neq \emptyset\) for all \(G \in {\mathcal G}\). (This property is also known as Property \(S\) or generalized Property \(B\). The second name came from the fact that if \(\mathcal F = \mathcal G\) and the pair forms a bipartite pair then the hypergraph \(\mathcal F\) satisfies Property \(B\).) The decision problem to decide whether two given hypergraphs form a bipartite pair is NP-complete. This paper surveys several related problems.