I have been trying to firm up my feeling for the theory of clutters. To that end, I have been working through proofs of some elementary lemmas. For my future use, as much as anything else, I will post some of that material here.

A clutter is a pair $H=(S,\mathcal{A})$, where $S$ is a finite set, and $\mathcal{A}$ is a collection of subsets of $S$ satisfying the constraint that $A,A’\in\mathcal{A}$ implies $A\not\subset A’$. In other words, a clutter is a hypergraph satisfying the constraint that no edge is properly contained in another. For this reason we will say that the members of $\mathcal{A}$ are edges of $H$. Clutters are also known as Sperner families, because of Sperner’s result establishing that if $|S|=n$, then
\[\mathcal{A}\leq \binom{n}{\lfloor n/2\rfloor}.\]

Clutters abound in ‘nature’: the circuits, bases, or hyperplanes in a matroid; the edge-sets of Hamilton cycles, spanning trees, or $s$-$t$ paths in a graph. Even a simple (loopless with no parallel edges) graph may be considered as a clutter: just consider each edge of the graph to be a set of two vertices, and in this way an edge of the clutter. There is one example that is particularly important for this audience: let $M$ be a matroid on the ground set $E$ with $\mathcal{C}(M)$ as its family of circuits, and let $e$ be an element of $E$. We define $\operatorname{Port}(M,e)$ to be the clutter
\[(E-e,\{C-e\colon e\in C\in \mathcal{C}(M)\})\]
and such a clutter is said to be a matroid port.

If $H=(S,\mathcal{A})$ is a clutter, then we define the blocker of $H$ (denoted by $b(H)$) as follows: $b(H)$ is a clutter on the set $S$, and the edges of $b(M)$ are the minimal members of the collection $\{X\subseteq S\colon |X\cap A|\geq 1,\ \forall A\in\mathcal{A}\}$. Thus a subset of $S$ is an edge of $b(H)$ if and only if it is a minimal subset that has non-empty intersection with every edge of $H$. Note that if $\mathcal{A}=\{\}$, then vacuously, $|X\cap A|\geq 1$ for all $A\in \mathcal{A}$, no matter what $X$ is. The minimal $X\subseteq S$ is the empty set, so $b((S,\{\}))$ should be $(S,\{\emptyset\})$. Similarly, if $\mathcal{A}=\{\emptyset\}$, then the collection $\{X\subseteq S\colon |X\cap A|\geq 1,\ \forall A\in\mathcal{A}\}$ is empty, so $b((S,\{\emptyset\}))$ should be $(S,\{\})$. The clutter with no edges and the clutter with only the empty edge are known as trivial clutters.

Our first lemma was noted by Edmonds and Fulkerson in 1970.

Lemma. Let $H=(S,\mathcal{A})$ be a clutter. Then $b(b(H))=H$.

Proof. If $H$ is trivial, the result follows by the discussion above. Therefore we will assume that $H$ has at least one edge and that the empty set is not an edge. This implies that $b(H)$ and $b(b(H))$ are also non-trivial. Let $A$ be an edge of $H$. Now every edge of $b(H)$ has non-empty intersection with $A$, by the definition of $b(H)$. Since $A$ is a set intersecting every edge of $b(H)$, it contains a minimal such set. Thus $A$ contains an edge of $b(b(H))$.

Now let $A’$ be an edge of $b(b(H))$. Assume that $A’$ contains no edge of $H$: in other words, assume that every edge of $H$ has non-empty intersection with $S-A’$. Then $S-A’$ contains a minimal subset that has non-empty intersection with every edge of $H$; that is, $S-A’$ contains an edge of $b(H)$. This edge contains no element in common with $A’$. As $A’$ is an edge of $b(b(H))$, this contradicts the definition of a blocker. Hence $A’$ contains an edge of $H$.

Let $A$ be an edge of $H$. By the previous paragraphs, $A$ contains $A’$, an edge of $b(b(H))$, and $A’$ contains $A^{\prime\prime}$, an edge of $H$. Now $A^{\prime\prime}\subseteq A’\subseteq A$ implies $A^{\prime\prime}=A$, and hence $A=A’$. Thus $A$ is also an edge of $b(b(H))$. Similarly, if $A’$ is an edge of $b(b(H))$, then $A^{\prime\prime}\subseteq A\subseteq A’$, where $A’$ and $A^{\prime\prime}$ are edges of $b(b(H))$, and $A$ is an edge of $H$. This implies $A’=A^{\prime\prime}=A$, so $A’$ is an edge of $H$. As $H$ and $b(b(H))$ have identical edges, they are the same clutter. $\square$

If $H=(S,\mathcal{A})$ is a simple graph (so that each edge has cardinality two), then the edges of $b(H)$ are the minimal vertex covers. In the case of matroid ports, the blocker operation behaves exactly as we would expect an involution to do$\ldots$

Lemma. Let $M$ be a matroid and let $e$ be an element of $E(M)$. Then \[b(\operatorname{Port}(M,e))=\operatorname{Port}(M^{*},e).\]

