Definitions
Nearby Words

# Clutter (mathematics)

In mathematics, a clutter $H$ is a hypergraph $\left(V,E\right)$, with the added property that $A notsubseteq 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 = \left(V,E\right)$ is a clutter, then the blocker of $H$, denoted $b\left(H\right)$, 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\left(b\left(H\right)\right) = H$, so blockers give us a type of duality. We define $nu\left(H\right)$ to be the size of the largest collection of disjoint edges in $H$ and $tau\left(H\right)$ to be the size of the smallest edge in $b\left(H\right)$. It is easy to see that $nu\left(H\right) le tau\left(H\right)$.

## Examples

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

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

3. Let $G$ be a connected graph and let $H$ be the clutter on $E\left(G\right)$ consiting of all edge sets of spanning trees of $G$. Then $b\left(H\right)$ 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 = \left(V,E\right)$ is a clutter and $v in V$, then we may delete $v$ to get the clutter $H setminus v$ with vertex set $V setminus \left\{v\right\}$ and edge set consisting of all $A in E$ which do not contain $v$. We contract $v$ to get the clutter $H / v = b\left(b\left(H\right) setminus v\right)$. 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.