Clutter (mathematics)

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into Sperner family. (Discuss)

In mathematics, a clutter $H$ is a hypergraph $(V, E)$ , with the added property that $A \not\subseteq B$ whenever $A,B \in E$ and $A \neq B$ (i.e. no edge properly contains another). Clutters are an important structure in the study of combinatorial optimization. The opposite notion of a clutter is an abstract simplicial complex, where every subset of an edge is contained in the hypergraph.

If $H = (V, E)$ is a clutter, then the blocker of $H$ , denoted $b (H)$ , is the clutter with vertex set $V$ and edge set consisting of all minimal sets $B \subseteq V$ so that $B \cap A \neq \varnothing$ for every $A \in E$ . Lehman showed that $b (b (H)) = H$ , so blockers give us a type of duality. We define $ν(H)$ to be the size of the largest collection of disjoint edges in $H$ and $τ(H)$ to be the size of the smallest edge in $b (H)$ . It is easy to see that $\nu(H) \le \tau(H)$ .

[edit] Examples

1. If $G$ is a simple loopless graph, then $H = (V (G), E (G))$ is a clutter and $b (H)$ is the collection of all minimal dominating sets. Here $ν(H)$ is the size of the largest matching and $τ(H)$ is the size of the smallest dominating set.

2. Let $G$ be a graph and let $s,t \in V(G)$ . Define $H = (V, E)$ by setting $V = E (G)$ and letting $E$ be the collection of all edge-sets of $s$ - $t$ paths. Then $H$ is a clutter, and $b (H)$ is the collection of all minimal edge cuts which separate $s$ and $t$ . In this case $ν(H)$ is the maximum number of edge-disjoint $s$ - $t$ paths, and $τ(H)$ is the size of the smallest edge-cut separating $s$ and $t$ , so Menger's theorem (edge-connectivity version) asserts that $ν(H) = τ(H)$ .

3. Let $G$ be a connected graph and let $H$ be the clutter on $E (G)$ consiting of all edge sets of spanning trees of $G$ . Then $b (H)$ is the collection of all minimal edge cuts in $G$ .

[edit] Minors

There is a minor relation on clutters which is similar to that on graphs. If $H = (V, E)$ is a clutter and $v \in V$ , then we may delete $v$ to get the clutter $H \setminus v$ with vertex set $V \setminus \{v\}$ and edge set consisting of all $A \in E$ which do not contain $v$ . We contract $v$ to get the clutter $H / v = b(b(H) \setminus v)$ . These two operations commute, and if $J$ is another clutter, we say that $J$ is a minor of $H$ if a clutter isomorphic to $J$ may be obtained from $H$ by a sequence of deletions and contractions.