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.
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 HU = (U, EU) where . Then H is called balanced iff HU 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: (v1, e1, v2, e2, ..., vk, ek, vk+1=v1), where every vertex vi is contained in both ei−1 and ei. 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
Some theorems on bipartite graphs have been generalized to balanced hypergraphs. [4] [2] : 468–470
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]
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.
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]
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.
In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.
In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).
In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.
In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.
Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.
In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.
In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.
In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.
In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.
Deficiency is a concept in graph theory that is used to refine various theorems related to perfect matching in graphs, such as Hall's marriage theorem. This was first studied by Øystein Ore. A related property is surplus.
In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.
In geometry, a truncated projective plane (TPP), also known as a dual affine plane, is a special kind of a hypergraph or geometric configuration that is constructed in the following way.
In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.