Jump to content

Width of a hypergraph

From Wikipedia, the free encyclopedia

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:

  • The width of H, denoted w(H), is the smallest size of a subset of E that pins E.[2]
  • The matching width of H, denoted mw(H), is the maximum, over all matchings M in H, of the minimum size of a subset of E that pins M.[3]

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

[edit]

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:

  • w(H) = 2, since E is pinned e.g. by the set { {A,a}, {B,b} }, and cannot be pinned by any smaller set.
  • mw(H) = 1, since every matching can be pinned by a single edge. There are two matchings: {{A,a}, {B,b}} is pinned e.g. by { {A,b} }, and { {A,b}, {B,a} } is pinned e.g. by { {A, a} }.

Characterizations

[edit]

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:

  • w(H) > r if and only if D(H) satisfies a property called P(r,∞), which means that every set of r vertices in D(H) have a common neighbor. This is because w(H) > r iff H has no pinning-set of size r, iff for every subset of r edges of H there is an edge that is not pinned by it, iff every subset of r edges of H has a common neighbor in D(H).
  • mw(H) > r if and only if D(H) satisfies a property called P(r,0), which means that every set of r vertices in D(H) have a common neighbor, and in addition, there is a clique C in D(H) which contains a common neighbor of every such set.

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):

  • w(H) > r if and only if for every set of r vertices in L(H) there is a vertex not adjacent to any of them.
  • mw(H) > r if and only if for every set of r vertices in L(H) there is a vertex not adjacent to any of them, and in addition, there is an independent set I in L(H) which contains a vertex not adjacent to any such set.

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 (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) = (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

[edit]

References

[edit]
  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. ^ a b 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.