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 a cyclic alternating sequence of distinct vertices and hyperedges: (v₁, e₁, v₂, e₂, ..., v_k, e_k, v_k+1=v₁). The number k is 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 graph is balanced iff it contains no odd cycles at all, which holds iff it is bipartite.

Berge proved that the two definitions are equivalent; a proof is also available here.

Properties

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

• 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.
• Every balanced hypergraph satisfies a generalization of Hall's marriage theorem: it admits a perfect matching iff for all disjoint vertex-sets V₁, V₂, if $|e\cap V_{2}|\geq |e\cap V_{1}|$ for all edges e in E, then |V₂| ≥ |V₁|. See Hall-type theorems for hypergraphs.

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.

See also

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