Guest post by Ahmad Abdi

You may have heard of Paul Seymour’s f-Flowing Conjecture on binary matroids, perhaps as alluded to in these detailed posts (I, II, III) by Dillon Mayhew, or in connection with weakly bipartite graphs, or directly from the source. If you haven’t heard of it, or have but don’t remember much, or better yet, know it well but need a new lens to view the problem, it’s your lucky day! I’m here to tell you all about it.

For you to fully appreciate the conjecture though, I’ll have to put it in the proper context. That’ll require me to take you outside your comfort zone of matroids to the larger world of clutters, where I’ll be able to talk about ideal clutters and binary clutters. I’ll then be able to present the f-Flowing Conjecture, the latest progress made towards resolving it, as well as the tools that have made that possible.

But I won’t stop there. I’ll talk about an adjacent, intriguing class of clutters, those without an intersecting clutter as a minor, and then move my way up to the all-encompassing class of clean clutters (an oxymoron, I know!): a minor-closed class whose excluded minors come from degenerate projective planes and odd holes.

label	class name	conjecture
1	Ideal Clutters	Every clutter in this class has bounded chromatic number.
2	Binary Clutters	The f-Flowing Conjecture
3	Clutters without an Intersecting Minor	The $\tau=2$ Conjecture

This series of posts is meant to provide a non-technical survey of the classes displayed below. I shall provide a historical account of each class, hopefully making it clear why the class is interesting, and then provide just one exciting conjecture to stimulate further research on the class.

This post focuses on the class of Ideal Clutters.

1.

Clutters form the framework for my post. I’m grateful that Dillon has already laid the basics in these posts: I, II, III, but let me recall a few definitions, as well as make some new ones; the careful reader will notice that my notation is slightly but harmlessly different from Dillon’s.

Let E be a finite set of elements, and let $\mathcal{C}$ be a family of subsets of E called members. $\mathcal{C}$ is a clutter over ground set E if no member contains another one.

A cover of $\mathcal{C}$ is a subset of E that intersects every member. Every superset of a cover is another cover, so not all covers are interesting from a clutter theoretic perspective, thereby leading us to the forthcoming adjective. A cover is minimal if it does not contain another cover.

By design, the family of minimal covers of $\mathcal{C}$ forms another clutter over the same ground set. This clutter is called the blocker of $\mathcal{C}$, and is denoted $b(\mathcal{C})$. Dillon has already proved the basic fact that the blocking relation is an involution, that is, $b(b(\mathcal{C}))=\mathcal{C}$.

Our choice of terminology for “clutter” and “blocker” follows the convention set forth by Jack Edmonds and Ray Fulkerson in this 1970 paper. The origin of the blocking relation, however, dates earlier to the theory of games, wherein the members of $\mathcal{C}$ represent the minimal winning coalitions, while the blocker takes an adversarial position, collecting all the minimal hitting sets, meant to tear down every winning coalition. For instance, these important 1958 and 1965 papers lay some of the foundational concepts in the study of clutters, predating the Edmonds-Fulkerson paper.

Given disjoint subsets $I,J\subseteq E$, $\mathcal{C}\setminus I/J$ denotes the clutter over ground set $E-(I\cup J)$ whose members are the inclusionwise minimal sets of $\{C-J: C\in \mathcal{C}, C\cap I=\emptyset\}$. This clutter is called the minor of $\mathcal{C}$ obtained after deleting $I$ and contracting $J$. This notion was coined in 1971 by Ray Fulkerson. 

You might find the notions of the blocker and clutter minors reminiscent of matroid duality and matroid minors, in which case you’d be happily surprised that the former two notions may in fact be viewed as extensions of the latter two. 

2.

Now that we’re done with the basics of Clutter Theory, we can move on to the main topic of this post: Ideal Clutters.

$\mathcal{C}$ is an ideal clutter if any of the following equivalent conditions are satisfied:

