Width of a hypergraph

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

• The width of H, denoted w(H), is the smallest size of a subset of E that pins E.
• 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.

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. 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 I_M in L(H), and every subset of E that pins M in H corresponds to a set that dominates I_M in L(H).

See also

• For other concepts termed "width" in graph theory, see Width (disambiguation)#Graph theory.