Sperner Family - Clutters

Clutters

A clutter H is a hypergraph, with the added property that whenever and (i.e. no edge properly contains another). That is, the sets of vertices represented by the hyperedges form a Sperner family. Clutters are an important structure in the study of combinatorial optimization. An opposite notion to a clutter is an abstract simplicial complex, where every subset of an edge is contained in the hypergraph (this is an order ideal in the poset of subsets of E).

If is a clutter, then the blocker of H, denoted, is the clutter with vertex set V and edge set consisting of all minimal sets so that for every . It can be shown that (Edmonds & Fulkerson 1970), so blockers give us a type of duality. We define to be the size of the largest collection of disjoint edges in H and to be the size of the smallest edge in . It is easy to see that .