1. Every vertex of the polyhedron $Q(\mathcal{C}):=\{x\in \mathbb{R}^E_+: x(C)\geq 1 ~ \forall C\in \mathcal{C}\}$ is integral. 
2. For all cost vectors $c\in \mathbb{R}^E$, the linear program $$\text{minimize } c^\top x \text{ subject to } x\in Q(\mathcal{C})$$ if finite has an integral optimal solution.
3. For all lengths $\ell\in \mathbb{R}^E_+$ and widths $w\in \mathbb{R}^E_+$, the width-length inequality holds: $$\min\{\ell(C):C\in \mathcal{C}\}\cdot \min\{w(B):B\in b(\mathcal{C})\}\leq \ell^\top w.$$

Here, $x(C)$ is short-hand notation for $\sum_{e\in C}x_e$.

The term ideal was coined in 1994 by Gérard Cornuéjols and Beth Novick, who used #1 as the main definition. This concept has been dubbed in the literature as the weak max-flow min-cut property, the max-flow min-cut property, the width-length property, or even the Fulkersonian property, all of which only speaks to the rich and tangled history of the concept, hinted at by the following table, displaying various classes of ideal clutters in the literature.

year	reference	Examples of ideal clutters
1927 1956 1979	Menger Ford and Fulkerson Lehman	st-paths of a graph of a graph
1931	König, Egreváry	edges of a simple, bipartite graph
1938	Gallai (a.k.a. Grünwald)	directed st-paths of a digraph
1956	Hoffman and Kruskal	totally unimodular matrices
1967	Edmonds	rooted arborescences of a digraph
1972	Berge	balanced matrices
1973	Edmonds and Johnson	T-joins of a graft
1979	Lucchesi and Younger	dicuts of a digraph
1985 1994	Prodon Goemans	Steiner cuts of a series-parallel digraph
2001	Guenin	odd circuits of a signed graph without an odd-K5 minor
2020	Abdi, Cornuéjols, Guričanová and Lee	cube-ideal sets

In 1963 Alfred Lehman, inspired by Moore and Shannon’s landmark work on unreliable communication networks, studied the width-length inequality, condition #3, and proved it equivalent to #1, and also to what he called the max-flow min-cut equality, #2. In case you’re wondering what the terminology refers to, apply Strong Duality to the LP in #2.

The characterization #3 of idealness is particularly interesting due to its consequence that

the blocker of an ideal clutter is also ideal.

The blocking relation between clutters was later extended to polyhedra by Fulkerson, as documented in this RAND report. In the 1968 memorandum, he develops a geometric view of the blocking relation and gives another proof that idealness is closed under the blocking relation. Sadly, some authors fail to cite Lehman for this fact and only cite Fulkerson’s 1971 published version of the report, even though Ray himself cites Lehman for the fact. Understandably, Lehman did not put his 1963 memorandum in print until 1979!

3.

Not only is idealness closed under the blocking relation, but 

every minor of an ideal clutter is also ideal.

I leave the proof of this as an exercise for the reader; the only thing I’ll say is that there are three proofs, one corresponding to each characterization of idealness.

Given the fact above, a natural question arises:

What are the excluded minors for the class of ideal clutters?

A clutter is minimally non-ideal (mni) if it is non-ideal but every proper minor is ideal. Observe that a clutter is ideal if, and only if, it has no mni minor. In particular, the excluded minors for the class of ideal clutters are precisely the mni clutters.

Note that as idealness is closed under the blocking relation, and deletion/contraction corresponds to contraction/deletion in the blocker, the blocker of every mni clutter is another mni clutter.

In 1963, Lehman found four classes of mni minors, three of which formed infinite classes:

