Width of a hypergraph


In graph theory, there are two related properties of a hypergraph that are called its "width". Given a hypergraph H =, we say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K. Then:
  • The width of H, denoted w, is the smallest size of a subset of E that pins E.
  • The matching width of H, denoted mw, is the maximum, over all matchings M in H, of the minimum size of a subset of E that pins M.
Since E contains all matchings in E, for all H: w ≥ mw.
The width of a hypergraph is used in Hall-type theorems for hypergraphs.

Examples

Let H be the hypergraph with vertex set V = and edge set:
E =
The widths of H are:
  • w = 2, since E is pinned e.g. by the set, and cannot be pinned by any smaller set.
  • mw = 1, since every matching can be pinned by a single edge. There are two matchings: is pinned e.g. by, and is pinned e.g. by.

Characterizations

The disjointness graph of H, denoted D, is a graph where each edge in H is a vertex in D, and every two disjoint edges in H are adjacent in D. The matchings in H correspond to the cliques in D. Meshulam characterized the widths of a hypergraph H in terms of the properties of D. For any positive integer r:
  • w > r if and only if D satisfies a property called P, which means that every set of r vertices in D have a common neighbor. This is because w > 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.
  • mw > r if and only if D satisfies a property called P, which means that every set of r vertices in D have a common neighbor, and in addition, there is a clique C in D which contains a common neighbor of every such set.
The line graph of H, denoted L, is a graph where each edge in H is a vertex in L, and every two intersecting edges in H are adjacent in L. The matchings in H correspond to the independent sets in L. Since L is the complement of D, the above characterization can be translated to L:
  • w > r if and only if for every set of r vertices in L there is a vertex not adjacent to any of them.
  • mw > r if and only if for every set of r vertices in L there is a vertex not adjacent to any of them, and in addition, there is an independent set I in L which contains a vertex not adjacent to any such set.
The domination number of a graph G, denoted γ, 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 = γ. This is because the edges of E are the vertices of L: every subset of E that pins E in H corresponds to a vertex set in L that dominates all L.
The independence domination number of a graph G, denoted iγ, is the maximum, over all independent sets A of G, of the smallest set dominating A. The matching width of a hypergraph equals the independence domination number or its line-graph: mw = iγ. This is because every matching M in H corresponds to an independent set IM in L, and every subset of E that pins M in H corresponds to a set that dominates IM in L.