Pattern Recognition on Oriented Matroids

6.7Relatively Blocking Elements in the Boolean Lattices

In this section we count in several ways the rank k relatively r-blocking elements of antichains in the Boolean lattices, and from the viewpoint of combinatorial optimization we thus implicitly count the r-committees, of size k, of clutters; note that the counting of the relatively 0-blocking elements is in fact equivalent to the counting of the blocking sets.

Let A be a nontrivial antichain of the Boolean lattice (n) of rank n, and A⊥ the set of lattice complements of the elements of A in (n). As earlier ρ denotes the rank function, (n)(i) := {b ∈ (n) : ρ(b) = i} is the ith layer of (n