What is a bipartite hypergraph?

Question

Bipartite graphs are very useful, and I am looking for a generalization of this concept to hypergraphs. I found two different definitions of bipartite hypergraphs:

1. In the Wikipedia page Hypergraph, a bipartite hypergraph is defined as a hypergraph whose vertices can be partitioned into two parts, $X$ and $Y$, such that each hyperedge of cardinality at least 2 contains at least one vertex from $X$ and one vertex from $Y$. It is equivalent to Property B or to 2-colorability.

2. Aharoni and Kessler (1990), and later Annamalai (2016), use the term bipartite hypergraph in a stronger sense: vertices can be partitioned into two parts, $X$ and $Y$, such that each hyperedge of cardinality at least 2 contains exactly one vertex from $X$, and all its other vertices are from $Y$.

What is the more standard meaning of this term today? And, is there an alternative term to the second (stronger) meaning, that I can use to differentiate it from the first (weaker) meaning?

Answer 1

Both (and more...) notions are used.

Coloring hypergraphs is annoying, and so we come up with silly names like “property B” and “rainbow” (to be fair, rainbow is a good name).

This also comes up for independent sets. Is it a set containing no edges, a set that each edge meets at most once, or other?

The reason there’s no fixed standard is that there are a ton of naturally useful definitions, which unfortunately don’t coincide when edges have more than two elements. (I’ve heard it said, “the problem in coloring $k$-uniform hypergraphs is that $k-1$ doesn’t usually equal 1.”)

This gets worse. Even notions like “cycle” have oodles of possible meanings, and (again) all of them are studied.

In writing or reading a paper, you pick a notion that fits your situation, and go with that. You also (of course) explicitly say what notion you’re going with by telling the reader exactly what you mean by “bipartite” (or whatever).

#hypergraphsAreHard

Answer 2

As Pat Devin wrote there are many notions of "bipartite hypergraphs". There is a chapter about this topic in the Hypergraph book by Berge (it can be found online as a pdf, look at chapter 5) Berge, Claude, Hypergraphs. Combinatorics of finite sets. Transl. from the French, North-Holland Mathematical Library, 43. Amsterdam etc.: North-Holland. x, 255 p. {$} 79.00; Dfl. 150.00 (1989). ZBL0674.05001.

In my dissertation I studied different concepts of "bipartite hypergraphs" with a focus on matching and flow problems. It is also available online: Matchings and Flows in Hypergraphs.

One can look at the various equivalent definitions of bipartite graphs and than try to generalize them for hypergraphs. One property is the 2-colorability, but here, one demands that every subhypergraph is 2-colorable. Another possibility is to forbid certain kind of odd cycles (called strong odd cycles). Hypergraphs without strong odd cycles are than called balanced. It depends on the situation or application how one defines a "bipartite" hypergraph.