Bipartite hypergraph

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

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 fo 2-colorability was first introduced by Felix Bernstein in the context of set families;[1] therefore it is also called Property B.

Exact 2-colorability

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.[2][3]

To see that this sense 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 exactly-2-colorable, 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.

Every bipartite graph G = (X+Y, E) is exactly-2-colorable.

Hall's marriage theorem has been generalized from bipartite graphs to exactly-2-colorable hypergraphs; see Hall-type theorems for hypergraphs.

n-partiteness and rainbow-colorability

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. [4] An alternative term is rainbow-colorable.[5]

To see that n-partiteness is stronger than exact-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} }

This H is 3-uniform. It is exactly-2-colorable 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.

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.

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, 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber., 60: 325–328.

[:1-2] 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.

[3] 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, ISBN 978-1-61197-433-1

[4] 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.

[5] 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.