Login
Login

Width of a hypergraph

[[File:Width of a hypergraph.svg|thumb|upright=1.35|The hypergraph H shown in both illustrations has width w(H) = 2 and matching width mw(H) = 1.



The set of edges in the first graph highlighted yellow pins all other edges (each edge outside the set shares a vertex with at least one edge inside the set), and there is no smaller set that can pin all edges.



Any matching of the graph can be pinned by a single edge. Here, a matching is shown in red, and an edge that pins it in yellow.

]]

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.{{Cite journal|last1=Aharoni|first1=Ron|last2=Haxell|first2=Penny|date=2000|title=Hall's theorem for hypergraphs|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/1097-0118%28200010%2935%3A2%3C83%3A%3AAID-JGT2%3E3.0.CO%3B2-V|journal=Journal of Graph Theory|language=en|volume=35|issue=2|pages=83–88|doi=10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V|issn=1097-0118|url-access=subscription}} Then:

  • The width of H, denoted w(H), is the smallest size of a subset of E that pins E.{{Cite journal|last=Meshulam|first=Roy|date=2001-01-01|title=The Clique Complex and Hypergraph Matching|url=https://doi.org/10.1007/s004930170006|journal=Combinatorica|language=en|volume=21|issue=1|pages=89–94|doi=10.1007/s004930170006|s2cid=207006642 |issn=1439-6912|url-access=subscription}}
  • 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.{{Cite journal|last=Aharoni|first=Ron|date=2001-01-01|title=Ryser's Conjecture for Tripartite 3-Graphs|url=https://doi.org/10.1007/s004930170001|journal=Combinatorica|language=en|volume=21|issue=1|pages=1–4|doi=10.1007/s004930170001|s2cid=13307018 |issn=1439-6912|url-access=subscription}}

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:

  • 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

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 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 iγ(G), is the maximum, over all independent sets A of G, of the smallest set dominating A.{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Ziv|first3=Ran|date=2007-05-01|title=Independent systems of representatives in weighted graphs|url=https://doi.org/10.1007/s00493-007-2086-y|journal=Combinatorica|language=en|volume=27|issue=3|pages=253–267|doi=10.1007/s00493-007-2086-y|s2cid=43510417 |issn=1439-6912|url-access=subscription}} 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

References

{{reflist}}

Category:Hypergraphs