# Clutter

A clutter is a set family with no member containing another member. In other context, they are also called Sperner families.

Let ${\mathcal C}$ be a clutter on ground set V. We investigate the following linear system $LP({\mathcal C})$ associated with ${\mathcal C}$:

$\begin{array}{rll} \min wx: \ x(v) & \geq 0 & \text{ for each } v \in V,\\ x(A) & \geq 1 & \text{ for each } A \in {\mathcal C}\\ \end{array}$

• A clutter ${\mathcal C}$ packs if both $LP({\mathcal C})$ and its dual have integral optimal solutions for $w={\mathbf 1}$.
• A clutter ${\mathcal C}$ has the packing property if both $LP({\mathcal C})$ and its dual have integral optimal solutions if $w \in \{0,1, +\infty\}^V$.
• A clutter ${\mathcal C}$ has the max flow min cut property (MFMC property for short) if both $LP({\mathcal C})$ and its dual have integral optimal solutions if $w \in \mathbb{Z}_+^V$. Equivalently, if $LP({\mathcal C})$ is TDI.
• A clutter ${\mathcal C}$ is ideal if $LP({\mathcal C})$ has an integral optimal solution if $w \in \mathbb{Z}_+^V$. Equivalently, if $LP({\mathcal C})$ describes an integer polyhedron.

The blocker of a clutter is the clutter of inclusionwise minimal transversals. Given a clutter ${\mathcal C}$ and an element $v \in V$, the deletion of v means the restriction of the clutter to $V-v$, while the contraction of v is the clutter on ground set $V-v$ formed by the inclusionwise minimal elements of $\{X-v: X \in {\mathcal C}\}$. A minor of ${\mathcal C}$ is a clutter obtained by a sequence of deletions and contractions.

A comprehensive description on the topic can be found in Cornuéjols' book [1]. See also the Wikipedia article.

## References

1. G. Cornuéjols, Combinatorial Optimization: Packing and Covering, author link