# Clutter

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

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

[math] \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} [/math]

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

The **blocker** of a clutter is the clutter of inclusionwise minimal transversals. Given a clutter [math]{\mathcal C}[/math] and an element [math]v \in V[/math], the **deletion** of *v* means the restriction of the clutter to [math]V-v[/math], while the **contraction** of *v* is the clutter on ground set [math]V-v[/math] formed by the inclusionwise minimal elements of [math]\{X-v: X \in {\mathcal C}\}[/math]. A **minor** of [math]{\mathcal C}[/math] 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

- ↑ G. Cornuéjols,
*Combinatorial Optimization: Packing and Covering*, author link