name	elements	members	notes
$\mathbb{L}_7$	1,2,3,4,5,6,7	{1,2,3}, {1,4,5},{1,6,7}, {2,4,7}, {2,5,6}, {3,4,6}, {3,5,7}	The elements/members correspond to the points/lines of the Fano plane. $b(\mathbb{L}_7) =\mathbb{L}_7$
$\Delta_n$, n=3,4,5,…	1,2,3,…,n	{1,2},{1,3},…,{1,n} and {2,3,…,n}	The elements/members correspond to the points/lines of a degenerate projective plane. $b(\Delta_n) =\Delta_n$
Odd hole of dimension n, n=5,7,9,…	1,2,3,…,n	{1,2},{2,3},{3,4}, …,{n-1,n},{n,1}	In the literature, $\Delta_3$ is sometimes called an odd hole, too.
The blocker of an odd hole	1,2,3,…,n	Too many to list.	Every member has cardinality at least $\frac{n+1}{2}$.

Lehman seems to have been discouraged by the multiplicity of the excluded minors:

“Whether or not this list is complete, the multiplicity of minimal matrices seems to preclude their usefulness as a W-L matrix characterization. (Cf. author’s foreword.)” 

In the foreword, which was added 17 years later in 1979 when the paper was finally published, he writes:

“More is known about minimal non-W-L matrices. U. Peled has found several additional classes of matrices which are also classically known in other contexts.”

I’m not sure what additional classes Uri Peled had found at the time but to this day, there are over 1500 small examples of mni clutters: See the paper by Cornuejols and Novick, as well as this paper by Lütolf and Margot. A new infinite class of mni clutters was also found 9 years ago (and don’t forget, the blocking clutters form another infinite class).

Lehman continues in the foreword:

“A consequence of a recent matrix theorem is apparently that the degenerate projective planes [i.e. the deltas] are the only minimal matrices requiring unequal weights.”

More specifically, the consequence of the “matrix theorem” states that for a minimally non-ideal clutter $\mathcal{C}$ different from $\Delta_4$, $\Delta_5$,…,, the width-length inequality is violated for $w=\ell={\bf 1}.$ Whereas for the mni clutters $\Delta_4$, $\Delta_5$,…, the width-length inequality is satisfied for $w=\ell={\bf 1}$.

The foreword above is the humblest of hints to one of the deepest results on ideal clutters, a result that dusted in Lehman’s desk drawer for over 10 years, until it finally appeared in 1990 at the request of Bill Cook and Paul Seymour in the first issue of DIMACS Series. A year later, Lehman won a Fulkerson prize for this “matrix theorem”. If you’re curious about the statement of this theorem, I urge you to read Chapter 9 of my notes, and in particular, Theorem 9.12.

If you, like Lehman himself, are skeptical about the usefulness of his matrix theorem, the next post is bound to change your mind.

4.

Before I conclude with ideal clutters, let me leave you with a conjecture on idealness that Gérard Cornuéjols, Tony Huynh, Dabeen Lee, and I made in a paper whose extended abstract appeared in the proceedings of IPCO 2020, held online this past summer at the London School of Economics.

Suppose $\mathcal{C}$ has no member of cardinality one. A proper colouring of $\mathcal{C}$ is an assignment of colours to the elements so that there is no monochromatic member, that is, it consists of an assignment of an integer $\phi(e)$ to every element $e$ such that $\{\phi(e):e\in C\}$ has cardinality at least two. The chromatic number of $\mathcal{C}$ is the minimum number of colours used in a proper colouring.

Conjecture. There exists an integer $k\geq 4$ such that every ideal clutter without a member of cardinality one has chromatic number at most $k$.

Why $k$ should be at least four, and part of the origins of the conjecture, are explained in the paper. I hope the abrupt appearance of the conjecture is made up for by its utter simplicity.

Thank you for sticking around long enough to read this sentence. If you have any questions, feel free to ask them in the comment section below.

Ahmad Abdi, London School of Economics

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

1. $b(H\backslash s) = b(H)/s$, and
2. $b(H/s) = b(H)\backslash s$.

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$