Balanced hypergraph

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph. Balanced hypergraphs were introduced by Berge as a natural generalization of bipartite graphs. He provided two equivalent definitions.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph. Balanced hypergraphs were introduced by Berge as a natural generalization of bipartite graphs. He provided two equivalent definitions. A hypergraph H = (V, E) is called 2-colorable if its vertices 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. A hypergraph in which some hyperedges are singletons (contain only one vertex) is obviously not 2-colorable; to avoid such trivial obstacles to 2-colorability, it is common to consider hypergraphs that are essentially 2-colorable, i.e., they become 2-colorable upon deleting all their singleton hyperedges. A hypergraph is called balanced if it is essentially 2-colorable, and remains essentially 2-colorable upon deleting any number of vertices. Formally, for each subset U of V, define the restriction of H to U as the hypergraph H U = (U, E U ) where E_U = \{e\cap U | e\in E\} . Then H is called balanced iff H U is essentially 2-colorable for every subset U of V. Note that a simple graph is bipartite iff it is 2-colorable iff it is balanced. A cycle (or a circuit) in a hypergraph is a cyclic alternating sequence of distinct vertices and hyperedges: (v 1 , e 1 , v 2 , e 2 , ..., v k , e k , v k +1 =v 1 ), where every vertex v i is contained in both e i −1 and e i . The number k is called the length of the cycle. A hypergraph is balanced iff every odd-length cycle C in H has an edge containing at least three vertices of C. Note that in a simple graph all edges contain only two vertices. Hence, a simple graph is balanced iff it contains no odd-length cycles at all, which holds iff it is bipartite. Berge proved that the two definitions are equivalent; a proof is also available here. In every balanced hypergraph, the degree (= the maximum number of hyperedges containing some one vertex) equals the chromatic index (= the least number of colors required for coloring the hyperedges such that no two hyperedges with the same color have a vertex in common). This generalizes a theorem of Konig on bipartite graphs. Every balanced hypergraph satisfies a generalization of Hall's marriage theorem: it admits a perfect matching iff for all disjoint vertex-sets V 1 , V 2 , if |e\cap V_2| \geq |e\cap V_1| for all edges e in E, then |V 2 | ≥ |V 1 |. See Hall-type theorems for hypergraphs. Every balanced hypergraph with maximum degree D, can be partitioned into D edge-disjoint matchings. A k-fold transversal of a balanced hypergraph can be expressed as a union of k pairwise-disjoint transversals, and such partition can be obtained in polynomial time. 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. Tripartiteness does not imply balance. For example, let H be the tripartite hypergraph with vertices {1,2},{3,4},{5,6} and edges: { {1,3,5}, {2,4,5}, {1,4,6} } It is not balanced since if we remove the vertices 2,3,6, the remainder is: { {1,5}, {4,5}, {1,4} } which is not colorable since it is a 3-cycle. Another way to see that it is not balanced is that It contains the odd-length cycle C = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1), and no edge of C contains all three vertices 1,4,5 of C.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1276470915 under CC BY-SA 4.0; modifications have been made.