Width of a hypergraph

Last updated

In graph theory, there are two related properties of a hypergraph that are called its "width". Given a hypergraph H = (V, E), we say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K. [1] Then:

Contents

Since E contains all matchings in E, for all H: w(H) ≥ mw(H).

The width of a hypergraph is used in Hall-type theorems for hypergraphs.

Examples

Let H be the hypergraph with vertex set V = {A,B; a,b} and edge set:

E = { {A,a}, {B,b}, {A,b}, {B,a} }

The widths of H are:

Characterizations

The disjointness graph of H, denoted D(H), is a graph where each edge in H is a vertex in D(H), and every two disjoint edges in H are adjacent in D(H). The matchings in H correspond to the cliques in D(H). Meshulam [2] characterized the widths of a hypergraph H in terms of the properties of D(H). For any positive integer r:

The line graph of H, denoted L(H), is a graph where each edge in H is a vertex in L(H), and every two intersecting edges in H are adjacent in L(H). The matchings in H correspond to the independent sets in L(H). Since L(H) is the complement of D(H), the above characterization can be translated to L(H):

The domination number of a graph G, denoted γ(G), is the smallest size of a vertex set that dominates all vertices of G. The width of a hypergraph equals the domination number or its line-graph: w(H) = γ(L(H)). This is because the edges of E are the vertices of L(H): every subset of E that pins E in H corresponds to a vertex set in L(H) that dominates all L(H).

The independence domination number of a graph G, denoted iγ(G), is the maximum, over all independent sets A of G, of the smallest set dominating A. [4] The matching width of a hypergraph equals the independence domination number or its line-graph: mw(H) = iγ(L(H)). This is because every matching M in H corresponds to an independent set IM in L(H), and every subset of E that pins M in H corresponds to a set that dominates IM in L(H).

See also

Related Research Articles

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">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. The domination numberγ(G) is the number of vertices in a smallest dominating set for G.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

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.

<span class="mw-page-title-main">Factor-critical graph</span> Graph of n vertices with a perfect matching for every subgraph of n-1 vertices

In graph theory, a mathematical discipline, a factor-critical graph is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching.

In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraphH, denoted L(H), is the graph whose vertex set is the set of the hyperedges of H, with two vertices adjacent in L(H) when their corresponding hyperedges have a nonempty intersection in H. In other words, L(H) is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph.

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

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.

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.

The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) is indeed closed under taking subsets.

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

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index k such that all reduced homological groups up to and including k are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.

In graph theory, a d-interval hypergraph is a kind of a hypergraph constructed using intervals of real lines. The parameter d is a positive integer. The vertices of a d-interval hypergraph are the points of d disjoint lines. The edges of the graph are d-tuples of intervals, one interval in every real line.

References

  1. ↑ Aharoni, Ron; Haxell, Penny (2000). "Hall's theorem for hypergraphs". Journal of Graph Theory. 35 (2): 83–88. doi:10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN   1097-0118.
  2. 1 2 Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN   1439-6912. S2CID   207006642.
  3. ↑ Aharoni, Ron (2001-01-01). "Ryser's Conjecture for Tripartite 3-Graphs". Combinatorica. 21 (1): 1–4. doi:10.1007/s004930170001. ISSN   1439-6912. S2CID   13307018.
  4. ↑ Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN   1439-6912. S2CID   43510417.
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.