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.

Definition by 2-colorability

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.

Definition by odd cycles

A cycle (or a circuit) in a hypergraph is an cyclic alternating sequence of vertices and hyperedges: (v₁, e₁, v₂, e₂, ..., v_k, e_k, v_k+1=v₁).

A hypergraph is called balanced iff it does not contain an unbalanced odd-length circuit just like a simple graph is bipartite iff it does not contain an odd-length cycle).

Other notions of bipartiteness

The see that this sense is stonger than 2-colorability, let H be the hypergraph with vertices {1,2,3,4} and edges:

{ {1,2,3} , {1,2,4} , {1,3,4} }

It is 2-colorable (it is even exactly-2-colorable), but it 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. The above example shows that exact 2-colorability does not imply balancedness; to see that balancedness does not imply exact-2-colorability either, 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 exactly 2-colorable, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.

Some theorems on bipartite graphs have been generalized to balanced hypergraphs.

• A hypergraph is balanced iff it does not contain an unbalanced odd-length circuit just like a simple graph is bipartite iff it does not contain an odd-length cycle).
• In every balanced hypergraph, the minimum vertex-cover has the same size as its maximum matching. This generalizes the Kőnig-Egervary theorem on bipartite graphs.
• 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.

See also

• Bipartite hypergraph - an alternative generalization of a bipartite graph.