Bipartite hypergraph

Last updated

In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.

Contents

Property B and 2-colorability

The weakest definition of bipartiteness is also called 2-colorability. A hypergraph H = (V, E) is called 2-colorable if its vertex set V can be partitioned into two sets, X and Y, such that each hyperedge meets both X and Y. Equivalently, the vertices of H 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.

The property of 2-colorability was first introduced by Felix Bernstein in the context of set families; [1] therefore it is also called Property B.

Exact 2-colorability

A stronger definition of bipartiteness is: 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. [2] [3] Every bipartite graph is also a bipartite hypergraph.

Every bipartite hypergraph is 2-colorable, but bipartiteness is stronger than 2-colorability. Let H be a hypergraph on the vertices {1, 2, 3, 4} with the following hyperedges:

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

This H is 2-colorable, for example by the partition X = {1,2} and Y = {3,4}. However, it is not bipartite, since every set X with one element has an empty intersection with one hyperedge, and every set X with two or more elements has an intersection of size 2 or more with at least two hyperedges.

Hall's marriage theorem has been generalized from bipartite graphs to bipartite hypergraphs; see Hall-type theorems for hypergraphs.

n-partiteness and rainbow-colorability

A stronger definition is: given an integer n, a hypergraph is called n-uniform if all its hyperedges contain exactly n vertices. An n-uniform hypergraph is called n-partite if its vertex set V can be partitioned into n subsets such that each hyperedge contains exactly one element from each subset. [4] An alternative term is rainbow-colorable. [5]

Every n-partiteness hypergraph is bipartite, but n-partiteness is stronger than bipartiteness. Let H be a hypergraph on the vertices {1, 2, 3, 4} with the following hyperedges;

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

This H is 3-uniform. It is bipartite by the partition X = {1} and Y = {2,3,4}. However, it is not 3-partite: in every partition of V into 3 subsets, at least one subset contains two vertices, and thus at least one hyperedge contains two vertices from this subset.

A 3-partite hypergraph is often called "tripartite hypergraph". However, a 2-partite hypergraph is not the same as a bipartite hypergraph; it is equivalent to a bipartite graph.

Comparison with other notions of bipartiteness

There are other natural generalizations of bipartite graphs. A hypergraph is called balanced if it is essentially 2-colorable, and remains essentially 2-colorable upon deleting any number of vertices (see Balanced hypergraph).

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

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.

Balance does not imply bipartiteness. Let H be the hypergraph:[ citation needed ]

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

See also

Related Research Articles

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

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:

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

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.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

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.

<span class="mw-page-title-main">Clique complex</span> Abstract simplicial complex describing a graphs cliques

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.

<span class="mw-page-title-main">3-dimensional matching</span>

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices.

<span class="mw-page-title-main">Baranyai's theorem</span> Theorem that deals with the decompositions of complete hypergraphs

In combinatorial mathematics, Baranyai's theorem deals with the decompositions of complete hypergraphs.

<span class="mw-page-title-main">Skew partition</span>

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

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, the hypergraph removal lemma states that when a hypergraph contains few copies of a given sub-hypergraph, then all of the copies can be eliminated by removing a small number of hyperedges. It is a generalization of the graph removal lemma. The special case in which the graph is a tetrahedron is known as the tetrahedron removal lemma. It was first proved by Nagle, Rödl, Schacht and Skokan and, independently, by Gowers.

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 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 balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

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, perfect matching in high-degree hypergraphs is a research avenue trying to find sufficient conditions for existence of a perfect matching in a hypergraph, based only on the degree of vertices or subsets of them.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

In mathematics, the hypergraph regularity method is a powerful tool in extremal graph theory that refers to the combined application of the hypergraph regularity lemma and the associated counting lemma. It is a generalization of the graph regularity method, which refers to the use of Szemerédi's regularity and counting lemmas.

References

  1. ↑ Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber., 60: 325–328.
  2. ↑ Aharoni, Ron; Kessler, Ofra (1990-10-15). "On a possible extension of Hall's theorem to bipartite hypergraphs". Discrete Mathematics. 84 (3): 309–313. doi: 10.1016/0012-365X(90)90136-6 . ISSN   0012-365X.
  3. ↑ Annamalai, Chidambaram (2015-12-21), "Finding Perfect Matchings in Bipartite Hypergraphs", Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 1814–1823, doi: 10.1137/1.9781611974331.ch126 , hdl: 20.500.11850/224679 , ISBN   978-1-61197-433-1
  4. ↑ Aharoni, Ron (1985-12-01). "Matchings inn-partiten-graphs". Graphs and Combinatorics. 1 (1): 303–304. doi:10.1007/BF02582958. ISSN   1435-5914. S2CID   19258298.
  5. ↑ Guruswami, Venkatesan; Lee, Euiwoong (2018-06-01). "Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs". Combinatorica. 38 (3): 547–599. doi:10.1007/s00493-016-3383-0. ISSN   1439-6912. S2CID   53566425.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.