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 = and edge set:

''E'' =

The widths of ''H'' are:

* w(''H'') = 2, since ''E'' is pinned e.g. by the set , 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: is pinned e.g. by , and is pinned e.g. by .

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.

References

{{reflist

Hypergraphs