Proof. Note that if $e$ is a coloop of $M$, then $\operatorname{Port}(M,e)$ has no edges, and if $e$ is a loop, then $\operatorname{Port}(M,e)$ contains only the empty edge. In these cases, the result follows from earlier discussion. Now we can assume that $e$ is neither a loop nor a coloop of $M$. Let $A$ be an edge in $\operatorname{Port}(M^{*},e)$, so that $A\cup e$ is a cocircuit of $M$. Since a circuit and a cocircuit cannot meet in the set $\{e\}$, it follows that $A$ has non-empty intersection with every circuit of $M$ that contains $e$, and hence with every edge of $\operatorname{Port}(M,e)$. Now $A$ contains a minimal set with this property, so $A$ contains an edge of $b(\operatorname{Port}(M,e))$.

Conversely, let $A’$ be an edge of $b(\operatorname{Port}(M,e))$. Assume that $e$ is not in the coclosure of $A’$. By a standard matroid exercise this means that $e$ is in the closure of $E(M)-(A’\cup e)$. Let $C$ be a circuit contained in $E(M)-A’$ that contains $e$. Then $C-e$ is an edge of $\operatorname{Port}(M,e)$ that is disjoint from $A’$. This contradicts the fact that $A’$ is an edge of the blocker. Therefore $e$ is in the coclosure of $A’$, so there is a cocircuit $C^{*}$ contained in $A’\cup e$ that contains $e$. Therefore $A’$ contains the edge, $C^{*}-e$, of $\operatorname{Port}(M^{*},e)$.

In exactly the same way as the previous proof, we can demonstrate that $b(\operatorname{Port}(M,e))$ and $\operatorname{Port}(M^{*},e)$ have identical edges. $\square$

This last fact should be attractive to matroid theorists: clutters have a notion of duality that coincides with matroid duality. There is also a notion of minors. Let $H=(S,\mathcal{A})$ be a clutter and let $s$ be an element of $S$. Define $H\backslash s$, known as $H$ delete $s$, to be
\[(S-s,\{A\colon A\in \mathcal{A},\ s\notin A\}\]
and define $H/s$, called $H$ contract $s$, to be
\[(S-s,\{A-s\colon A\in \mathcal{A},\ A’\in \mathcal{A}\Rightarrow A’-s\not\subset A-s\}.\]
It is very clear that $H\backslash s$ and $H/s$ are indeed clutters. Any clutter produced from $H$ by a (possibly empty) sequence of deletions and contractions is a minor of $H$.

We will finish with one more elementary lemma.

Lemma. Let $H=(S,\mathcal{A})$ be a clutter, and let $s$ be an element in $S$. Then

Proof. We note that it suffices to prove the first statement: imagine that the first statement holds. Then
\[b(b(H)\backslash s)=b(b(H))/s=H/s\]
which implies that
\[
b(H)\backslash s=b(b(b(H)\backslash s))=b(H/s)
\]
and that therefore the second statement holds.

If $H$ has no edge, then neither does $H\backslash s$, so $b(H\backslash s)$ has only the empty edge. Also, $b(H)$ and $b(H)/s$ have only the empty edge, so the result holds. Now assume $H$ has only the empty edge. Then $H\backslash s$ has only the empty edge, so $b(H\backslash s)$ has no edges. Also, $b(H)$ and $b(H)/s$ have no edges. Hence we can assume that $H$ is nontrivial, and therefore so is $b(H)$.

If $s$ is in every edge of $H$, then $H\backslash s$ has no edges, so $b(H\backslash s)$ has only the empty edge. Also, $\{s\}$ is an edge of $b(H)$, so $b(H)/s$ has only the empty edge. Therefore we can now assume that some edge of $H$ does not contain $s$, and that therefore $H\backslash s$ is non-trivial and $\{s\}$ is not an edge of $b(H)$.

As $b(H)$ has at least one edge we can let $A$ be an arbitrary edge of $b(H)/s$, and as $\{s\}$ is not an edge of $b(H)$, it follows that $A$ is non-empty. Since $s$ is not in every edge of $H$, we can let $A’$ be an arbitrary edge of $H\backslash s$. Hence $A’$ is an edge of $H$. As $H$ is non-trivial, $A’$ is non-empty. If $A$ is an edge of $b(H)$, then certainly $A$ and $A’$ have non-empty intersection. Otherwise, $A\cup s$ is an edge of $b(H)$, so $A\cup s$ and $A’$ have non-empty intersection. As $A’$ does not contain $s$, it follows that $A$ and $A’$ have non-empty intersection in any case. This shows that every edge of $b(H)/s$ intersects every edge of $H\backslash s$, and thus every edge of $b(H)/s$ contains an edge of $b(H\backslash s)$.

As $H\backslash s$ is non-trivial, so is $b(H\backslash s)$. We let $A’$ be an arbitrary edge of $b(H\backslash s)$ and note that $A’$ is non-empty. Let $A$ be an arbitrary edge of $H$, so that $A$ is non-empty. If $s\notin A$, then $A$ is an edge of $H\backslash s$, so $A’\cap A\ne\emptyset$. If $s$ is in $A$, then $(A’\cup s)\cap A\ne\emptyset$. This means that $A’\cup s$ intersects every edge of $H$, so it contains an edge of $b(H)$ and therefore $A’=(A’\cup s)-s$ contains an edge of $b(H)/s$. We have shown that every edge of $b(H\backslash s)$ contains an edge of $b(H)/s$ and now the rest is easy. $\square$