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.<\/p>\n
A clutter<\/em> 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<\/em> of $H$. Clutters are also known as Sperner families<\/em>, because of Sperner’s result establishing that if $|S|=n$, then 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 If $H=(S,\\mathcal{A})$ is a clutter, then we define the blocker<\/em> 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<\/em> clutters.<\/p>\n Our first lemma was noted by Edmonds and Fulkerson in 1970.<\/p>\n Lemma.<\/strong> Let $H=(S,\\mathcal{A})$ be a clutter. Then $b(b(H))=H$.<\/em><\/p>\n Proof.<\/em> 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))$.<\/p>\n 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$.<\/p>\n 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$<\/p>\n 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$<\/p>\n Lemma.<\/strong> Let $M$ be a matroid and let $e$ be an element of $E(M)$. Then \\[b(\\operatorname{Port}(M,e))=\\operatorname{Port}(M^{*},e).\\]<\/em><\/p>\n Proof.<\/em> 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))$.<\/p>\n 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)$.<\/p>\n 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$<\/p>\n 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$<\/em>, to be We will finish with one more elementary lemma.<\/p>\n Lemma.<\/strong> Let $H=(S,\\mathcal{A})$ be a clutter, and let $s$ be an element in $S$. Then<\/p>\n <\/em><\/p>\n Proof.<\/em> We note that it suffices to prove the first statement: imagine that the first statement holds. Then 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)$.<\/p>\n 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)$.<\/p>\n 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)$.<\/p>\n 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$<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading
\n\\[\\mathcal{A}\\leq \\binom{n}{\\lfloor n\/2\\rfloor}.\\]<\/p>\n
\n\\[(E-e,\\{C-e\\colon e\\in C\\in \\mathcal{C}(M)\\})\\]
\nand such a clutter is said to be a matroid port<\/em>.<\/p>\n
\n\\[(S-s,\\{A\\colon A\\in \\mathcal{A},\\ s\\notin A\\}\\]
\nand define $H\/s$, called $H$ contract $s$<\/em>, to be
\n\\[(S-s,\\{A-s\\colon A\\in \\mathcal{A},\\ A’\\in \\mathcal{A}\\Rightarrow A’-s\\not\\subset A-s\\}.\\]
\nIt 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<\/em> of $H$.<\/p>\n\n
\n\\[b(b(H)\\backslash s)=b(b(H))\/s=H\/s\\]
\nwhich implies that
\n\\[
\nb(H)\\backslash s=b(b(b(H)\\backslash s))=b(H\/s)
\n\\]
\nand that therefore the second statement holds.<\/p>\n