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 ^[1] 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. ^{[2] : 468}

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 ${\displaystyle 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₁), 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. ^[3]

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 ^[1] proved that the two definitions are equivalent; a proof is also available here. ^{[2] : 468–469}

Properties

Some theorems on bipartite graphs have been generalized to balanced hypergraphs. ^{[4] [2] : 468–470}

• 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). ^[5] This generalizes a theorem of Konig on bipartite graphs.
• Every balanced hypergraph satisfies a generalization of Hall's marriage theorem: ^[3] it admits a perfect matching iff for all disjoint vertex-sets V₁, V₂, if ${\displaystyle |e\cap V_{2}|\geq |e\cap V_{1}|}$ for all edges e in E, then |V₂| ≥ |V₁|. See Hall-type theorems for hypergraphs.
• Every balanced hypergraph with maximum degree D, can be partitioned into D edge-disjoint matchings. ^{[1] : Chapter 5  [3] : Corollary 3}

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. ^[6]

Comparison with other notions of bipartiteness

Besides balance, there are alternative generalizations of bipartite graphs. 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 (see bipartite hypergraph). Obviously every bipartite graph is 2-colorable.

The properties of bipartiteness and balance do not imply each other.

Balance does not imply bipartiteness. Let H be the hypergraph: ^[7]

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

Related properties

Totally balanced hypergraphs

A hypergraph is called totally balanced if every cycle C in H of length at least 3 (not necessarily odd-length) has an edge containing at least three vertices of C. ^[8]

A hypergraph H is totally balanced iff every subhypergraph of H is a tree-hypergraph. ^[8]

Normal hypergraphs

The Konig property of a hypergraph H is the property that its minimum vertex-cover has the same size as its maximum matching. The Kőnig-Egervary theorem says that all bipartite graphs have the Konig property.

The balanced hypergraphs are exactly the hypergraphs H such that every partial subhypergraph of H has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges and vertices).

If every partial hypergraph of H has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges - but not vertices), then H is called a normal hypergraph. ^[9]

Thus, totally-balanced implies balanced, which implies normal.

References

1. Berge, Claude (1970). "Sur certains hypergraphes généralisant les graphes bipartites". Combinatorial Theory and Its Applications. 1: 119–133.
2. Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN   0-444-87916-1, MR   0859549
3. Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). "Perfect matchings in balanced hypergraphs". Combinatorica. 16 (3): 325–329. doi:10.1007/BF01261318. ISSN   1439-6912. S2CID   206792822.
4. Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences. 175 (1): 32–40. doi:10.1111/j.1749-6632.1970.tb56451.x. ISSN   1749-6632. S2CID   84670737.
5. Lovász, L. (1972-06-01). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics. 2 (3): 253–267. doi:10.1016/0012-365X(72)90006-4. ISSN   0012-365X.
6. Dahlhaus, Elias; Kratochvíl, Jan; Manuel, Paul D.; Miller, Mirka (1997-11-27). "Transversal partitioning in balanced hypergraphs". Discrete Applied Mathematics. 79 (1): 75–89. doi:10.1016/S0166-218X(97)00034-6. ISSN   0166-218X.
7. "coloring - Which generalization of bipartite graphs is stronger?". Mathematics Stack Exchange. Retrieved 2020-06-27.
8. Lehel, Jenö (1985-11-01). "A characterization of totally balanced hypergraphs". Discrete Mathematics. 57 (1): 59–65. doi: 10.1016/0012-365X(85)90156-6 . ISSN   0012-365X.
9. Beckenbach, Isabel; Borndörfer, Ralf (2018-10-01). "Hall's and Kőnig's theorem in graphs and hypergraphs". Discrete Mathematics. 341 (10): 2753–2761. doi:10.1016/j.disc.2018.06.013. ISSN   0012-365X. S2CID   52067804.