Clutter (mathematics)

In mathematics, a clutter $H$ is a hypergraph $(V,E)$, with the added property that $A\; otsubseteq\; B$ whenever $A,B\; in\; E$ and $A\; eq\; 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\; eq\; varnothing$ for every $A\; in\; E$. Lehman showed that $b(b(H))\; =\; H$, so blockers give us a type of duality. We define $u(H)$ to be the size of the largest collection of disjoint edges in $H$ and $au(H)$ to be the size of the smallest edge in $b(H)$. It is easy to see that $u(H)\; le\; au(H)$.

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 $u(H)$ is the size of the largest matching and $au(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 $u(H)$ is the maximum number of edge-disjoint $s$-$t$ paths, and $au(H)$ is the size of the smallest edge-cut separating $s$ and $t$, so Menger's theorem (edge-connectivity version) asserts that $u(H)\; =\; au(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$.

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.

See also

* Sperner system