Bertrand Guenin  The Flowing ConjecturePerfect and Ideal cluttersA family of sets over a finite groundset where no set is properly contained in another is a clutter. Given a clutter \(\mathcal F\) we can define the set packing polytope, \[ Q(\mathcal F)=\{x\geq{\bf 0}: \sum_{v\in S}x_v\leq 1,\; S\in\mathcal F\}. \] The clutter \(\mathcal F\) is said to be perfect if the associated set packing polytope \(Q(\mathcal F)\) is integral. Padberg, Chvátal, and Lovász proved that a clutter \(\mathcal F\) is perfect if and only if its members are the maximal cliques in a perfect graph. Thus the study of perfect clutters reduces to the study of perfect graphs. The Strong Perfect Graph theorem of Chudnowsky, Robertson, Seymour and Thomas, then easily leads to an excluded minor characterization for perfect clutters. Given a clutter \(\mathcal F\) we can define the set covering polyhedron, \[ P(\mathcal F)=\{x\geq{\bf 0}: \sum_{v\in S}x_v\geq 1,\; S\in{\mathcal F}\}. \] The clutter \(\mathcal F\) is said to be ideal if the associated set covering polyhedron \(P\) is integral. Ideal clutters, in contrast to perfect clutters, are not associated with a single class of combinatorial objects. Examples of ideal clutters,
Not all examples of ideal clutters arise from graphs, there are some purely geometric constructions as well. Thus ideal clutter form a very rich and complex class of objects. Problem
Characterize ideal clutters. A solution to this problem seems to be out of range at this juncture, so we will consider special cases. Here we shall focus on excluded minor characterizations. Let us formalize this. Let \(\mathcal F\) be a clutter and let \(P'\) be the polyhedron obtained from \(P(\mathcal F)\) by setting variables to zero and projecting variables. Then \(P'\) is of the form \(P(\mathcal F’)\) for some clutter \(\mathcal F’.\) We then say that \(\mathcal F'\) is a minor of \(\mathcal F.\) As projection and faces of integral polyhedra are integral, idealness is a minor closed property. A clutter is said to be minimally nonideal (mni) if it is not ideal but every proper minor is. Lehman proved that minimally nonideal clutters have a unique fractional extreme point, moreover, that fractional point satisfies some very strong regularity properties. However, this is only a partial characterization, and (in contrast to minimally non perfect clutters) there are complicated infinite classes, and lots of sporadic examples of mni clutters. An accessible proof of Lehman's proof is available in [1]. Results about general mni clutters can be found in [2].
To make further headway we need to restrict ourselves to special classes of clutters. Binary cluttersA signed matroid is a pair \((M,\Sigma)\) where \(M\) is a binary matroid and \(\Sigma\subseteq EM.\) A cycle of \(M\) is even (resp. odd) if \(C\cap\Sigma\) is even (resp. odd). Clearly, the set of inclusionwise minimal odd cycles of \((M,\Sigma)\) is a clutter. Clutters that can be obtained by this construction are said to be binary. If characterizing all mni clutters is difficult, what about binary mni clutters? At least we have the following beautiful 1977 conjecture by Seymour, The Flowing Conjecture
The only minimally nonideal binary clutters are the clutters of
For (1) the groundset of the clutter are the elements of the Fano matroids, and the members the lines. We illustrate the corresponding clutter \(\mathcal F\) in the following picture, For (2) and (3) the groundset are the edges of the complete graph on \(5\) vertices. Note for (2) the members are the triangles and the pentagons and for (3) the members are triangles together with an independent edge and complete graphs on four vertices. The conjecture remains open but there are lots of known special cases as we will discuss next. Known cases of the Flowing ConjectureConsider a binary clutter \(\mathcal F\) and it associated signed matroid \((M,\Sigma)\), recall that \(M\) is a binary matroid. When \(M\) is cographic the members of \(\mathcal F\) are precisely the \(T\)cuts of some graft \((G,T).\) As none of outcomes (1)(3) of the Flowing Conjecture can be expressed as \(T\)cuts, the conjecture implies that clutters of \(T\)cuts are ideals. This is indeed the case and was proved by Edmonds and Johnson. When \(M\) is graphic the members of \(\mathcal F\) are precisely the odd circuits of some signedgraph \((G,\Sigma).\) It is easy to verify that (1) and (3) are not clutters of odd circuits of any signedgraph. Thus the Flowing Conjecture predicts that (2) is the only obstruction to idealness in that case. Indeed this is the case, Weakly Bipartite Theorem
Clutters of odd circuits of signedgraphs are ideal if and only if it they do not contain as a minor the clutter of odd circuits of \(K_5.\)
An immediate consequence of this result are examples (1) and (2). This has implications for multicommodity flow problems. For a survey on flows in graphs and matroids see,
Combining the Weakly Bipartite Theorem, the Theorem of Edmonds and Johnson on \(T\)cuts and Seymour's decomposition of regular matroids, we can obtain sufficient conditions, in term of excluded minors, for a binary clutter to be ideal.
An extension to the Weakly Bipartite Theorem and an extension to the Edmonds and Johnson \(T\)cuts Theorem is given in
In [7] we develop an algorithmic version of Lehman's theorem with applications, including the following, Theorem
For any graph \(G\) with nonnegative weight edges, we can in polynomial time do one of the following, (a) find a maximum weight cut, or (b) find a set of edges \(B\) and a cut \(\delta(U)\) disjoint from \(B\) such that the graph obtained from \(G\) by deleting \(B\) and contracting all edges of \(\delta(U)\) is \(K_5.\)
The Weak Flowing ConjectureConsider a clutter \(\mathcal F\), the blocker of \(\mathcal F\) is the clutter \(b(\mathcal F)\) with the same groundset as \(\mathcal F\) where the members are the inclusionwise minimal sets that intersect every member of \(\mathcal F.\) The blocking operation is an involution and Lehman proved that idealness is preserved under taking the blocker. This is implies in particular that if a clutter is mni then so is its blocker. Observe that the blocker of the Lines of the Fano is itself, and that the blocker of the complements of cuts of \(K_5\) is the clutter of odd circuits of \(K_5.\) As the blocker of a binary clutter is also binary, the Flowing Conjecture can be restated as follows, The Flowing Conjecture  alternate statement
Let \(\mathcal F\) be a minimally nonideal binary clutter. Then \(\mathcal F\) or \(b(\mathcal F)\) is the clutter of the Lines of the Fano or the clutter of the odd circuits of \(K_5.\) Observe that both the clutter of the Lines of the Fano and the clutter of odd circuits of \(K_5\) have a member of cardinality three. Hence, a weakening of the Flowing Conjecture is the following, The Weak Flowing Conjecture
Let \(\mathcal F\) be a minimally nonideal binary clutter. Then \(\mathcal F\) or \(b(\mathcal F)\) has a member of cardinality three. We proved in [8] that in fact the Weak Flowing Conjecture is equivalent to the Flowing Conjecture. The results were then extended in [9].
