Binary Clutters, Connectivity, and a Conjecture of Seymour.
A binary clutter is the family of odd circuits of a binary matroid, that is, the family of circuits that intersect with odd cardinality a fixed given subset of elements. Let A denote the 0,1 matrix whose rows are the characteristic vectors of the odd circuits. A binary clutter is ideal if the polyhedron $\{ x \geq {\bf 0}: \; Ax \geq {\bf 1} \}$ is integral. Examples of ideal binary clutters are st-paths, st-cuts, T-joins or T-cuts in graphs, and odd circuits in weakly bipartite graphs. In 1977, Seymour [J. Combin. Theory Ser. B, 22 (1977), pp. 289--295] conjectured that a binary clutter is ideal if and only if it does not contain ${\cal{L}}_{F_7}$, ${\cal{O}}_{K_5}$, or $b({\cal{O}}_{K_5})$ as a minor. In this paper, we show that  a binary clutter is ideal if it does not contain five specified minors, namely the three above minors plus two others. This generalizes Guenin's characterization of weakly bipartite graphs [J. Combin. Theory Ser., 83 (2001), pp. 112--168], as well as the theorem of Edmonds and Johnson [ Math. Programming, 5 (1973), pp. 88--124] on T-joins and T-cuts.
INTRODUCTION
A clutter H is a finite family of sets, over some finite ground set E(H), with the property that no set of
H contains, or is equal to, another set of H. A clutter is said to be ideal if the polyhedron fx 2 R jE(H)j
is an integral polyhedron, that is, all its extreme points have 0; 1 coordinates. A
clutter H is trivial if f;g. Given a nontrivial clutter H, we write A(H) for a 0,1 matrix whose
columns are indexed by E(H) and whose rows are the characteristic vectors of the sets S 2 H. With this
notation, a nontrivial clutter H is ideal if and only if fx  is an integral polyhedron.
Given a clutter H, a set T  E(H) is a transversal of H if T intersects all the members of H. The clutter
b(H), called the blocker of H, is defined as follows: E b(H)
E(H) and b(H) is the set of inclusion-wise
minimal transversals of H. It is well known that b b(H)
Hence we say that H; b(H) form a
blocking pair of clutters. Lehman [14] showed that, if a clutter is ideal, then so is its blocker. A clutter is said
to be binary if, for any S 1 contains, or is equal to, a
set of H.
Given a clutter H and i 2 E(H), the contraction H=i and deletion H n i are clutters defined as follows:
fig, the family H=i is the set of inclusion-wise minimal members of
Hg. Contractions and deletions can be performed sequentially,
and the result does not depend on the order. A clutter obtained from H by a set of deletions J d and a set of
contractions J c , (where J c \J called a minor of H and is denoted by HnJ d =J c . It is a proper minor
if J c [ J d 6= ;. A clutter is said to be minimally nonideal (mni) if it is not ideal but all its proper minors are
ideal.
Date: March 2000, revised December 2001.
Key words and phrases. Ideal clutter, signed matroid, multicommodity flow, weakly bipartite graph, T -cut, Seymour's conjecture.
Classification: 90C10, 90C27, 52B40.
This work supported in part by NSF grants DMI-0098427, DMI-9802773, DMS-9509581, ONR grant N00014-9710196, and DMS
96-32032.
EJOLS AND BERTRAND GUENIN
The clutter OK5 is defined as follows: E(OK5 ) is the set of 10 edges of the complete graph K 5 and OK5 is
the set of odd circuits of K 5 (the triangles and the circuits of length 5). The 10 constraints corresponding to the
triangles define a fractional extreme point
3 ) of the associated polyhedron fx
1g. Thus OK5 is not ideal and neither is its blocker. The clutter LF7 is the family of circuits of length three
of the Fano matroid (or, equivalently, the family of lines of the Fano plane), i.e. E(LF7
and

The fractional point
3 ) is an extreme point of the associated polyhedron, hence LF7 is not ideal.
The blocker of LF7 is LF7 itself. The following excluded minor characterization is predicted.
Seymour's Conjecture [Seymour [23] p. 200, [26] (9.2), (11.2)]
A binary clutter is ideal if and only if it has no LF7 , no OK5 , and no b(OK5 ) minor.
Consider a clutter H and an arbitrary element t 62 E(H). We for the clutter with E(H
Hg. The clutter Q 6 is defined as follows: E(Q 6 ) is the set of edges
of the complete graph K 4 and Q 6 is the set of triangles of K 4 . The clutter Q 7 is defined as follows:
Note that the first six columns of A(Q 7 ) form the matrix A b(Q 6 )
The main result of this paper is that Seymour's Conjecture holds for the class of clutters that do not have
6 and Q
7 minors.
Theorem 1.1. A binary clutter is ideal if it does not have LF7 , OK5 , b(OK5
6 or Q
7 as a minor.
Since the blocker of an ideal binary clutter is also a ideal, we can restate Theorem 1.1 as follows.
Corollary 1.2. A binary clutter is ideal if it does not have LF7 , OK5 , b(OK 5
6 ) as a minor.
We say that H is the clutter of odd circuits of a graph G if E(H) is the set of edges of G and H the set of
odd circuits of G. A graph is said to be weakly bipartite if the clutter of its odd circuits is ideal. This class of
graphs has a nice excluded minor characterization.
Theorem 1.3 (Guenin [10]). A graph is weakly bipartite if and only if its clutter of odd circuits has no OK5
minor.
The class of clutters of odd circuits is closed under minor taking (Remark 8.2). Moreover, one can easily
check that OK5 is the only clutter of odd circuits among the five excluded minors of Theorem 1.1 (see
Remark 8.3 and [20]). It follows that Theorem 1.1 implies Theorem 1.3. It does not provide a new proof of
Theorem 1.3 however, as we shall use Theorem 1.3 to prove Theorem 1.1.
Consider a graph G and a subset T of its vertices of even cardinality. A T -join is an inclusion-wise
minimal set of edges J such that T is the set of vertices of odd degree of the edge-induced subgraph G[J ].
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 3
A T -cut is an inclusion-wise minimal set of edges -(U ) := U is a set of
vertices of G that satisfies jU \ T j odd. T -joins and T -cuts generalize many interesting special cases. If
then the T -joins (resp. T -cuts) are the st-paths (resp. inclusion-wise minimal st-cuts) of G. If
then the T -joins of size jV j=2 are the perfect matchings of G. The case where T is identical to the
set of odd-degree vertices of G is known as the Chinese postman problem [6, 12]. The families of T -joins
and T -cuts form a blocking pair of clutters.
Theorem 1.4 (Edmonds and Johnson [6]). The clutters of T -cuts and T -joins are ideal.
The class of clutters of T -cuts is closed under minor taking (Remark 8.2). Moreover, it is not hard to check
that none of the five excluded minors of Theorem 1.1 are clutters of T -cuts (see Remark 8.3 and [20]). Thus
Theorem 1.1 implies that the clutter of T -cuts is ideal, and thus that its blocker, the clutter of T -joins, is ideal.
Hence Theorem 1.1 implies Theorem 1.4. However, we shall also rely on this result to prove Theorem 1.1.
The paper is organized as follows. Section 2 considers representations of binary clutters in terms of
signed matroids and matroid ports. Section 3 reviews the notions of lifts and sources, which are families of
binary clutters associated to a given binary matroid [20, 29]. Connections between multicommodity flows
and ideal clutters are discussed in Section 4. The material presented in Sections 2, 3 and 4 is not all new. We
present it here for the sake of completeness and in order to have a unified framework for the remainder of the
paper. In Sections 5, 6, 7 we show that minimally nonideal clutters do not have small separations. The proof
of Theorem 1.1 is given in Section 8. Finally, Section 9 presents an intriguing example of an ideal binary
clutter.
2. BINARY MATROIDS AND BINARY CLUTTERS
We assume that the reader is familiar with the basics of matroid theory. For an introduction and all
undefined terms, see for instance Oxley [21]. Given a matroid M , the set of its elements is denoted by
E(M ) and the set of its circuits by
). The dual of M is written M  . The deletion minor M n e of M
is the matroid defined as follows: E(M n
and
)g.
The contraction minor M=e of M is defined as (M  n e)  . Contractions and deletions can be performed
sequentially, and the result does not depend on the order. A matroid obtained from M by a set of deletions
J d and a set of contractions J c is a minor of M and is denoted by M n J d =J c .
matroid M is binary if there exists a 0; 1 matrix A with column set E(M ) such that the independent
sets of M correspond to independent sets of columns of A over the two element field. We say that A is a
representation of M . Equivalently, a 0; 1 matrix A is a representation of a binary matroid M if the rows of A
span the circuit space of M  . If C 1 and C 2 are two cycles of a binary matroid then C 1 4 C 2 is also a cycle
of M . In particular this implies that every cycle of M can be partitioned into circuits. Let M be a binary
matroid and   E(M ). The pair (M; ) is called a signed matroid, and  is called the signature of M . We
say that a circuit C of M is odd (resp. even) if jC \ j is odd (resp. even).
The results in this section are fairly straightforward and have appeared explicitly or implicitly in the
literature [8, 13, 20, 23]. We include some of the proofs for the sake of completeness.
EJOLS AND BERTRAND GUENIN
Proposition 2.1 (Lehman [13]). The followingstatements are equivalent for a clutter: (i) H is binary; (ii) for
every
contains, or is equal, to an element of H.
Proposition 2.2. The odd circuits of a signed matroid (M; ) form a binary clutter.
Proof. Let circuits of (M; ). Then L := C 1 4 C 2 4 C 3 is a cycle of M . Since
each of C parity, so does L. Since M is binary, L can be partitioned into a
family of circuits. One of these circuits must be odd since jL \ j is odd. The result now follows from the
definition of binary clutters (see Section 1).
Proposition 2.3. Let F be a clutter such that ; 62 F . Consider the following properties: (i) for all C
F and e 2 C 1 \ C 2 there exists C 3 2 F such that e 62 C 3 . (ii) for all C there exists C 3 2 F such
that C 3  C 1 4 C 2 . If property (i) holds then F is the set of circuits of a matroid. If property (ii) holds then
F is the set of circuits of a binary matroid.
Property (i) is known as the circuit elimination axiom. Circuits of matroids satisfy this property. Note that
property (ii) implies property (i). Both results are standard, see Oxley [21].
Proposition 2.4. Let H be a binary clutter such that ; 62 H. Let F be the clutter consisting of all inclusion-
wise minimal, non-empty sets obtained by taking the symmetric difference of an arbitrary number of sets of
H. Then H  F and F is the set of circuits of a binary matroid.
Proof. By definition, F satisfies property (ii) in Proposition 2.3. Thus F is the set of circuits of a binary
matroid M . Suppose for a contradiction there is S 2 H F . Then there exists S 0 2 F such that S 0  S.
Thus S 0 is the symmetric difference of a family of, say t, sets of H. If t is odd then, Proposition 2.1 implies
that S 0 contains a set of H. If t is even then, Proposition 2.1 implies that S 0 4 S contains a set of H. Thus S
is not inclusion-wise minimal, a contradiction.
Consider a binary clutter H such that ; 62 H. The matroid defined in Proposition 2.4 is called the up matroid
and is denoted by u(H). Proposition 2.1 implies that every circuit of u(H) is either an element of H or the
symmetric difference of an even number of sets of H. Since H is a binary clutter, sets of b(H) intersect with
odd parity exactly the circuits of u(H) that are elements of H. Hence,
Remark 2.5. A binary clutter H such that ; 62 H is the clutter of odd circuits of (u(H); ) where  2 b(H).
Moreover, this representation is essentially unique.
Proposition 2.6. Suppose that the clutters of odd circuits of the signed matroid (N; ) and (N are the
same and are not trivial. If N and N 0 are connected then
To prove this, we use the following result (see Oxley [21] Theorem 4.3.2).
Theorem 2.7 (Lehman [13]). Let e be an element of a connected binary matroid M . The circuits of M not
containing e are of the form C are circuits of M containing e.
We shall also need the following observation which follows directly from Proposition 2.3.
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 5
Proposition 2.8. Let (M; ) be a signed matroid and e an element not in E(M ). Let F := fC [
eveng. Then F is the set of circuit of a binary matroid.
Proof of Proposition 2.6. Let M (resp. M 0 ) be the matroid constructed from
Proposition 2.8. By construction the circuits of M and M 0 using e are the same. Since N is connected and
H is not trivial, M and M 0 are connected. It follows from Theorem 2.7 that and in particular
. By the same argument and Remark 2.5,
In a binary matroid, any circuit C and cocircuit D have an even intersection. So, if D is a cocircuit, the
clutter of odd circuits of (M; ) and (M;  4 D) are the same (see Zaslavsky [28]). Let e 2 E(M ). The
deletion (M; )ne of (M; ) is defined as (M n e;  feg). The contraction (M; )=e of (M; ) is defined
as follows: if e 62  then (M; )=e := (M=e; ); if e 2  and e is not a loop then there exists a cocircuit D
of M with e 2 D and (M; )=e := (M=e; 4D). Note if e 2  is a loop of M , then H=e is a trivial clutter.
A minor of (M; ) is any signed matroid which can be obtained by a sequence of deletions and contractions.
A minor of (M; ) obtained by a sequence of J c contraction and J d deletions is denoted (M; )=J c n J d .
Remark 2.9. Let H be a the clutter of odd circuits of a signed matroid (M; ). If J c does not contain an odd
circuit, then H=J c n J d is the clutter of odd circuits of the signed matroid (M; )=J c n J d .
Let M be a binary matroid and e an element of M . The clutter P ort(M; e), called a port of M , is defined
as
)g.
Proposition 2.10. Let M be a binary matroid, then P ort(M; e) is a binary clutter.
Proof. By definition S 2 P ort(M; e) if and only if S [ feg is an odd circuit of the signed matroid (M; feg).
We may assume P ort(M; e) is nontrivial, hence in particular, e is not a loop of M . Therefore, there exists a
cocircuit D that contains e. Thus P ort(M; e) is the clutter of odd circuits of the signed matroid (M=e; D 4
feg). Proposition 2.2 states that these odd circuits form a binary clutter.
Proposition 2.11. Let H be a binary clutter. Then there exists a binary matroid M with element e 2 E(M )
E(H) such that P ort(M;
Proof. If define M to have element e as a loop. If ; 62 H, we can represent H as the set of odd
circuits of a signed matroid (N; ) (see Remark 2.5). Construct a binary matroid M from (N; ) as in
Proposition 2.8. Then P
Proposition 2.12 (Seymour [23]). P ort(M; e) and P ort(M  ; e) form a blocking pair.
Proof. Proposition 2.10 implies that P ort(M; e) and P ort(M  ; e) are both binary clutters. Consider T 2
is a circuit of M . For all is a circuit of M  . Since
T [feg and S[feg have an even intersection jS \T j is odd. Thus we proved: for all
is To complete the proof it suffices to show: for all T
there is
odd (Proposition 2.1). Thus T 0 [ feg intersects every circuit of M using e with even parity. It follows from
Theorem 2.7 that T 0 [ feg is orthogonal to the space spanned by the circuits of M , i.e. T 0 [ feg is a cycle of
M  . It follows that there is a circuit of M  of the form T [ feg where T  T 0 . Hence,
required.
EJOLS AND BERTRAND GUENIN
3. LIFTS AND SOURCES
Let N be a binary matroid. For any binary matroid M with element e such that M=e, the binary
clutter P ort(M; e) is called a source of N . Note that H is a source of its up matroid u(H). For any binary
matroid M with element e such that e, the binary clutter P ort(M; e) is called a lift of N . Note
that a source or a lift can be a trivial clutter.
Proposition 3.1. Let N be a binary matroid. H is a lift of N if and only if b(H) is a source of N  .
Proof. Let H be a lift of N , i.e. there is a binary matroid M with M n
Proposition 2.12, we have that b(H) is a source of
N  . Moreover, the implications can be reversed.
It is useful to relate a description of H in terms of excluded clutter minors to a description of u(H) in
terms of excluded matroid minors.
Theorem 3.2. Let H be a binary clutter such that its up matroid u(H) is connected, and let N be a connected
binary matroid. Then u(H) does not have N as a minor if and only if H does not have H 1 or H
2 as a minor,
a source of N and H 2 is a lift of N .
To prove this we will need the following result (see Oxley [21] Proposition 4.3.6).
Theorem 3.3 (Brylawski [3], Seymour [25]). Let M be a connected matroid and N a connected minor of
M . For any i 2 E(M ) E(N ), at least one of M n i or M=i is connected and has N as a minor.
Proof of Theorem 3.2. Let M := u(H) and let  2 b(H). Remark 2.5 states that H is the clutter of odd
circuits of (M; ). Suppose first that H has a minor H 1 that is a source of N . Remark 2.9 implies that H 1
is the clutter of odd circuits of a signed minor (N 0 ;  0 ) of (M; ). Since N is connected, H 1 is nontrivial
and therefore Proposition 2.6 implies In particular N is a minor of M . Suppose now that H has a
is a lift of N . Let e be the element of E(H
implies that H +is the clutter of odd circuits of a signed minor
of (M; ). Since H 2 is a lift of N there is a connected
M 0 with element e such that ^
2 is the clutter of odd
circuits of
M 0 is a minor of M and so is
Now we prove the converse. Suppose that M has N as a minor and does not satisfy the theorem. Let H be
such a counterexample minimizing the cardinality of E(H). Clearly, N is a proper minor of M as otherwise
is a source of N . By Theorem 3.3, for every i 2 E(M ) E(N ), one of M n i and M=i is
connected and has N as a minor. Suppose M=i is connected and has N as a minor. Since i is not a loop of M ,
it follows from Remark 2.9 that H=i is nontrivial and is a signed minor (M=i;  0 ) of (M; ). Proposition 2.6
implies contradicts the choice of H minimizing the cardinality of E(H). Thus,
for every connected and has an N minor. Suppose for some
because of Remark 2.9 and Proposition 2.6 u(H n a contradiction to the
choice of H. Thus for every or equivalently, all odd circuits of (M; )
use i. As even circuits of M do not use i. We claim that E(M ) E(N
not and let j 6= i be an element of E(M ) E(N ). The set of circuits of (M; ) using j is exactly the set
of odd circuits. It follows that the elements must be in series in M . But then M n i is not connected,
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 7
a contradiction. Therefore E(M . As the circuits of (M; ) using i are
exactly the odd circuits of (M; ), it follows that column i of A(H) consists of all 1's. Thus
is a lift of N .
Next we define the binary matroids F 7 ; F
7 and R 10 . For any binary matroid N , let BN be a 0,1 matrix
whose rows span the circuit space of N (equivalently BN is a representation of the dual matroid N  ). Square
identity matrices are denoted I . Observe that R
I
Given a binary matroid N , let M be a binary matroid with element e such that M=e. The circuit space
of M is spanned by the rows of a matrix of the form [BN jx], where x is a 0,1 column vector indexed by e.
Assuming M is connected, we have (up to isomorphism), the following possible columns x for each of the
three aforementioned matroids
x
x
x
Note that (1),(2) are easy and (3) can by found in [24] (p. 357). The rows of the matrix [BF7 jx b ] (resp.
span the circuit space of a matroid known as AG(3; 2) (resp. S 8 ). If [BN jx] is a matrix whose
rows span the circuits of M , then by definition of sources, P ort(M; e) is a source of N . Thus,
Remark 3.4.
7 has a unique source, namely Q
6 .
F 7 has three sources:
sources including b(OK5 ) (when
Luetolf and Margot [16] have enumerated all minimally nonideal clutters with at most 10 elements (and many
more). Using Remark 3.4, we can then readily check the following.
Proposition 3.5. Let H be the clutter of odd circuits of a signed matroid (M; ).
or H is ideal.
7 , then H is ideal.
4. MULTICOMMODITY FLOWS
In this section, we show that a binary clutter H is ideal exactly when certain multicommodity flows exist
in the matroid u(H). This equivalence will be used in Sections 6 and 7 to show that minimally nonideal
EJOLS AND BERTRAND GUENIN
binary clutters do not have small separations. Given a set S, a function
i2T p(i). Consider a signed matroid (M; F ). The set of circuits of M that have exactly one
element in common with F , is
denoted
F . Let be a cost function on the elements of M .
Seymour [26] considers the following two statements about the triple (M; F; p).
For any cocircuit D of M :
There exists a function
F
We say that the cut condition holds if inequality (4.1) holds for all cocircuits D. We say that M is F -flowing
with costs p if statement (4.2) holds; the corresponding solution is an F -flow satisfying costs p. M is F -
flowing [26] if, for every p for which the cut condition holds, M is F -flowing with costs p. Elements in F
are called demand (resp. capacity) elements. It is helpful to illustrate the aforementioned
definitions in the case where M is a graphic matroid [9]. For a demand edge f , p(f) is the amount of flow
required between its endpoints. For a capacity edge e, p(e) is the maximum amount of flow that can be carried
by e. Then M is F -flowing with costs p when a multicommodity flow meeting all demands and satisfying all
capacity constraints exists. The cut condition requires that for every cut the demand across the cut does not
exceed its capacity. When F consists of a single edge f and when M is graphic then M is f-flowing [7].
The cut condition states p(D \F )  p(D F
sides, we obtain p(F
Remark 4.1. The cut condition holds if and only if p(F )  p(D 4 F ) for all cocircuits D.
Let H be the clutter of odd circuits of (M; F ). We define:
(a)
(H;
(b)
By linear programming duality we have:  (H; p)    (H; p). When
write  (H) for  (H; p) and   (H) for   (H; p).
Proposition 4.2. Let H be the clutter of odd circuits of a signed matroid (M;F ) and let
only if the cut condition holds.
-flowing with costs p.
(iii) If (C) > 0 for a solution to (4.2), then CF for all F 2 b(H) with p(F
Proof. We say that a set X  E(M ) is a (feasible) solution for (a) if its characteristic vector is. Consider
(i). Suppose  (H; We can assume that F is an inclusion-wise minimal solution of (a) and thus
D be any cocircuit of M and consider any S 2 H. Since S is a circuit of M , jD \ Sj is even
and since H is binary, jF \Sj is odd. Thus j(D 4F ) \Sj is odd. It follows that D4F is a transversal of H.
Therefore, D 4 F is a feasible solution to (a) and we have p(F )  p(D 4 F ). Hence, by Remark 4.1, the
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 9
cut condition holds. Conversely, assume the cut condition holds and consider any set X that is feasible for
(a). We need to show p(F )  p(X). We can assume that X is inclusion-wise minimal, i.e. that X 2 b(H).
Observe that F and X intersect circuits of M with the same parity. Thus D := F 4 X is a cocycle of M .
Since the cut condition holds, by Remark 4.1, p(F )  p(D 4 F
Consider (ii). Suppose   (H; it follows from linear
programming duality that F is an optimal solution to (a). Let y be an optimal solution to (b). Complementary
slackness states: if jF \ Cj > 1, then the corresponding dual variable y
F
y C , for all e 2 E(M ). Complementary slackness states: if e 2 F , then
F
Hence, choosing every CF satisfies (4.2). Conversely, suppose  is a solution to (4.2).
For each e 2 F such that
C:
F
reduce the values C on the left hand side until equality
holds. Since C contains no element of F other than e, we can get equality for every e 2 F . So we may
assume
F
Now y is a feasible solution to (b) and F; y satisfy all complementary slackness conditions. Thus F and y
must be a pair of optimal solutions to (a) and (b) respectively.
Finally, consider (iii). From (ii) we know there is an optimal solution y to (b) with y C > 0. By complementary
slackness, it follows that jF \ F that are optimal solutions to (a).
The last proposition implies in particular that, if M is F -flowing with costs p, then the cut condition is
satisfied. We say that a cocircuit D is tight if the cut condition (4.1) holds with equality, or equivalently
(Remark 4.1) if p(F
Proposition 4.3. Suppose M is F -flowing with costs p and let D be a tight cocircuit. If C is a circuit with
Proof. We may assume C\D 6= ;. As CF , it follows that ffg. Moreover, C\D 6= ffg, since
M is binary. To complete the proof, it suffices to show that there is no pair of elements
Suppose for a contradiction that we have such a pair and let F As D is tight, p(F
It follows from Proposition 4.2(iii) that CF 0 . But
Corollary 4.4. Let H be the clutter of odd circuits of a signed matroid (M; F ). (i) If H is ideal then M
is F -flowing with costs p, for all satisfies the cut condition. (ii) If H
is nonideal then M is not F 0 -flowing with costs p, for some
minimizes p(F 0 ).
Proof. Consider (i). Proposition 4.2 states  (H; Because H is ideal,  (H;
This implies by Proposition 4.2(ii) that M is F -flowing with costs p. Consider (ii). If H
is nonideal then for some be an optimal solution to (a).
states M is not F 0 -flowing with costs p.
We leave the next result as an easy exercise.
Corollary 4.5. A binary clutter H is ideal if and only if u(H) is F -flowing for every F 2 b(H).
Consider the case where H = OK5 . Let F be a set of edges of K 5 such that E(K 5 ) F induces a K 2;3 .
(the graphic matroid of K 5 ) is not F -flowing.
EJOLS AND BERTRAND GUENIN
5. CONNECTIVITY, PRELIMINARIES
be a partition of the elements E of a matroid M and let r be the rank function. M
is said to have a k-separation
then the separation is said to be strict. A matroid M has a k-separation only if its dual M  does
(Oxley [21], 4.2.7). A matroid is k-connected if it has no (k 1)-separation and is internally k-connected if
it has no strict (k 1)-separation. A 2-connected matroid is simply said to be connected. We now follow
Seymour [24] when presenting k-sums. Let M be binary matroids whose element sets E(M 1
may intersect. We define M 1 4M 2 to be the binary matroid on E(M 1 the cycles are all
the subsets of E(M 1 of the form C 1 4 C 2 where C i is a cycle of M i , 2. The following
special cases will be of interest to us:
Definition 5.1.
is the 1-sum of M
f is not a loop of M 1 or M 2 . Then M 1 4M 2 is the 2-sum of M
a circuit of both M 1 and M 2 . Then M 1 4M 2 is the
3-sum of M
We denote the k-sum of M 1 and M 2 as Mk M 2 . The elements in E(M i are called the markers
of M i . As an example, for 3, the k-sum of two graphic matroids corresponds to taking two graphs,
choosing a k-clique from each, identifying the vertices in the clique pairwise and deleting the edges in the
clique. The markers are the edges in the clique. We have the following connection between k-separations
and k-sums.
Theorem 5.2 (Seymour [24]). Let M be a k-connected binary matroid and k 2 f1; 2; 3g. Then M has a
k-separation if and only if it can be expressed as Mk M 2 . Moreover, M 1 (resp. M 2 ) is a minor of M
obtained by contracting and deleting elements in E(M 2
We say that a binary clutter H has a (strict) k-separation if u(H) does.
Remark 5.3. H has a 1-separation if and if A(H) is a block diagonal matrix. Moreover, H is ideal if and
only if the minors corresponding to each of the blocks are ideal.
Recall (Proposition 2.11) that every binary clutter H can be expressed as P ort(M; e) for some binary
matroid M with element e. So we could define the connectivity of H to be the connectivity of the associated
matroid M . The two notions of connectivity are not equivalent as the clutter LF7 illustrates. The matroid
AG(3; 2) has a strict 3-separation while F 7 does not, but P ort(AG(3; 2); and LF7 is the clutter of
odd circuits of the signed matroid F 7
Chopra [4] gives composition operations for matroid ports and sufficient conditions for maintaining ide-
alness. This generalizes earlier results of Bixby [1]. Other compositions for ideal (but not necessarily binary
clutters) can be found in [19, 17, 18]. Novick-Seb-o [20] give an outline on how to show that mni binary
clutters do not have 2-separations, the argument is similar to that used by Seymour [26](7.1) to show that
k-cycling matroids are closed under 2-sums. We will follow the same strategy (see Section 6). Proving that
mni binary clutters do not have 3-separations is more complicated and requires a different approach (see
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 11
Section 7). In closing observe that none of LF7 ; OK5 and b(OK5 ) have strict 4-separations. So if Seymour's
Conjecture holds, then mni binary clutters are internally 5-connected.
6. 2-SEPARATIONS
Let (M;F ) be a signed matroid with a 2-separation
We say that is a part of (M;F ) if it is a signed minor
of (M; F ). It is not hard to see that at most two choices of F i can give distinct signed matroids
Therefore (M;F ) can have at most four distinct parts. In light of Remark 2.5 we can identify binary clutters
with signed matroids. The main result of this section is the following.
Proposition 6.1. A binary clutter with a 2-separation is ideal if and only if all its parts are ideal.
To prove this, we shall need the following results.
Proposition 6.2 (Seymour [24]). If connected if and only if M 1 and M 2 are
connected.
Proposition 6.3 (Seymour [24]). Let M be a binary matroid with a 2-separation
two circuits of M . If C 1
Proposition 6.4 (Seymour [24]). Let choose any circuit C of M such that C\E 1
and C \E 2 6= ;. Let j. For any f 2 C
Proof of Proposition 6.1. Let H be a binary clutter with a 2-separation,
without loss of generality that M is connected. Remark 2.5 states that H is the clutter of odd circuits of
(M; F ). If H is ideal, then so are all its parts by Remark 2.9. Conversely, suppose all parts of (M; F ) are
ideal. Consider any p : E(M Because of Corollary 4.4(ii),
it suffices to show that M is F -flowing with costs p. Observe that the cut condition is satisfied because of
Proposition 4.2(i).
Since M has a 2-separation, it can be expressed as M2 M 2 . Throughout this proof,
denote arbitrary distinct elements of f1; 2g. Define F be the marker of M i . Since f i is
not a loop, there is a cocircuit D i of M i using f i . Let  i denote the smallest value of
where D i is any cocircuit of M i using f i . In what follows, we let D i denote some cocircuit where the
minimum is attained. Expression (*) gives the difference between the sum of the capacity elements and the
sum of the demand elements in D i , excluding the marker f i . Thus
is a cocycle of M and the cut condition is satisfied, we must have:
Claim 1. If  i > 0, then there is an even circuit of (M uses marker f i .
Proof of Claim: Suppose for a contradiction that all circuits C of M i that use f i , satisfy jC \ F i j odd. Then
intersects all these circuits with even parity. By hypothesis M is connected and, because of
Proposition 6.2, so is M i . We know from Theorem 2.7 that all circuits that do not use the marker f i are the
EJOLS AND BERTRAND GUENIN
symmetric difference of two circuits that do use f i . It follows that D intersects all circuits of M i with even
parity. Thus D is a cocycle of M i . But expression (*) is nonpositive for cocycle D. D can be partitioned
into cocircuits. Because the cut condition holds, expression (*) is nonpositive for the cocircuit that uses f i , a
contradiction as  i > 0. 3
2. If  i < 0, then there is an odd circuit of (M uses marker f i .
Proof of Claim: Suppose, for a contradiction, that all circuits C of M i that use f i , satisfy jC \ F i j even. By
the same argument as in Claim 1, we know that in fact so do all circuits of M i . This implies that F and F j
intersect each circuit of M with the same parity. As F is inclusion-wise minimal must have
;. But this implies that expression (*) is non negative, a contradiction. 3
a part of (M; F ).
Proof of Claim: From Claim 2 (resp. Claim 1), there is an odd (resp. even) circuit C using f j of (M
Proposition 6.3 implies that elements are in series in M n (E j C). Proposition 6.4 implies that M i
is obtained from M n (E j C) by replacing series elements of C \E j by a unique element f j . The required
signed minor is (M; F any element of C
Because suffices to consider the following cases.
Case 1:  1  0;  2  0.
We know from Proposition 6.4 that M i is a minor of M (where no loop is contracted) say M n J d =J c .
For
be the signed minor (M; F ) n J d =J c . Since (M
a part of (M; F ), it is ideal.
So in particular (M
be defined as follows:
Let D be a cocircuit of M i n f i . The inequality p(D \ F i )  p(D F i ) follows
from  i  0 when D [ f i is a cocircuit of M i and it follows from the fact that the cut condition holds for
when D is a cocircuit of M i . Therefore the cut condition holds for It follows from
Corollary 4.4(i) that each of these signed matroids has an F i -flow satisfying costs p i . Let  i
be the corresponding function satisfying (4.2). By scaling p, we may assume  i for each circuit in
. Let L i be the multiset where each circuit C
in
appears  i (C) times. Define L j similarly. The union
(with repetition) of all circuits in L i and L j correspond to an F -flow of M satisfying costs p.
Case 2:  i < 0;  j > 0.
Because of Claim 3, there are parts (M
defined as follows: p i (f be defined as follows:
Since we can scale p, we can assume that the F i -flow of M i
satisfying costs p i is a multiset L i of circuits and that the F j [ff j g-flow of M j satisfying costs p j is a multiset
l can be partitioned into L l
is a demand element for the flow L j , jL j
is a capacity element for the
flow
j. Let us define a collection of circuits of M
as follows: include all circuits of L i
. Pair each circuit C
1 with a different circuit C
1 , and
add to the collection the circuit included in C i 4C j that contains the element of F . The resulting collection
corresponds to a F -flow of M satisfying costs p.
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 13
7. 3-SEPARATIONS
The main result of this section is the following,
Proposition 7.1. A minimally nonideal binary clutter H has no strict 3-separation.
The proof follows from two lemmas, stated next and proved in sections 7.1 and 7.2 respectively.
Lemma 7.2. Let H be a minimally nonideal binary clutter with a strict 3-separation There exists a
set F 2 b(H) of minimum cardinality such that F  E 1 or F  E 2 .
Let (M; F ) be a signed matroid with a strict 3-separation
be the triangle common to both M 1 and M 2 .
Let
be obtained by deleting from M i a (possibly empty) set of elements of C 0 . We call
of (M; F ) if it is a signed minor of (M; F ).
Lemma 7.3. Let (M; F ) be a connected signed matroid with a strict 3-separation suppose
-Flowing with costs p if the cut condition is satisfied and all parts of (M; F ) are ideal.
Proof of Proposition 7.1. Suppose H is a mni binary clutter that is connected with a strict 3-separation. Re-mark
2.5 states that H is the clutter of odd circuits of a signed matroid (M;F ). Consider
defined by We know (see Remark 7.5) that  (H; p) >   (H; p). From
Lemma 7.2 and Remark 2.5, we may assume F  E 1 and p(F It follows from Proposition
4.2(i) that the cut condition holds. Since the separation of (M; F ) is strict, all parts of (M; F ) are proper
minors, and hence ideal. It follows therefore from Lemma 7.3 that M is F -flowing with costs p. Hence,
because of Proposition 4.2(ii),   (H;
7.1. Separations and blocks. In this section, we shall prove Lemma 7.2. But first let us review some results
on minimally nonideal clutters. For every clutter H, we can associate a 0; 1 matrix A(H). Hence we shall
talk about mni 0; 1 matrices, blocker of 0; 1 matrices, and binary 0; 1 matrices (when the associated clutter is
binary). The next result on mni 0,1 matrices is due to Lehman [15] (see also Padberg [22], Seymour [27]).
We state it here in the binary case.
Theorem 7.4. Let A be a minimally nonideal binary 0,1 matrix with n columns. Then
nonideal binary as well, the matrix A (resp. B) has a square, nonsingular row submatrix
A (resp.
B) with
entries in every row and columns, rs > n. Rows of A (resp. B) not in
A (resp.
B) have
at least r entries. Moreover,
A
(rs n)I , where J denotes an n  n
matrix filled with ones.
It follows that ( 1
r ) is a fractional extreme point of the polyhedron fx 2 R n
1g. Hence,
Remark 7.5. If H is a minimally nonideal binary clutter, then  (H) >   (H).
The submatrix
A is called the core of A. Given a mni clutter H with we define the core of H to
be the clutter
H for which A(
A. Let H and be binary and mni. Since H;G are binary, for all
H and T 2
G, we have jS \T j odd. As
A
(rs n)I , for every S 2
H, there is exactly one set
G called the mate of S such that jS \ T (rs n). Note that if A is binary then rs
EJOLS AND BERTRAND GUENIN
Proposition 7.6. Let A be a mni binary matrix. Then no column of
A is in the union of two other columns.
Proof. Bridges and Ryser [2] proved that square 0; 1 matrices
B that satisfy
A
commute, i.e.
A T
(rs n)I. Thus col(
rs ng.
Hence there is no ng fig such that col(
A; i), for otherwise
contradicting the equation
A T
(rs n)I.
Proposition 7.7 (Guenin [10]). Let H be a mni binary clutter and e 2 E(H). There exists
such that S 1
Proposition 7.8 (Guenin [10]). Let H be a mni binary clutter and S 1
H. If S
then either
Proposition 7.9. Let H be a mni binary clutter and let
2.
Proof. Let T be the mate of S. Then jT \ Sj  3 and jT \ S
Proposition 7.10 (Luetolf and Margot [16]). Let H be a mni binary clutter. Then
H). Further-
more, if T is a transversal of
H and jT
then T is a transversal of H.
We shall also need,
Proposition 7.11 (Seymour [24]). Let M be a binary matroid with 3-separation . Then there exist
circuits such that every circuit of M can be expressed as the symmetric difference of a subset of
circuits in fC 2
g.
Throughout this section, we shall consider a signed matroid (M; F ) with a 3-separation
will denote the corresponding circuits of Proposition 7.11. Let H be the clutter of odd circuits of (M; F ). We
shall partition b(H) into sets
Proposition 7.12. If S 1 contains a set of b(H).
Proof. Let Note that since S 1 circuits C of M , jS 1 \ Cj
and jS 2 \ Cj have the same parity. This implies that if C is a circuit where C
intersects S 0 and S 1 with the same parity. It also implies, together with the definition of B i , that S 0 intersects
with the same parity as S 1 . It follows from Proposition 7.11 that S 0 and S 1 intersect all
circuits of M with the same parity.
Proof of Lemma 7.2. Let G denote the blocker of H and let be the sets partitioning G. We
will denote by
G the core of G. It follows that
G can be partitioned into sets
. Assume for a contradiction that for all S 2
We will say that a set
with forms an E 1 -block if, for all pairs of sets
Similarly we define E 2 -blocks.
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 15
Claim 1. For each nonempty
is either an or an E 2 -block.
Proof of Claim: Consider S 1
Proposition 7.12 states that (S 1 contains a set
G. Proposition 7.8 implies that S
Moreover, by hypothesis neither S 0 \E 1 nor S 0 \E 2 is empty. Since
chosen arbitrarily, the result follows. 3
For any nonempty
. We define E(
to be equal to S \
is an
and to S \
is an E 2 -block. Let r (resp. s) be the cardinality of the members of
H)j. As H is binary r  3 and s  3.
2. Let U  E(
G) be a set that intersects E(
. Then U is a transversal of
G
and jU j
Proof of Claim: Clearly U is a transversal of
G, thus jU j   (
G). Proposition 7.10 states  (
3. Let U; U 0 be distinct transversals of
G. If  (
2.
Proof of Claim: Proposition 7.10 imply that U and U 0 are minimum transversals of G. Hence, U; U
The result now follows from Corollary 7.9. 3
4. None of the
Proof of Claim: Let U be a minimum cardinality set that intersects E(
r  3, it follows from Claim 2 that at most one of the
can be empty. Assume for a contradiction that
one of the
is empty. It follows from Claim 2 and the choice of U that each of E(
E(
are pairwise disjoint (otherwise U contains an element common to at least 2 of E(
E(
1 be distinct elements of E(
E(
E(
contradict Claim 3. Thus jE(
similarly, jE(
are not all E 1 -blocks and not
-blocks. Thus w.l.o.g. we may assume
-blocks and
3 is an E 2 -block. Let t 1 be any
element in E 1 E(
E(
be the unique element in E(
the column of A(
indexed
by t 1 is included in the column of A(
indexed by t 2 , a contradiction to Proposition 7.6. 3
Consider first the case where every
is an E 1 -block. Suppose that no two E(
has four columns that add up to the vector of all ones. By Theorem 7.4, each of these columns has s ones
and therefore 4s. Furthermore the four elements that index these columns form a transversal of
G
and therefore r  4 (see Claim 2). This contradicts Theorem 7.4 stating that rs > n. Thus two E(
intersect, say
. For otherwise a contradiction to rs > n. Let t be any element of
E(
any element of E(
E(
4 g. It follows
from Claim 2 that r = 3. It follows from Claim 3 that each of E(
E(
cardinality one, and
E(
E(
contains a unique element e. Since there are no dominated columns in A(
we have that
E(
E(
a contradiction to the hypothesis that the 3-separation is
strict.
Consider now the case where
-blocks and
-blocks. Suppose there exists
that is not in any of E(
4g. Assume without loss of generality that e
EJOLS AND BERTRAND GUENIN
Then column e of A(
is included in the union of any two columns f 1 2 E(
E(
contradiction to Proposition 7.6. Thus every element of E(H) is in E(
there is e 2 E(
E(
g. Then implies that
partitioned into E(
E(
partitioned into E(
E(
4, then we can use Claim 3 to show that for each i 2
contradiction as then jE 2. Thus
be a minimum transversal of
G. Suppose both u; v 2 E(
E(
is a transversal. It then follows that T intersects all sets of
parity, a contradiction as H is binary. Thus we may assume w 2 E(
all sets in
It follows that, for any x 2 E(
E(
3 ), the set fw; x; yg is a transversal of
G, a contradiction to
3. Hence for any transversal each element of T is in a different E(
may
assume E(
E(
E(
It follows that for any x 2 E(
wg is a transversal
and thus by Claim 3 E(
contains a unique element t. Since jE 1 j > 2, we cannot have a transversal
E(
E(
E(
would imply jE(
Hence every minimum transversal
contains t, a contradiction to Theorem 7.4.
Finally, consider the case where
-blocks and
B 4 is an E 2 -block. Note that every t
is in some E(
3g. Otherwise the corresponding column t of A(
is dominated by any
E(
Suppose there is t 2 E(
E(
are distinct elements in
3g. Proposition 7.7 states there exist three sets of
G that intersect exactly in t. This implies jE(
Now since E(
E(
there is a column in say E(
E(
Similarly,
a contradiction to jE 1 j > 3. Thus E(
E(
and therefore either (1) for some distinct E(
E(
is a partition of E(
E(
E(
for each distinct 3g. By considering sets U containing one element of
E(
intersecting each of E(
E(
E(
use Claim 3 to show that jE 1 j  2 in
Case (1) and jE 1 j  3 in Case (2), a contradiction.
7.2. Parts and minors. In this section, we prove Lemma 7.2 Consider the matroid with exactly three elements
which form a circuit C 0 . Let I 0 ; I 1 be disjoint subsets of C 0 . We say that a signed matroid
(N; ) is a fat triangle is obtained from C 0 by adding a parallel element for every
signed binary matroid with a circuit C
of M is a simple circuit of type We say that a
cocircuit D has a small intersection with a simple circuit C if either: D \ and the
unique element in C \  is in D.
Lemma 7.13. Let (M; ) be a signed binary matroid with a circuit C
(1) Let I  C 0 be such that for all i 2 I there is a simple circuit C i of type i. Suppose for all distinct
small intersection with
the simple circuits in fC Ig. Then the fat triangle (;; I) is a minor of (M; ).
(2) Let C 1 be a simple circuit of type 1. Suppose we have a cocircuit D 12 where D 12 \C
D 12 has a small intersection with C 1 . If C 1 f1g [ f2g is dependent then C 1 f1g [ f2g contains
an odd circuit using 2 and the fat triangle (f3g; f2g) is a minor of (M; ).
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 17
(3) Suppose for each we have a simple circuit C i of type i. Suppose we have a cocircuit D 12
where D 12 \C small intersection with C 1 and C 2 . If both C 1 f1g [ f2g
and C 2 f2g [ f1g are independent, then the fat triangle (;; f1; 2g) is a minor of (M; ).
Proof. Throughout the proof distinct elements of C 0 .
Let us prove (1). For each i 2 I let f i be the unique element in C i \. For each D jk either: D jk \C
or D jk \ C is an element not in . Let E 0 be the set of elements in C 0 or in any of C i
(a) If g i exists then f i is in each of D 12 ; D 13 ; D 23 and g i is in D jk but not D ij ; D ik .
(b) If g i does not exists but f i does then f i is in D ij ; D ik but not in D jk .
. Observe that (a) and (b) imply respectively (a') and (b').
(a') If g i exists then f i 62 and g i 2 .
(b') If g i does not exist then f i 2 .
Let (N; ) be the minor of (M; ) obtained by deleting the elements not in E 0 and then contracting the
elements not in C 0 [ . It follows from (a') and (b') that if C 0 is a circuit then (N; ) is the fat triangle
(;; I). Otherwise some element i 2 C 0 is a loop of N , say 1. Then there is a circuit C of M such that
does not intersect D 12 and D 23 with the same
parity. Consider any e 2 C C 0 such that e is in some cocircuit D ij . Since e 62 , it follows from (a') and
(b') that I and that g i exists. But then (a) implies that e 2 D 12 \ D 13 \ D 23 . It follows
that C cannot intersect D 12 and D 23 with the same parity, a contradiction.
Let us prove (2). Let f be the unique element in C 1 \. By hypothesis there is a circuit C in C 1 f1g[
f2g. Since C 1 is a circuit 2 2 C. Since D 12 has a small intersection C 1 \ D fg. It follows that
be the circuit using 3 in C 1 4C4C 0 . Since C 0 is a circuit, 3 is not a loop, hence
contains at least one element say g.
Observe that f2; fg is an odd cycle of (N; ) and that f3; gg and C 0 are even cycles of (N; ). Hence, if C 0 is
a circuit of N then (N; ) is the fat triangle (f3g; f2g). Because D 12 is a cocircuit of M , f1; 2; fg is a cocycle
of N , in particular 1; 2; f are not loops. If 3 is a loop of N then there is a circuit S  C 1 f1; 2; f; gg[ f3g
of (M; ). But C 0 4 S is a cycle and C 0 4 S  C 1 , a contradiction as C 1 is a circuit.
Let us prove (3). Let M 0 be obtained from M by deleting all elements not in C 0 [
small intersection with C 1 and C 2 we have
is a signed minor of (M; ). Choose a minor N of M 0 which is minimal and satisfies the
following properties:
(i) C 0 is a circuit of N ,
there exist circuits C i of N such that C i \C
Note that by hypothesis M satisfies properties (i)-(iv) and thus so does M 0 . Hence N is well defined. We
will show that jC 1 in N . Then (N; f1; 2g) is a minor of (M; ) and after resigning on the
cocircuit containing we obtain the fat triangle (;; f1; 2g). There is no circuit S  C 1 f1g [ f3g of N ,
for otherwise there exists a cycle C 1 4 S 4C 0  C 1 f1g [ f2g, a contradiction with (iii). Hence,
EJOLS AND BERTRAND GUENIN
2. C 1 \ C
Proof of Claim: Otherwise define N 0 := N=(C 1 \ C 2 ). Note that N 0 satisfies (ii)-(iv). Suppose (i) does not
hold for N 0 , i.e. C 0 is a cycle but not a circuit of N 0 . Then 3 is a loop of N 0 . Thus there is S  C 1 \C 2 such
that S [ f3g is a circuit of N , contradicting Claim 1. 3
Assume for a contradiction jC
3. There exists a circuit S  of N .
Proof of Claim: Let e 2 C 1 f1g and consider (N is not a circuit of N 0 .
Then 2 or 3 is a loop of N . But then either f2; eg or f3; eg is a circuit of N . In the former case it contradicts
(iii), in the latter it contradicts Claim 1. Hence (i) holds for N 0 . Trivially (iii) holds for N 0 as well. Suppose
(ii) does not hold, then C 2 is not a circuit of N 0 . It implies there exists a circuit S  C 2 [ feg f2g of N .
Then S is the required circuit. Suppose (iv) does not hold. Then there is a circuit S
N , and S 4 C 1 contains the required circuit. 3
Let S be the circuit in the previous claim. Since C are circuits, S \C 1 are non-empty. Let C 0
2 be
the circuit in C 2 4 S which uses 2. Note that N n (E(N
properties (i)-(iii) using
2 instead of C 2 . Thus, by minimality, (iv) is not satisfied for C 0
contains a circuit C 0
1 .
2 is a circuit, 1 2 C 0
. By the same argument as above, (iii) is not satisfied for C 0
contains a circuit C 00
using 2. Since C 00
it follows that C 00
2 is a circuit). Therefore,
f1g. But the cycle C 0
contradicts the fact that C 0 is a circuit.
Lemma 7.14. Let (M; ) be an ideal signed binary matroid with a circuit C
Suppose we have such that the cut condition is satisfied. Then there exists
Q+ which satisfies the following properties: (i) p 0 satisfies the cut condition; (ii) p 0
and 0g. There is a
-flow
(1) The fat triangle (;; I) is a signed minor of (M; ) and
circuits C such that (C) > 0.
Or after possibly relabeling elements of C 0 we have p 0
(3) The fat triangle (f3g; f2g) is a signed minor of (M; ) and
(4) for all odd circuits C with (C) > 0 and C \ C
contains an odd circuit using 2.
Proof.
Claim 1. We can assume that there exists Q+ such that properties (i)-(iii) hold. For distinct
be the minimum of p 0 (D jg. We then have
(after possibly relabeling the elements of C 0 ) the following cases, either: (a)
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 19
Proof of Claim: Choose which satisfies the following prop-
erties: the cut condition holds for
(i)-(iii) holds for p 0 . Suppose (a) does not hold. Then we may assume (after relabeling) that  23 > 0 and that
Consider first the case where  12 > 0. Then 2 is in no tight cocircuit, it follows from the choice of p 0
that then for all circuits C such that
holds. Moreover, (1) is satisfied since (M; )n(E(M ) C 0 ) is the
Thus we may assume  relabeling 2 and 3 we satisfy (b).
Hence we can assume  is in no tight cocircuit, thus p 0
holds. Thus we may assume  defined as
hold for ^
p. Suppose
p(3). Thus we may assume for each distinct there is a
cocircuit D where D \ C which is tight for
p. It follows that (a) holds. 3
Throughout the proof distinct elements of C 0 . Let p 0 be the costs given in Claim 1.
implies that there is a -flow,
ij be the cocircuits of M for which D ij \ C
Consider first case (a) of Claim 1, i.e. D ij is tight for all distinct We will show that (1) and
(2) hold. Let C be any circuit with (C) > 0. Then jC 1. Suppose there is an element i in C 0 \ C .
Proposition 4.3 states C is the unique element in C \ .
Thus C \ C is in a tight cocircuit, thus if p 0 (i) > 0 then
there is a circuit C i with Moreover, (2) implies that C i is a simple circuit of type i.
Proposition 4.3 implies that D 12 ; D 13 ; D 23 all have small intersections with each of the simple circuits. Then
(1) follows from Proposition 7.13(1).
Consider case (b) of Claim 1, i.e.
2. Let C be a circuit with (C) > 0. If i 2 C \ f1; 2g, then C i is a simple circuit of type i.
This follows from the fact that 3 62 C (as p 0 and that jC \ f1; (because of Proposition 4.3
and the fact that D 12 is tight). The case where p 0 has already been considered (see proof
of Claim 1). Suppose for some f be the unique element in
. The minor (M; )n(E(M is the fat triangle (;; fig) and both (1) and
(2) hold. Thus p 0 (1) > 0; p 0 (2) > 0. Suppose now for all i 2 f1; 2g there exists a circuit C i with
states that these circuits are simple circuits
of type i. Then (2) holds and Proposition 7.13(3) implies that (M; ) contains the fat triangle (;; f1; 2g), i.e.
(1) holds. Thus we may assume, for some i 2 f1; 2g that for all circuits C i such that (C i
dependent. If interchange the labels 2 and 1. Since we had
we get in that case p 0 (2)
Proposition 7.13(2) implies that for all circuits C 1 with contains an
odd circuit using 1 and that (M; ) contains the fat triangle (f3g; f2g) as a minor. Together with
this implies (3) and (4) hold.
EJOLS AND BERTRAND GUENIN
We are now ready for the proof of the main lemma.
Proof of Lemma 7.3. Since M has a strict 3-separation,
a triangle. Throughout this proof i; j; k will denote distinct elements of C 0 . Recall that F  E 1 . Let  1
denote the smallest value of
some cocircuit of M 1 with D ij \ C jg. Expression (*) gives the difference between
the sum of the capacity elements and the sum of the demand elements in D ij , excluding the marker C 0 .
Denote by D 1
ij the cocircuit for which the minimum is attained in (*). Let  2
ij denote the smallest value of
some cocircuit of M 2 with jg. In what follows, we let D 2
the cocircuit for which p(D 2
ij . For each
Proof of Claim: We have  2
jk . Thus
2.  1
Proof of Claim:  1
But the last expression is non negative since the cut condition holds for (M; F; p). 3
signed minor of (M; F ).
Proof of Claim: Theorem 5.2 implies that M 1 is a minor of M obtained by contracting and deleting elements
in
4. The cut condition is satisfied for
Proof of Claim: Since the cut condition holds for (M; F; p) the cut condition is satisfied for all cocircuits of
1 disjoint from C 0 . Let D be a cocircuit of M 1 such that D\C
ij . It follows
from Claim 2 that the previous expression is non-negative. 3
implies that (M 1 of (M; F ) and hence its clutter of odd circuits is ideal. Together with
implies that (M 1 the hypothesis of Lemma 7.14. It follows that M 1 is F -flowing
with costs p 0
1 is as described in the lemma) and either case 1 or case 2 occurs.
Case 1: Statements (1) and (2) hold.
We define I :=
5. (M 0
is a signed minor of (M; F ).
Proof of Claim: Statement (1) says that the fat triangle (;; I) is a signed minor of (M is equal to
showed that (M3 M 2 ) nJ d =J
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 21
6. The cut condition is satisfied for (M 0
Proof of Claim: It suffices to show the cut condition holds for cocircuits D that intersect C 0 . Suppose D \
states that p 0
ij .
Thus
implies that (M 0
is a part of (M; F ) and hence its clutter of odd circuits is ideal. It follows
from Claim 6 and Corollary 4.4(i) that M 0
2 is I-flowing with costs p 2 . Since we can scale p (and hence p 0
1 and
may assume that the F -flow of M 1 satisfying costs p 0
1 is a multiset L 1 of circuits and that the I-flow
of M 0
satisfying costs p 2 is a multiset L 2 of circuits. Because of Statement (2), L 1 can be partitioned into L 1and L 1

. Because
can be partitioned into L 2

1 (i) for each i 2 I, jL 1
us define a collection of circuits of M
as follows: include all circuits of L 1
, and for every i 2 I pair each circuit C
i with a different circuit
and add to the collection the circuit included in C 1 4C 2 that contain the element of F . The resulting
collection corresponds to a F -flow of M satisfying costs p.
Case 2:
statements (3) and (4) hold (after possibly relabeling C 0 ).
that the fat triangle (f3g; f2g) is a signed minor of (M 1 ; F ).
Proceeding as in the proof of Claim 5 we obtain the following.
7. (M 0
is a signed minor of (M; F ).
1 (1) and
8. The cut condition is satisfied for (M 0
Proof of Claim: Consider first a cocircuit D of M 0
2 such that D \ C 3g. Let us check D does not
violate the cut condition. The following expression should be non negative: p 2 (D f2g) p 2 (D \
states
Consider a cocircuit D of M 0
2 such that 2 2 D but 3 62 D. Let us check D does not violate the cut condition.
The following expression should be non negative: p 2 (D f2g) p 2 (D \
is a cocircuit of M 2 ,
It follows that p(D C 0
imply that M 0
2 is f2g-flowing with costs p 2 . We may assume that
the F -flow of M 1 satisfying costs p 0
1 is a multiset L 1 of circuits. Because of Statement (4), L 1 can be
partitioned into L 1
. We may assume that the f2g-flow of M 0
satisfying costs p 2 is a multiset
L 2 of circuits. Since C 2 L 2 implies Cf2g and since 1 62 E(M 0
can be partitioned into L 2
, and L 2
22 G -
EJOLS AND BERTRAND GUENIN
9. (i) jL 1
j.
Proof of Claim: Let us prove (i). 2 is a demand element for the flow L 2 , thus jL 2
(2). 3 is a capacity element for the flow L 2 , thus jL 2
where the last inequality follows from the fact that 2 is a capacity element for the flow L 1 . Let us prove (ii).
Let us define a collection of circuits of M as follows: (a) include all circuits of L 1
every circuit
2 with a different circuit C
- such a pairing exists because of Claim 9(i) - and add to the
collection pair as many circuits C 1 of L 1
1 to as many different circuits C 2 of L 2
1 as possible, and
add to the collection C 1 remaining circuits C 1 of L 1
1 to circuits of L 2
not already used in (b).
Such a pairing exists because of Claim 9(ii). Statement (4) says that C 1 f1g [ f2g contains an odd circuit
1 . For every pair C add to the collection the cycle C 0
for each cycle C in the collection
only keep the circuit included in C that contains the element of F . The resulting collection corresponds to an
F -flow of M satisfying costs p.
8. SUFFICIENT CONDITIONS FOR IDEALNESS
We will prove Theorem 1.1 in this section, i.e. that a binary clutter is ideal if it has none of the following
minors: LF7 , OK5 , b(OK5
6 and Q
7 . The next result is fairly straightforward.
Proposition 8.1 (Novick and Seb-o [20]).
H is a clutter of odd circuits of a graph if and only if u(H) is graphic.
H is a clutter of T -cuts if and only if u(H) is cographic.
Remark 8.2. The class of clutters of odd circuits and the class of clutters of T -cuts is closed under minor
taking.
This follows from the previous proposition, Remark 2.9 and the fact that the classes of graphic and cographic
matroid are closed under taking (matroid) minors. We know from Remark 3.4 that b(Q 6
is a source of F 7 , and Q
6 is a source of F
7 . Thus Proposition 8.1 implies,
Remark 8.3. Q
7 and Q
6 are not clutters of odd circuits or clutters of T -cuts.
We use the following two decomposition theorems.
Theorem 8.4 (Seymour [24]). Let M be a 3-connected and internally 4-connected regular matroid. Then
is graphic or M is cographic.
Theorem 8.5 (Seymour [24, 26]). Let M be a 3-connected binary matroid with no F
Then M is regular or
Corollary 8.6. Let H be a binary clutter such that u(H) has no F
7 minor. If H is 3-connected and internally
4-connected, then H is one of b(Q 7 or one of the 6 lifts of R 10 , or a clutter of odd circuits or
a clutter of T-cuts.
IDEAL BINARY CLUTTERS, CONNECTIVITY, AND A CONJECTURE OF SEYMOUR 23
Proof. Since H is 3-connected, u(H) is 3-connected. So, by Theorem 8.5, u(H) is regular or In
the latter case, Remark 3.4 implies that H is one of b(Q 7 . Thus we can assume that u(H) is
regular. By hypothesis, u(H) is internally 4-connected and therefore, by Theorem 8.4,
is graphic or u(H) is cographic. Now the corollary follows from Proposition 8.1 and Remark 3.4.
We are now ready for the proof of the main result of this paper.
Proof of Theorem 1.1. We need to prove that, if H is nonideal, then it contains LF7 , OK5 , b(OK5
6 or
7 as a minor. Without loss of generality we may assume that H is minimally nonideal. It follows from
Remark 5.3 and propositions 6.1 and 7.1 that H is 3-connected and internally 4-connected. Consider first the
case where u(H) has no F
7 minor. Then, by Corollary 8.6 either: (i) H is one of b(Q 7
(ii) H is one of the 6 lifts of R 10 , or (iii) H is a clutter of odd circuits, or (iv) H is a clutter of T-cuts. Since H
is minimally nonideal, it follows from Proposition 3.5 that if (i) occurs then occurs then
occurs then, by Theorem 1.3, occur because of Theorem 1.4.
Now consider the case where u(H) has an F
7 minor. It follows by Theorem 3.2 that H has a minor H 1
a source of F
7 and H 2 is a lift of F
7 . Proposition 3.1 states that the lifts of F
7 are the
blockers of the sources of F 7 . Remark 3.4 states that the sources of F 7 are b(Q 7 ), LF7 or b(Q 6 that
F
7 has only one source, namely Q
6 . This implies that H
6 and H
7 or b(LF7 )
has an LF7 minor and b b(Q
has a Q
6 minor, the proof of the theorem is complete.
One can obtain a variation of Theorem 1.1 by modifying Corollary 8.6 as follows: Let H be a binary
clutter such that u(H) has no F 7 minor. If H is 3-connected and internally 4-connected, then H is b(Q 7 ),
6 ) or one of the 6 lifts of R 10 or a clutter of odd circuits or a clutter of T-cuts. Following the proof
of Theorem 1.1, this yields: A binary clutter is ideal if it does not have an LF7 , OK5 , b(OK5
minor. But this result is weaker than Corollary 1.2. Other variations of Theorem 1.1 can be obtained
by using Seymour's Splitter Theorem [24] which implies, since u(H) is 3-connected and u(H) 6= F
7 , that
u(H) has either S 8 or AG(3; 2) as a minor. Again, by using Proposition 3.2, we can obtain a list of excluded
minors that are sufficient to guarantee that H is ideal.
9. SOME ADDITIONAL COMMENTS
Corollary 8.6 implies the following result, using the argument used in the proof of Theorem 1.1.
Theorem 9.1. Let H be an ideal binary clutter such that u(H) has no F
7 minor. If H is 3-connected and
internally 4-connected, then H is one of b(Q 7 or one of the 5 ideal lifts of R 10 , or a clutter of odd
circuits of a weakly bipartite graph, or a clutter of T-cuts.
A possible strategy for resolving Seymour's Conjecture would be to generalize this theorem by removing
the assumption that u(H) has no F
7 minor, while allowing in the conclusion the possibility for H to also be
a clutter of T-joins or the blocker of a clutter of odd circuits in a weakly bipartite graph. However, this is not
possible as illustrated by the following example.
EJOLS AND BERTRAND GUENIN
Let T 12 be the binary matroid with the following partial representation.6 6 4
This matroid first appeared in [11]. It is self dual and satisfies the following properties:
(i) For every element t of T 12 , T 12 =t is 3-connected and internally 4-connected.
(ii) For every element t of T 12 , T 12 =t is not regular.
We are indebted to James Oxley (personal communication) for bringing to our attention the existence of
the matroid T 12 and pointing out that it satisfies properties (i) and (ii). Let t be any element of T 12 and let
Because of (i), T 12 3-connected and internally 4-connected and thus so is H.
Because of (ii), T 12 not graphic or cographic thus Proposition 8.1 implies that H is not a clutter
of T -cuts and not a clutter of odd circuits. We know from Proposition 2.12 that
Thus, b(H) is also 3-connected, internally 4-connected, and H is not the clutter of T -joins or
the blocker of the clutter of odd circuits. However, it follows from the results of Luetolf and Margot [16] that
the clutter H is ideal.



--R

On the length-width inequality for compound clutters
Combinatorial designs and related systems.
A decomposition for combinatorial geometries.
Composition for matroids with the Fulkerson property.

Euler tours and the chinese postman.
Blocking and anti-blocking pairs of polyhedra
Graphs and polyhedra

A characterization of weakly bipartite graphs.
A generalization of a graph result of D.
Graphic programming using odd or even points (in chinese).
A solution of the Shannon switching game.
On the width-length inequality
On the width-length inequality and degenerate projective planes
A catalog of minimally nonideal matrices.
The anti-join composition and polyhedra
Polyhedral properties of clutter amalgam.
Composition operations for clutters and related polyhedra.
On combinatorial properties of binary spaces.
Matroid Theory.
Lehman's forbidden minor characterization of ideal 0 1 matrices.
The Matroids with the Max-Flow Min-Cut property
Decomposition of regular matroids.
A note on the production of matroid minors.
European J.
On Lehman's width-length characterization
Signed graphs.
Biased graphs.
--TR

--CTR
Bertrand Guenin, Integral Polyhedra Related to Even-Cycle and Even-Cut Matroids, Mathematics of Operations Research, v.27 n.4, p.693-710, November 2002
Grard Cornujols , Bertrand Guenin, Ideal clutters, Discrete Applied Mathematics, v.123 n.1-3, p.303-338, 15 November 2002
ideal clutter;signed matroid;connectivity;multicommodity flow;t-cut;seymour's conjecture;weakly bipartite graph;separation