In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.
Property B and 2-colorability
Main article: Property BThe weakest definition of bipartiteness is also called 2-colorability. A hypergraph H = (V, E) is called 2-colorable if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge meets both X and Y. Equivalently, the vertices of H can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph G = (X+Y, E) is 2-colorable: each edge contains exactly one vertex of X and one vertex of Y, so e.g. X can be colored blue and Y can be colored yellow and no edge is monochromatic.
The property of 2-colorability was first introduced by Felix Bernstein in the context of set families; therefore it is also called Property B.
Exact 2-colorability
A stronger definition of bipartiteness is: a hypergraph is called bipartite if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge contains exactly one element of X. Every bipartite graph is also a bipartite hypergraph.
Every bipartite hypergraph is 2-colorable, but bipartiteness is stronger than 2-colorability. Let H be a hypergraph on the vertices {1, 2, 3, 4} with the following hyperedges:
{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }
This H is 2-colorable, for example by the partition X = {1,2} and Y = {3,4}. However, it is not bipartite, since every set X with one element has an empty intersection with one hyperedge, and every set X with two or more elements has an intersection of size 2 or more with at least two hyperedges.
Hall's marriage theorem has been generalized from bipartite graphs to bipartite hypergraphs; see Hall-type theorems for hypergraphs.
n-partiteness and rainbow-colorability
A stronger definition is: given an integer n, a hypergraph is called n-uniform if all its hyperedges contain exactly n vertices. An n-uniform hypergraph is called n-partite if its vertex set V can be partitioned into n subsets such that each hyperedge contains exactly one element from each subset. An alternative term is rainbow-colorable.
Every n-partiteness hypergraph is bipartite, but n-partiteness is stronger than bipartiteness. Let H be a hypergraph on the vertices {1, 2, 3, 4} with the following hyperedges;
{ {1,2,3} , {1,2,4} , {1,3,4} }
This H is 3-uniform. It is bipartite by the partition X = {1} and Y = {2,3,4}. However, it is not 3-partite: in every partition of V into 3 subsets, at least one subset contains two vertices, and thus at least one hyperedge contains two vertices from this subset.
A 3-partite hypergraph is often called "tripartite hypergraph". However, a 2-partite hypergraph is not the same as a bipartite hypergraph; it is equivalent to a bipartite graph.
Comparison with other notions of bipartiteness
There are other natural generalizations of bipartite graphs. A hypergraph is called balanced if it is essentially 2-colorable, and remains essentially 2-colorable upon deleting any number of vertices (see Balanced hypergraph).
The properties of bipartiteness and balance do not imply each other.
Bipartiteness does not imply balance. For example, let H be the hypergraph with vertices {1,2,3,4} and edges:
{ {1,2,3} , {1,2,4} , {1,3,4} }
It is bipartite by the partition X={1}, Y={2,3,4}. But is not balanced. For example, if vertex 1 is removed, we get the restriction of H to {2,3,4}, which has the following hyperedges;
{ {2,3} , {2,4} , {3,4} }
It is not 2-colorable, since in any 2-coloring there are at least two vertices with the same color, and thus at least one of the hyperedges is monochromatic.
Another way to see that H is not balanced is that it contains the odd-length cycle C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), and no edge of C contains all three vertices 2,3,4 of C.
Balance does not imply bipartiteness. Let H be the hypergraph:
{ {1,2} , {3,4} , {1,2,3,4} }
it is 2-colorable and remains 2-colorable upon removing any number of vertices from it. However, it is not bipartite, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.
See also
References
- Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber., 60: 325–328.
- Aharoni, Ron; Kessler, Ofra (1990-10-15). "On a possible extension of Hall's theorem to bipartite hypergraphs". Discrete Mathematics. 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.
- Annamalai, Chidambaram (2015-12-21), "Finding Perfect Matchings in Bipartite Hypergraphs", Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 1814–1823, doi:10.1137/1.9781611974331.ch126, hdl:20.500.11850/224679, ISBN 978-1-61197-433-1
- Aharoni, Ron (1985-12-01). "Matchings inn-partiten-graphs". Graphs and Combinatorics. 1 (1): 303–304. doi:10.1007/BF02582958. ISSN 1435-5914. S2CID 19258298.
- Guruswami, Venkatesan; Lee, Euiwoong (2018-06-01). "Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs". Combinatorica. 38 (3): 547–599. doi:10.1007/s00493-016-3383-0. ISSN 1439-6912. S2CID 53566425.