A SHARP BOUND ON THE SIZE OF A CONNECTED MATROID

MANOEL LEMOS AND JAMES OXLEY

Abstract. This paper proves that a connected matroid M whose largest circuit and largest cocircuit have c and c^{∗} elements, respectively, has at most \frac{1}{2} cc^{∗} elements. It is also shown that if e is an element of M and c_{e} and c_{e}^{∗} are the sizes of a largest circuit containing e and a largest cocircuit containing e, then |E(M)| ≤ (c_{e} − 1)(c_{e}^{∗} − 1) + 1. Both these bounds are sharp and the first is proved using the second. The second inequality is an interesting companion to Lehman’s width-length inequality which asserts that the former inequality can be reversed for regular matroids when c_{e} and c_{e}^{∗} are replaced by the sizes of a smallest circuit containing e and a smallest cocircuit containing e. Moreover, it follows from the second inequality that if u and v are distinct vertices in a 2-connected loopless graph G, then |E(G)| cannot exceed the product of the length of a longest (u, v)-path and the size of a largest minimal edge-cut separating u from v.

1. Introduction

At the 1991 Seattle conference on graph minors, Robin Thomas informally asked the question as to whether every sufficiently large connected matroid has a big circuit or a big cocircuit. This question was rapidly answered at that meeting by Lovász, Schrijver, and Seymour (see [9]) who proved the following result. 1.1. Theorem. Let M be a connected matroid with at least two elements. If a largest circuit of M has c elements and a largest cocircuit has c^{∗} elements, then M has at most 2^{c+c^{∗}−1} elements.

An affirmative answer to Thomas’s question can also be obtained from a result of Tuza [15] for set systems. In response to Theorem 1.1, a natural question is whether the bound in the theorem can be improved, particularly if attention is restricted to certain special classes of matroids. For graphic matroids, the following dramatic improvement was found by Pou-Lin Wu [16]. 1.2. Theorem. Let G be a loopless 2–connected graph in which a largest cycle has c edges and a largest bond has c^{∗} edges. Then G has at most \frac{1}{2} cc^{∗} edges.

Of course, c is just the circumference of the graph G. There is a wide gap between the graph bound in Theorem 1.2 and the general matroid bound in Theorem 1.1. Reid [11] partially closed this gap. He defined the matroid Ramsey number n(s, t) to be the least positive integer n so that every n–element connected matroid has a circuit of size at least s or a cocircuit of size at least t. Reid showed that n(s, t) has several attractive properties that are analogous to properties of the classical Ramsey numbers for graphs established by Erdős and Szekeres [3]. Using these, Reid proved the following improvement of Theorem 1.1.

1991 Mathematics Subject Classification. 05B35.

1.3. Theorem. If M is a connected matroid with largest circuit of size c and largest cocircuit of size c^{∗}, then

|E(M)| ≤ \binom{c + c^{∗} − 2}{c − 1} − 2

provided both c and c^{∗} exceed three.

Reid [11] and Hurst and Reid [5] also determined some small matroid Ramsey numbers including all n(s, t) with s or t at most three.

The purpose of this paper is to prove that the bound that Pou-Lin Wu proved for graphic matroids also holds for matroids in general. The following is our main result. 1.4. Theorem. Let M be a connected matroid with at least two elements. If a largest circuit of M has c elements and a largest cocircuit has c^{∗} elements, then

|E(M)| ≤ ⌊\frac{cc^{∗}}{2} ⌋ .

This theorem solves a problem raised by Oxley [10] and settles a conjecture of Bonin, McNulty, and Reid [1]. For comparison, a lower bound on |E(M)| in terms of c and c^{∗} that holds for all matroids M having non-zero rank and corank is

c + c^{∗} − 2 ≤ |E(M)|.  (1)

To see this, observe that c ≤ r(M) + 1 and c^{∗} ≤ r^{∗}(M) + 1. The bound in (1) is sharp. It is attained by, for example, the whirls, all uniform matroids of non-zero rank and corank, and, more generally, by all matroids with both a free element and a cofree element.

The proof of Theorem 1.4 will use another bound that is of independent interest. 1.5. Theorem. Let M be a connected matroid with at least two elements and let e be an element of M. If a largest circuit of M containing e has c_{e} elements and a largest cocircuit containing e has c_{e}^{∗} elements, then

|E(M)| ≤ (c_{e} − 1)(c_{e}^{∗} − 1) + 1.

The last theorem has an attractive similarity to a bound derived from the widthlength inequality [7, 4]. In a matroid M, let e be an element that is neither a loop nor a coloop. Let λ(M) + 1 and ω(M) + 1 be the cardinalities of a smallest circuit containing e and a smallest cocircuit containing e. Lehman [7] showed that if M is regular, then

λ(M)ω(M) ≤ |E(M)| − 1.  (2)

More generally, it follows from a result of Seymour [12] that the last inequality holds for all binary matroids that have no F_{7}^{∗}-minor using e. In fact, it also holds for F_{7}^{∗}, although it fails, for example, for AG(3, 2).

A straightforward consequence of Theorem 1.5 is the following result for graphs. 1.6. Corollary. Let u and v be distinct vertices in a 2-connected loopless graph G. Then |E(G)| cannot exceed the product of the length of a longest (u, v)-path and the size of a largest minimal edge-cut separating u from v.

The bounds in Theorems 1.2, 1.4, and 1.5 are sharp. Pou-Lin Wu [17] determined all graphs that attain the bound in Theorem 1.2. The cycle matroid of each such graph attains the bound in Theorem 1.4 provided c or c^{∗} is even. A non-graphic matroid attaining the bound in Theorem 1.4, which was noted by Reid [11], is AG(3, 2). In Section 4, we shall describe all the matroids that attain the bound in Theorem 1.5, noting that there is a close link between these matroids and those found by Wu.

The matroid terminology used here will follow Oxley [9]. In particular, the set of circuits of a matroid M will be denoted by C(M). Theorem 1.5 will be deduced in the next section from a stronger result, while Theorem 1.4 will be proved in Section 3.

2. Two strengthenings of Theorem 1.5

Let e be an element of a matroid M and suppose that e is not a coloop of M. We define the circumference of M through e by

c_{e}(M) = max{|C| : e ∈ C ∈ C(M)},

that is, c_{e}(M) is the size of a largest circuit that contains e. If f is an element of M that is not a loop, we define c_{f}^{∗}(M) = c_{f}(M^{∗}). The circumference c(M) of a non-free matroid is the size of a largest circuit of M. If r(M) > 0, we define c^{∗}(M) = c(M^{∗}).

Let C be a circuit of a matroid M. A subset P of E(M) − C is a chord of C if P ∈ C(M/C) − C(M). Equivalently, P is a chord of C if and only if P is disjoint from C and M|(C ∪ P) is a connected matroid having corank two. In particular, when P is a chord of C, it is a series class of M|(C ∪ P).

The first strengthening of Theorem 1.5 will require some more preliminaries. Let L be a subset of the ground set of a matroid M and suppose that L is the union of a set of circuits of M and r^{∗}(M|L) = 2. Then L is what Tutte [14] has called a “line” of M. We shall call L a Tutte-line since the word “line” is also commonly used in matroid theory to mean a rank-2 flat. It is not difficult to see that every Tutte-line L of a matroid M has a canonical partition {L_{1}, L_{2}, …, L_{k}} such that a subset C of L is a circuit of M|L if and only if C = L−L_{i} for some i in {1, 2, …, k}. A Tutte-line L is connected if M|L is a connected matroid. The size of a Tutte-line is the number of sets in its canonical partition. Hence a Tutte-line is connected if and only if it has size at least three. 2.1. Theorem. Let M be a connected matroid such that |E(M)| > 1 and let e be an element of M. Then

|E(M)| ≤ c_{e}(M) + \frac{1}{m − 2}(c_{e}(M) − 1)(c_{e}^{∗}(M) − 2)

for all integers m exceeding two such that every connected Tutte-line of M has size at least m.

The dual of this theorem can be restated using the concept of a coline of a matroid, a flat of rank two less than the matroid. 2.2. Corollary. Let M be a connected matroid such that |E(M)| > 1 and let e be an element of M. Suppose that m is an integer exceeding two such that every coline of M that is contained in more than two hyperplanes is contained in at least m hyperplanes. Then

|E(M)| ≤ c_{e}^{∗}(M) + \frac{1}{m − 2}(c_{e}^{∗}(M) − 1)(c_{e}(M) − 2).

Proof of Theorem 1.5. In all connected matroids with at least two elements, every connected Tutte-line has size at least three. The theorem follows immediately by taking m = 3 in Theorem 2.1. □

Proof of Corollary 1.6. Add the edge e to G so that it joins u and v. Then the result follows immediately from Theorem 1.5. □

Proof of Theorem 2.1. We argue by induction on |E(M)| noting that the result holds when |E(M)| = 2. Assume it holds for |E(M)| < k and let |E(M)| = k ≥ 3. Choose a circuit C of M such that e ∈ C and |C| = c_{e}(M). Observe that the result holds when E(M) = C. Thus we may suppose that E(M) ≠ C. Let M_{1}, M_{2}, …, M_{n} be the connected components of M/C.

For each element f of C − e, consider the connected component N_{f} of M/(C − {e, f}) that contains f. There is a set P_{f} of matroids such that

(i) N_{f} is the parallel connection of the matroids in P_{f} across the basepoint e; and

(ii) N/e is connected for every N in P_{f}. Observe that {e, f} is the ground set of a matroid that belongs to P_{f}. For each matroid N in P_{f}, let C_{N}^{∗} be a cocircuit of N such that e ∈ C_{N}^{∗} and |C_{N}^{∗}| = c_{e}^{∗}(N). Let

C^{∗} = ⋃_{N∈P_{f}} C_{N}^{∗}.

Then C^{∗} contains e and is a cocircuit of N_{f} and hence of M. Thus

c_{e}^{∗}(M) ≥ |C^{∗}| = 1 + ∑_{N∈P_{f}}(c_{e}^{∗}(N) − 1).  (3)

For each f in C − e, view the set P_{f} as a multiset and let P be the multiset that is the union of all these multisets. For each i in {1, 2, …, n}, let Q_{i} be the multiset of matroids N in P for which N/e = M_{i}. Then P is the union of the multisets Q_{1}, Q_{2}, …, Q_{n} together with |C| − 1 copies of U_{1,2}, the ground sets of the latter being all sets of the form {e, f} such that f ∈ C − e. For all i in {1, 2, …, n}, let N_{i} be a matroid in Q_{i} for which

c_{e}^{∗}(N_{i}) = min{c_{e}^{∗}(N) : N ∈ Q_{i}}.  (4)

On summing (3) over all f in C − e, we get

(|C| − 1)c_{e}^{∗}(M) ≥ (|C| − 1) + ∑_{f∈C−e} ∑_{N∈P_{f}}(c_{e}^{∗}(N) − 1).

Therefore

(|C| − 1)c_{e}^{∗}(M) ≥ (|C| − 1) + [(|C| − 1) + ∑_{i=1}^{n} ∑_{N∈Q_{i}}(c_{e}^{∗}(N) − 1)] ,  (5)

where the extra (|C| − 1)-term appears because, for every f in C − e, there is a matroid belonging to P_{f} having ground set {e, f} and this matroid does not belong to any Q_{i}. Hence

(|C| − 1)(c_{e}^{∗}(M) − 2) ≥ ∑_{i=1}^{n} |Q_{i}|(c_{e}^{∗}(N_{i}) − 1).  (6)

As |C| = c_{e}(M), it follows that

(c_{e}(M) − 1)(c_{e}^{∗}(M) − 2) ≥ ∑_{i=1}^{n} |Q_{i}|(c_{e}^{∗}(N_{i}) − 1).  (7)

Next we obtain, for each i in {1, 2, …, n}, a lower bound on |Q_{i}|. Let P_{i} be a subset of E(M_{i}) such that P_{i} ∪ e is a circuit of N_{i} of size c_{e}(N_{i}). Thus

|P_{i}| = c_{e}(N_{i}) − 1.  (8)

Moreover, P_{i} is a chord of C, so C ∪ P_{i} is a connected Tutte-line L_{i} of M. Let {P_{i}, L_{i1}, L_{i2}, …, L_{in_{i}}} be the canonical partition of L_{i}. Without loss of generality, we may assume that e ∈ L_{in_{i}}. For all j in {1, 2, …, n_{i} − 1}, the set L_{i} − L_{ij} is a circuit of M containing e. Thus

|C| ≥ |L_{i} − L_{ij}| = |L_{i}| − |L_{ij}|.

But

|C| = |L_{i} − P_{i}| = |L_{i}| − |P_{i}|.

Hence

|P_{i}| ≤ min{|L_{ij}| : 1 ≤ j ≤ n_{i} − 1}.  (9)

For all f in ⋃_{j=1}^{n_{i}−1} L_{ij}, since M_{i} and N_{f} are the connected components of M/C and M/(C − {e, f}), respectively, containing P_{i}, we deduce that E(M_{i}) ⊆ E(N_{f}) and therefore P_{f} contains a member N of Q_{i}. Thus

|Q_{i}| ≥ ∑_{j=1}^{n_{i}−1} |L_{ij}| ≥ (n_{i} − 1)|P_{i}|,  (10)

where the second inequality follows by (9). Moreover, since C ∪ P_{i} is a connected Tutte-line of M of size n_{i} + 1, we have n_{i} + 1 ≥ m. Hence, using (10) and (8), we deduce that

|Q_{i}| ≥ (m − 2)|P_{i}| = (m − 2)(c_{e}(N_{i}) − 1).  (11)

On combining (7) and (11), we get

(c_{e}(M) − 1)(c_{e}^{∗}(M) − 2) ≥ ∑_{i=1}^{n}(m − 2)(c_{e}(N_{i}) − 1)(c_{e}^{∗}(N_{i}) − 1).  (12)

As 2 ≤ |E(N_{i})| < |E(M)|, the theorem holds for N_{i}. In particular, since every connected Tutte-line of N_{i} has size at least three, it follows that

|E(N_{i})| ≤ c_{e}(N_{i}) + (c_{e}(N_{i}) − 1)(c_{e}^{∗}(N_{i}) − 2).

But |E(M_{i})| = |E(N_{i})| − 1, so

|E(M_{i})| ≤ (c_{e}(N_{i}) − 1)(c_{e}^{∗}(N_{i}) − 1).  (13)

On combining (12) and (13), we get

(c_{e}(M) − 1)(c_{e}^{∗}(M) − 2) ≥ ∑_{i=1}^{n}(m − 2)|E(M_{i})|

≥ (m − 2) ∑_{i=1}^{n} |E(M_{i})| = (m − 2)|E(M) − C|.

Rewriting the last inequality, using the fact that c_{e}(M) = |C|, we obtain

|E(M)| ≤ c_{e}(M) + \frac{1}{m − 2}(c_{e}(M) − 1)(c_{e}^{∗}(M) − 2)

and the theorem follows by induction. □

As an immediate consequence of Corollary 2.2, we have the following result.

2.3. Corollary. Let M be a connected matroid such that |E(M)| > 1. Suppose that m is an integer exceeding two such that every coline of M that is contained in more than two hyperplanes is contained in at least m hyperplanes. Then

|E(M)| ≤ c^{∗}(M) + \frac{1}{m − 2}(c^{∗}(M) − 1)(c(M) − 2).

The bound in the last inequality is sharp, it being attained for every m ≥ 3 by U_{n−m+2,n} provided n ≥ m − 1.

After the original submission of this paper, Guoli Ding (private communication) gave a short proof of Theorem 1.5. A straightforward modification of his argument yields our second strengthening of Theorem 1.5. This result answers a question of Paul Seymour (private communication). 2.4. Theorem. Let M be a connected matroid with at least two elements and let e be an element of M. Then there are c_{e}(M) − 1 cocircuits of M each containing e such that the union of these cocircuits is E(M).

Proof. We argue by induction on c_{e}(M). If c_{e}(M) = 2, then M is a uniform matroid having rank one, so E(M) is a cocircuit of M and the result follows. Now suppose that the theorem holds for c_{e}(M) < n and let c_{e}(M) = n ≥ 3.

Let C^{∗} be a cocircuit of M that contains e. Clearly C^{∗} ≠ E(M). By a wellknown result of Tutte [14] (see also [9, Theorem 4.3.1]), for every element z of a connected matroid, the deletion or contraction of z leaves a connected matroid. Thus there is a partition {X, Y } of C^{∗}−e such that M\X/Y is a connected matroid; call it N. As every circuit of M that contains e must also meet X or Y, it follows that

c_{e}(N) < c_{e}(M).

Since C^{∗} ≠ E(M), the matroid N has at least two elements. Thus, by the induction assumption, for some k ≤ c_{e}(N) − 1, there are k cocircuits C_{1}^{∗}, C_{2}^{∗}, …, C_{k}^{∗} of N each containing e such that the union of these cocircuits is E(N). For each C_{i}^{∗}, there is a cocircuit D_{i}^{∗} of M such that C_{i}^{∗} = D_{i}^{∗} − X. Hence C^{∗}, D_{1}^{∗}, D_{2}^{∗}, …, D_{k}^{∗} are cocircuits of M each containing e and

E(M) = E(N) ∪ X ∪ Y ⊆ C_{1}^{∗} ∪ C_{2}^{∗} ∪ ⋯ ∪ C_{k}^{∗} ∪ C^{∗} ⊆ D_{1}^{∗} ∪ D_{2}^{∗} ∪ ⋯ ∪ D_{k}^{∗} ∪ C^{∗}.

Thus we have a family of k + 1 cocircuits of M that covers E(M). Since

k + 1 ≤ (c_{e}(N) − 1) + 1 = c_{e}(N) ≤ c_{e}(M) − 1,

the result follows by induction. □

We observe, from the last proof, that the family of c_{e}(M) − 1 cocircuits that covers E(M) can be required to include any arbitrarily chosen cocircuit of M that contains e.

3. Proof of Theorem 1.4

In this section, we shall prove Theorem 1.4. In addition to Theorem 1.5, the proof will use two lemmas and we begin the section by proving them. For a circuit C of a matroid M such that |C| ≥ 2, we define

c^{∗}(C, M) = max{|D^{∗}| : D^{∗} ∈ C(M^{∗}) and |D^{∗} ∩ C| = 2}.

3.1. Lemma. Suppose that M is a connected matroid having a circuit C such that every connected component of M/C is a circuit. If |E(M)| > 1, then

|E(M)| ≤ |C| + c(M) ⌈\frac{c^{∗}(C, M) − 2}{2}⌉ .  (∗)

Proof. Suppose that (∗) is false and choose a counterexample M such that |E(M)| is minimum. Observe that E(M) ≠ C, otherwise (∗) holds. Suppose that M/e is connected for some e in C. Observe that |E(M/e)| > 1 because E(M) ≠ C. As M/C = (M/e)/(C − e), it follows that the result holds for the pair (M/e, C − e), by the choice of (M, C). In particular,

|E(M/e)| ≤ |C − e| + c(M/e) ⌈\frac{c^{∗}(C − e, M/e) − 2}{2}⌉ .

Observe that c(M/e) ≤ c(M) and c^{∗}(C − e, M/e) ≤ c^{∗}(C, M). Hence

|E(M)| − 1 ≤ |C| − 1 + c(M) ⌈\frac{c^{∗}(C, M) − 2}{2}⌉

and we obtain the contradiction that (∗) holds for M. Thus M/e is disconnected for every e in C.

For all e in C, let P_{e} be a chord of C such that P_{e} is the ground set of a connected component of M/e. If possible, choose the chords P_{e} such that P_{a} ≠ P_{b} for every 2-element subset {a, b} of C. Suppose that this choice is impossible. Then P_{a} = P_{b} for some distinct a and b in C. Therefore both P_{a} ∪ a and P_{a} ∪ b are circuits of M. Thus if x ∈ P_{a}, then M has a circuit contained in (P_{a} − x) ∪ {a, b}. Suppose that {a, b} is a proper subset of C. Then, since P_{a} − x is independent in M/C, it follows that (P_{a} − x) ∪ {a, b} is independent in M; a contradiction. We conclude that C = {a, b}. Moreover, since, by hypothesis, P_{a} and P_{b} cannot be chosen to be different, M is the cycle matroid of the graph consisting of two vertices that are joined by a, b, and a path with edge set P_{a}. Thus

|E(M)| = |C| + |P_{a}| = 2 + |P_{a}|,

c^{∗}(C, M) = 3, and c(M) = |P_{a}| + 1. Therefore

|C| + c(M) ⌈\frac{c^{∗}(C, M) − 2}{2}⌉ = 2 + c(M) = 3 + |P_{a}|

and we obtain the contradiction that (∗) holds for M.

We now know that if a and b are distinct elements of C, then P_{a} ≠ P_{b}. It follows that M|[C ∪(⋃_{e∈C} P_{e})] is the cycle matroid of the graph that can be obtained from a cycle with edge set C by adding an edge e′ in parallel with each edge e and then subdividing e′ to produce a path with edge set P_{e}. Hence if C′ = ⋃_{e∈C} P_{e}, then C′ is a circuit of M, so

|C′| ≤ c(M).  (14)

Moreover, M\C′ is connected. Now, suppose that D^{∗} is a cocircuit of M such that |D^{∗} ∩ C| = 2, say D^{∗} ∩ C = {a, b}. Observe that D^{∗} must intersect P_{a} and P_{b} because P_{a} ∪ a and P_{b} ∪ b are circuits of M. Thus

c^{∗}(C, M\C′) ≤ c^{∗}(C, M) − 2.  (15)

By the choice of M, inequality (∗) holds for the pair (M\C′, C), that is,

|E(M\C′)| ≤ |C| + c(M\C′) ⌈\frac{c^{∗}(C, M\C′) − 2}{2}⌉ .

As c(M\C′) ≤ c(M), it follows using (15) that

|E(M)| − |C′| ≤ |C| + c(M) ⌈\frac{c^{∗}(C, M) − 4}{2}⌉ .

Hence

|E(M)| ≤ |C| + c(M) ⌈\frac{c^{∗}(C, M) − 2}{2}⌉ + |C′| − c(M)
≤ |C| + c(M) ⌈\frac{c^{∗}(C, M) − 2}{2}⌉ .

The last inequality, which holds by (14), gives the contradiction that the lemma holds for M. □

3.2. Lemma. Suppose that M is a connected matroid such that |E(M)| > 1. If C is a circuit of M such that |C| = c(M), then

|E(M)| ≤ c(M) ⌈\frac{c^{∗}(C, M)}{2}⌉ .  (∗∗)

Proof. Let M_{1}, M_{2}, …, M_{n} be the connected components of M/C. Suppose that (∗∗) is false and choose a counterexample M in which the number of M_{i} that are not circuits is a minimum. This number is non-zero, otherwise we get a contradiction to Lemma 3.1. In particular, E(M) ≠ C and we may assume that M_{1} is not a circuit.

Let P be a chord of C that is contained in E(M_{1}). Fix a circuit C_{1} of M|(C ∪P) such that C_{1} − C = P. Observe that, since P is a series class of M|(C ∪ P), this matroid has a circuit D_{1} containing P ∪ (C − C_{1}). Then |C_{1}| + |D_{1}| ≤ 2|C|. Moreover, |C_{1}| = |P | + |C ∩ C_{1}| and |D_{1}| ≥ |P | + |C − C_{1}|. Therefore

|P | + |C ∩ C_{1}| + |P | + |C − C_{1}| ≤ |C_{1}| + |D_{1}| ≤ 2|C|,

that is, 2|P | + |C| ≤ 2|C|, so

2|P | ≤ |C|.  (16)

By definition, P is a circuit of the component M_{1} of M/C. Thus P is a series class of (M/C)\(E(M_{1}) − P). Hence

P is a series class of M\(E(M_{1}) − P).  (17)

For each 2-element subset {x, y} of C, let N_{xy} be the component of M/(C − {x, y}) that contains {x, y}. Choose a 2-element subset {a, b} of C such that E(M_{1}) is contained in E(N_{ab}). Then M_{1} is a connected component of N_{ab}/a. Thus N_{ab} can be decomposed as the parallel connection of two matroids across a such that, for one of these matroids, N_{1}, we have N_{1}/a = M_{1}. Among the 2-element subsets {a, b} of C for which E(M_{1}) ⊆ E(N_{ab}), choose one such that

c_{a}^{∗}(N_{1}) − 1 is a minimum.  (18)

Let P_{1} be a chord of C contained in E(M_{1}) such that |P_{1}| = c_{a}(N_{1}) − 1. By Theorem 1.5, we have that

|E(M_{1})| = |E(N_{1})| − 1 ≤ (c_{a}(N_{1}) − 1)(c_{a}^{∗}(N_{1}) − 1).  (19)

Now M_{1} is not a circuit. By (17), P_{1} is a series class of M\(E(M_{1}) − P_{1}). Thus M\(E(M_{1}) − P_{1}) is the 2-sum, with basepoint p, of a circuit with ground set P_{1} ∪ p and a matroid M′_{1} with ground set (E(M) − E(M_{1})) ∪ p. We construct a new matroid M′ from M\(E(M_{1}) − P_{1}) by placing c_{a}^{∗}(N_{1}) − 2 series classes “in parallel” with P_{1}, with each such series class having exactly |P_{1}| elements. More formally, take c_{a}^{∗}(N_{1})−2 disjoint subsets of size |P_{1}|, each disjoint from E(M), and, for each such subset X, take a circuit with ground set X ∪ p. Then M′ is obtained by deleting p from the parallel connection, with basepoint p, of the collection of matroids consisting of all these circuits, the circuit with ground set P_{1} ∪ p, and the matroid M′_{1}. For each 2-element subset {x, y} of C, let N′_{xy} be the component of M′/(C −{x, y}) that contains {x, y}. Then E(N′_{ab}) contains P_{1}. Moreover, N′_{ab} can be obtained from N_{ab} by replacing N_{1} by the parallel connection, with basepoint a, of c_{a}^{∗}(N_{1}) − 1 circuits, each having exactly |P_{1}| + 1 elements. Thus

|E(M′)| = |E(M)| − |E(N_{1})| + |P_{1}|(c_{a}^{∗}(N_{1}) − 1) + 1.

Since |P_{1}| = c_{a}(N_{1}) − 1 and |E(M_{1})| = |E(N_{1})| − 1, we deduce that

|E(M′)| − |E(M)| = (c_{a}(N_{1}) − 1)(c_{a}^{∗}(N_{1}) − 1) − |E(M_{1})|.

Therefore, by (19) , |E(M′)| ≥ |E(M)|. Since M′/C has fewer components that are not circuits than does M/C, it will follow that (∗∗) holds for the pair (M′, C), provided we can show that

|C| = c(M′).  (20)

The proof of the lemma will be completed by proving this together with the inequality

c^{∗}(C, M′) ≤ c^{∗}(C, M).  (21)

Suppose that c(M′) > |C|. Then M′ has a circuit C′ such that |C′| > |C|. Certainly C′ meets E(M′) − E(M), otherwise C′ is a circuit of M; a contradiction. If C′ ⊆ E(M′) − E(M), then C′ is the union of two series class of M′ each of which is contained in E(M′) − E(M) and has |P_{1}| elements. Thus

|C′| = 2|P_{1}| ≤ |C|

where the last inequality follows by (16) . This contradiction implies that C′ meets both E(M′) − E(M) and E(M) ∩ E(M′). Thus C′ contains a series class P′ of M′ that is contained in E(M′) − E(M). Hence (C′ − P′) ∪ P_{1} is also a circuit of M′ having the same cardinality as C′. This is a contradiction because this circuit is also a circuit of M. Thus (20) holds.

Next we prove (21). Suppose that c^{∗}(C, M′) > c^{∗}(C, M). Then there is a 2element subset {g, h} of C such that

c_{gh}^{∗}(C, M′) > c_{gh}^{∗}(C, M),

where

c_{gh}^{∗}(C, M) = max{|D^{∗}| : D^{∗} ∈ C(M^{∗}) and D^{∗} ∩ C = {g, h}}.

Then certainly N_{gh} ≠ N′_{gh}. Moreover, if E(M_{1}) avoids E(N_{gh}), then M_{1} is a component of M/(C − {g, h}) and so N_{gh} = N′_{gh}; a contradiction. Thus E(M_{1}) meets, and so is contained in, E(N_{gh}). Hence P_{1} is contained in E(N_{gh}).

Each of N_{gh} and N′_{gh} can be obtained as a parallel connection across g of a certain set of matroids. For N_{gh}, this set S_{g} includes a matroid N′′_{1} for which N′′_{1}/g = M_{1}. The set S′_{g} for N′_{gh} must contain S_{g} − {N′′_{1}}.

We show next that P_{1} ∪g is a circuit of N′′_{1}. Suppose not. Then P_{1} is a circuit of M/(C − {g, h}) and hence of M′/(C − {g, h}). It follows from the construction of M′ that P_{1} is a component of M′/(C − {g, h}) and that the elements of E(M′) − E(M) are partitioned into c_{a}^{∗}(N_{1}) − 2 sets each a |P_{1}|-circuit that is a component of M′/(C − {g, h}). Thus S′_{g} = S_{g} − {N′′_{1}} and so c_{gh}^{∗}(C, M′) ≤ c_{gh}^{∗}(C, M); a contradiction. Thus P_{1} ∪ g is indeed a circuit of N′′_{1}.

The construction of M′ now implies that S′_{g} is obtained from S_{g} − {N′′_{1}} by adjoining c_{a}^{∗}(N_{1}) − 1 circuits, each of size |P_{1}| + 1. Thus

c_{gh}^{∗}(C, M′) − c_{gh}^{∗}(C, M) = (c_{a}^{∗}(N_{1}) − 1) − (c_{g}^{∗}(N′′_{1}) − 1).

But, by the choice of N_{1}, the right-hand side of this equation is not positive. Hence c_{gh}^{∗}(C, M′) ≤ c_{gh}^{∗}(C, M); a contradiction. We conclude that (21) holds.

Since (∗∗) holds for M′ and c(M) = |C| = c(M′),

|E(M′)| ≤ c(M) ⌈\frac{c^{∗}(C, M′)}{2}⌉ .

But |E(M)| ≤ |E(M′)| and c^{∗}(C, M′) ≤ c^{∗}(C, M). Hence

|E(M)| ≤ c(M) ⌈\frac{c^{∗}(C, M)}{2}⌉;

a contradiction. □

We are now ready to prove the main result of the paper.

Proof of Theorem 1.4. Evidently, it suffices to prove that

|E(M)| ≤ \frac{c(M)c^{∗}(M)}{2}.

We shall first prove this when c^{∗}(M) is even. By Lemma 3.2,

|E(M)| ≤ c(M) ⌈\frac{c^{∗}(C, M)}{2}⌉ ,

for any circuit C of M such that |C| = c(M). As c^{∗}(C, M) ≤ c^{∗}(M), it follows that

|E(M)| ≤ c(M) ⌈\frac{c^{∗}(C, M)}{2}⌉ ≤ c(M) ⌈\frac{c^{∗}(M)}{2}⌉ = \frac{c(M)c^{∗}(M)}{2},

where the last equality follows since c^{∗}(M) is an even integer.

When c^{∗}(M) is odd, let M′ be the matroid obtained from M by inserting an element in parallel with each element of the latter. Then c^{∗}(M′) = 2c^{∗}(M). Thus c^{∗}(M′) is even and hence

|E(M′)| ≤ \frac{c(M′)c^{∗}(M′)}{2}.

As |E(M′)| = 2|E(M)| and c(M′) = c(M), we get

2|E(M)| ≤ c(M)c^{∗}(M)

and the result follows. □

Reid [11] noted that the matroid Ramsey numbers have the property that n(1, 1) = 1 and n(s, t) = 2 if s or t is in {1, 2} provided (s, t) ≠ (1, 1). As a consequence of the last theorem, we can determine n(s, t) for all other pairs (s, t). Before this result, for s ≤ t, the Ramsey number with s largest for which the exact value was known was n(6, 6), which Bonin, McNulty, and Reid [1] showed was equal to 13. 3.3. Corollary. For all integers s and t exceeding two,

n(s, t) = ⌊\frac{(s − 1)(t − 1)}{2}⌋ + 1.

Proof. It follows immediately from Theorem 1.4 that

n(s, t) ≤ ⌊\frac{(s − 1)(t − 1)}{2}⌋ + 1.

We shall show that equality holds here by giving, for all s and t exceeding two, an example of a connected matroid M with c(M) = s − 1, c^{∗}(M) = t − 1, and

|E(M)| = ⌊\frac{(s − 1)(t − 1)}{2}⌋ .

In each case, the matroid M will be the cycle matroid of a graph G. If t is odd, let G be obtained from a cycle with s − 1 edges by replacing each edge by \frac{t−1}{2} edges in parallel. If s is odd, let G consist of two vertices joined by t − 1 internally disjoint paths each of length \frac{s−1}{2}. Finally, if s and t are both even, let G be constructed by joining two vertices by three internally disjoint paths, of lengths \frac{s−2}{2}, \frac{s−2}{2}, \frac{s}{2}, and then replacing each edge of the first and last paths by \frac{t−2}{2} edges in parallel. □

4. The matroids attaining the bound of Theorem 1.5

In this section, we characterize the matroids for which equality holds in the bound in Theorem 1.5. In addition, we relate this class of matroids to the graphs that attain the bound in Theorem 1.2. We denote by B_{3} the class of matroids that attain the bound in Theorem 1.5, that is, those matroids M that have an element e for which

|E(M)| = c_{e}(M) + (c_{e}(M) − 1)(c_{e}^{∗}(M) − 2).

It is straightforward to check that B_{3} is closed under duality and that every circuit with at least two elements including e belongs to B_{3}. In the next lemma, we shall prove that B_{3} is closed under series connection, provided some conditions are satisfied. A matroid M is uniform with respect to an element f if every circuit containing f has the same cardinality d and every cocircuit containing f has the same cardinality d^{∗}. A matroid M is a uniform series connection of k matroids M_{1}, M_{2}, …, M_{k} for some k ≥ 2 if the following hold: 4.1. (i) M_{1}, M_{2}, …, M_{k} are connected matroids each having at least two ele-

ments; (ii) E(M_{i}) ∩ E(M_{j}) = {e} for every 2-subset {i, j} of {1, 2, …, k}; (iii) c_{e}^{∗}(M_{1}) = c_{e}^{∗}(M_{2}) = ⋯ = c_{e}^{∗}(M_{k}); (iv) M_{1}, M_{2}, …, M_{k} are uniform with respect to e; and

(v) M is S(M_{1}, M_{2}, …, M_{k}), the series connection with basepoint e of M_{1}, M_{2}, …, M_{k}.

4.2. Lemma. Let M_{1}, M_{2}, …, M_{k} be matroids satisfying (4.1)(i)–(ii). Let M = S(M_{1}, M_{2}, …, M_{k}). Then M ∈ B_{3} if and only if all of M_{1}, M_{2}, …, M_{k} are in B_{3} and (4.1)(iii) holds. Moreover, M is uniform with respect to e if and only if (4.1)(iii) and (4.1)(iv) hold.

Proof. Clearly

|E(M)| = 1 + ∑_{i=1}^{k}(|E(M_{i})| − 1).

Thus, by applying Theorem 1.5 to each M_{i}, we get

|E(M)| ≤ 1 + ∑_{i=1}^{k}[c_{e}(M_{i}) − 1 + (c_{e}(M_{i}) − 1)(c_{e}^{∗}(M_{i}) − 2)]

= 1 + ∑_{i=1}^{k}(c_{e}(M_{i}) − 1) + ∑_{i=1}^{k}(c_{e}(M_{i}) − 1)(c_{e}^{∗}(M_{i}) − 2)

≤ c_{e}(M) + max{c_{e}^{∗}(M_{i}) − 2 : 1 ≤ i ≤ k} ∑_{i=1}^{k}(c_{e}(M_{i}) − 1)
= c_{e}(M) + max{c_{e}^{∗}(M_{i}) − 2 : 1 ≤ i ≤ k}(c_{e}(M) − 1)
= c_{e}(M) + (c_{e}^{∗}(M) − 2)(c_{e}(M) − 1).

Thus M ∈ B_{3} if and only if equality occurs throughout the above, that is, if and only if M_{1}, M_{2}, …, M_{k} are all in B_{3}, and

c_{e}^{∗}(M_{1}) = c_{e}^{∗}(M_{2}) = ⋯ = c_{e}^{∗}(M_{k}).

Hence the first part of the lemma holds. The second part follows straightforwardly from the definition of series connection. □

The proof of the characterization of the matroids attaining equality in Theorem 1.5 will use two results of Seymour [13]. Because the terminology of that paper is different from that used here, we have translated Seymour’s results into our terminology. The first result is [13, (3.7)], restated in the special case that Z is a circuit. 4.3. Lemma. Let e be an element of a circuit C of a connected matroid M. If M\e is connected, then there is no partition {X_{1}, X_{2}} of E(M) − e such that

(i) no chord of C meets both X_{1} and X_{2}; and

(ii) for each i in {1, 2}, if P is a chord of C contained in X_{i}, then X_{i} contains

a circuit containing P. The second lemma is a restatement of a special case of [13, (3.8)].

4.4. Lemma. Let C and D be circuits of a matroid M such that C ∩ D = {e} and (C ∪ D) − e is also a circuit of M. Then either (C ∪ D) − e has a chord A that is different from {e} and is not a chord of C or of D, or there is a partition {X_{1}, X_{2}} of E(M\e) such that X_{1} ⊇ C − e and X_{2} ⊇ D − e, and

r(X_{1}) + r(X_{2}) − r(M\e) = r(C − e) + r(D − e) − r((C ∪ D) − e) = 1.

4.5. Theorem. B_{3} is the minimal class M of matroids with the following properties. (i) Every circuit that contains e and has at least two elements is in M. (ii) The dual of every member of M is in M.

(iii) The uniform series connection of a collection of members of M is in M.

Proof. We noted above that B_{3} contains all circuits with at least two elements including e and that B_{3} is closed under both duality and uniform series connection. The proof will be completed by proving the following, where the superfluous strength of the assertion will facilitate the argument.

4.5.1. If M ∈ B_{3}, then M is uniform with respect to e, and M or its dual is a circuit or is a uniform series connection of a collection of matroids in B_{3}.

We shall argue by induction on |E(M)| noting that the assertion holds when M is a circuit. Thus we may assume that M is not a circuit.

We shall use the same notation as in the proof of Theorem 2.1 taking m = 3. When a matroid attains equality in the bound in Theorem 1.5, equality must hold in all the inequalities that appear in the proof of Theorem 2.1.

First, observe that, to achieve equality in (6), we must have that, for all i in {1, 2, …, n},

c_{e}^{∗}(N_{i}) = c_{e}^{∗}(N)

for every N in Q_{i}. Thus N_{i} can be chosen arbitrarily in Q_{i}.

Equality must also hold in (9), that is,

|P_{i}| = min{|L_{ij}| : 1 ≤ j ≤ n_{i} − 1},

so, for all j in {1, 2, …, n_{i} − 1},

|L_{ij}| = |P_{i}|.  (22)

Since equality must hold in (10) and (11), we have that, for all i in {1, 2, …, n},

(n_{i} − 1)|P_{i}| = |Q_{i}| = |P_{i}|.

Thus, for all such i,

n_{i} = 2.  (23)

As any N in Q_{i} can be taken to be N_{i}, and since equality holds in (13), we have that, for all N in Q_{i},

c_{e}(N) − 1 = \frac{|E(M_{i})|}{c_{e}^{∗}(N) − 1} = \frac{|E(M_{i})|}{c_{e}^{∗}(N_{i}) − 1} = c_{e}(N_{i}) − 1.

Hence

c_{e}(N_{i}) = c_{e}(N)  (24)

for every N in Q_{i}.

Again, since equality holds in (13),

|E(M_{i})| = |E(N_{i})| − 1 = (c_{e}(N_{i}) − 1)(c_{e}^{∗}(N_{i}) − 1),

and so N_{i} ∈ B_{3}. Thus, by the induction assumption, we deduce the following:

4.5.2. For all i in {1, 2, …, n}, the matroid N_{i} is uniform with respect to e.

Next we observe that the chords of C have the following property.

4.5.3. For all i in {1, 2, …, n}, every chord of C contained in E(M_{i}) has cardinality equal to |P_{i}|.

To see this, we note that, for such a chord P, the set P ∪ e is a circuit of N for some N in Q_{i}. As this N can be taken to be N_{i}, the assertion follows from (8) and (24) because |P_{i}| = c_{e}(N_{i}) − 1 and N_{i} is uniform with respect to e.

Next we show the following:

4.5.4. Suppose i ∈ {1, 2, …, n}. Let P′_{i} be a chord of C contained in E(M_{i}) and let C_{i} and C′_{i} be the unique circuits of M|(C ∪ P_{i}) and M|(C ∪ P′_{i}), respectively, that avoid e. Then

C_{i} ∩ C = L_{i1} = C′_{i} ∩ C.

By definition, Q_{i} = ⋃_{f∈C−e}{N ∈ P_{f} : N/e = M_{i}}. Also |{N ∈ P_{f} : N/e = M_{i}}| is 0 or 1 for all f in C − e and, by (23), n_{i} = 2. Therefore, from the paragraph between (9) and (10), we have that, for all f in L_{i1}, there is a matroid N in P_{f} such that N/e = M_{i}. Thus

|Q_{i}| = |{f ∈ C − e : P_{f} contains a matroid N such that N/e = M_{i}}|
≥ |L_{i1}|.

But equality holds in (10) and therefore holds in the above. Hence, as L_{i1} = C_{i} ∩C, we have

C_{i} ∩ C = {f ∈ C − e : P_{f} contains a matroid N such that N/e = M_{i}}. (25)

By (4.5.3), |P′_{i}| = |P_{i}| and so P′_{i} can be used in place of P_{i} throughout the proof of Theorem 2.1 and in the above. In particular,

C′_{i} ∩ C = {f ∈ C − e : P_{f} contains a matroid N such that N/e = M_{i}}.

We conclude that

C_{i} ∩ C = C′_{i} ∩ C,

that is, (4.5.4) holds.

On combining (4.5.4) and (22), we get that

|C_{i} ∩ C| = |P_{i}|.  (26)

We now show that two sets C_{i}∩C and C_{j}∩C are either disjoint or are comparable.

4.5.5. If i and j are distinct elements of {1, 2, …, n}, then (i) C_{i} ∩ C_{j} = ∅; or (ii) C_{i} ∩ C ⊆ C_{j} ∩ C; or (iii) C_{j} ∩ C ⊆ C_{i} ∩ C.

By (23), n_{i} = n_{j} = 2. Thus each of the Tutte-lines C ∪ P_{i} and C ∪ P_{j} has size three, so the matroids M|(C ∪P_{i}) and M|(C ∪P_{j}) are binary. It is a straightforward consequence of a result of Lemos [8, (3.1)] that M|(C ∪ P_{i} ∪ P_{j}) is also binary. Assume that none of (i)–(iii) holds. Then M|(C ∪ P_{i} ∪ P_{j}) is the cycle matroid of the graph obtained from a cycle C by adding two disjoint paths P_{i} and P_{j} each with both endpoints on C such that the resulting graph is a subdivision of K_{4}. Let C′ = P_{i} ∪ P_{j} ∪ (C_{i} ∩ C_{j} ∩ C) ∪ (C − (C_{i} ∪ C_{j})). Then C′ is a circuit of M containing e and

|C′| = |P_{i}| + |P_{j}| + |C_{i} ∩ C_{j} ∩ C| + |C − (C_{i} ∪ C_{j})|.

Thus, by (26) and the fact that {C_{i}∩C_{j}∩C, C−(C_{i}∪C_{j}), (C_{i}∩C)−C_{j}, (C_{j}∩C)−C_{i}} is a partition of C, we deduce that

|C′| = |C_{i} ∩ C| + |C_{j} ∩ C| + |C| − |(C_{i} ∩ C) − C_{j}| − |(C_{j} ∩ C) − C_{i}|.

As C_{i}∩C properly contains (C_{i}∩C)−C_{j}, and C_{j} ∩C properly contains (C_{j} ∩C)−C_{i}, we deduce that |C′| > |C|; a contradiction. We conclude that (4.5.5) holds.

Let Q_{1}, Q_{2}, …, Q_{k} be the distinct maximal sets in the family {C_{i} ∩ C : 1 ≤ i ≤ n}. Then, by (4.5.5), Q_{i} ∩ Q_{j} = ∅ for all 2-element subsets {i, j} of {1, 2, …, k}. For each j in {1, 2, …, k}, let Q′_{j} be the union of all E(M_{i}) for which C_{i} ∩ C ⊆ Q_{j}. Then {Q′_{1}, Q′_{2}, …, Q′_{k}} is a partition of E(M) − C. Letting X_{1} = Q_{1} ∪ Q′_{1} and X_{2} = E(M\e) − (Q_{1} ∪ Q′_{1}), we deduce from Lemma 4.3 that either (a) M\e is disconnected, or (b) X_{2} is empty. In the first case, M is a series connection with basepoint e of a set of connected matroids each having at least two elements. Since M ∈ B_{3}, it follows by Lemma 4.2 and the induction assumption that M satisfies (4.5.1). Thus we may assume that (ii) holds. Hence

k = 1 and Q_{1} = C − e.  (27)

Moreover, for some i in {1, 2, …, n}, we have Q_{1} = C_{i} ∩C, and, by (26), |C_{i} ∩C| = |P_{i}|. Hence |P_{i}| = |C| − 1 and so, letting D = P_{i} ∪ e, we have that D is a circuit of M containing e and having cardinality |C|, and C ∪ D is a Tutte-line of size three for which the canonical partition is {{e}, C −e, D −e}. Thus (C ∪D)−e is a circuit of M.

Next we shall prove the following:

4.5.6. Let A be a chord of (C ∪ D) − e. Then A = {e}, or A is a chord of C or D.

Suppose that A ≠ {e} and let W = M|(C ∪ D ∪ A). The proof of (4.5.6) will be broken into several steps the first of which is as follows.

4.5.7. If D_{1} and D_{2} are circuits of W and e ∈ D_{1} ∩ D_{2}, then D_{1} ∪ D_{2} is a proper subset of E(W).

Suppose that E(W) = D_{1} ∪ D_{2}. Then

|D_{1} ∪ D_{2}| = |E(W)| = |C ∪ D ∪ A| = |C| + |D − e| + |A| = 2|C| − |{e}| + |A| ≥ 2|C|.

As e ∈ D_{1} ∩ D_{2}, it follows that |D_{1} ∩ D_{2}| ≥ 1. Thus

|D_{1}| + |D_{2}| = |D_{1} ∪ D_{2}| + |D_{1} ∩ D_{2}| ≥ 2|C| + 1.

Therefore |D_{1}| > |C| or |D_{2}| > |C|. This is a contradiction because |C| = c_{e}(M) and e ∈ D_{1} ∩ D_{2}. We conclude that (4.5.7) holds.

Now consider W^{∗}, which has rank three since W has corank three. Recall that the points and lines of a matroid are its rank-1 and rank-2 flats.

4.5.8. W^{∗} has the following properties:

(i) {e} and A are points of W^{∗}.

(ii) If L_{1} and L_{2} are lines of W^{∗} such that e ∉ L_{1} ∪ L_{2}, then L_{1} ∩ L_{2} ≠ ∅. (iii) There are exactly three lines in W^{∗} that contain A. (iv) The line which contains e and A does not contain another point.

Part (i) holds because {e} and A are series classes of W. Part (ii) follows immediately from (4.5.7) by duality. Parts (iii) and (iv) hold because E(W) − A contains exactly three circuits, and because E(W)−(A∪e) is the circuit (C ∪D)−e of W. Thus (4.5.8) holds.

By (4.5.8)(iii), W^{∗} has exactly three lines, say L_{1}, L_{2}, and L_{3}, that contain A. By (4.5.8)(iv), we may suppose that L_{1} = A ∪ e. Next we establish the following:

4.5.9. L_{2} or L_{3} contains just one point different from A.

For each i in {2, 3}, let p_{i1} and p_{i2} be distinct points contained in L_{i} − A. For each j and k in {1, 2}, let K_{jk} be the line of W^{∗} that contains p_{2j} and p_{3k}. Suppose that, for some i, j, k, and l in {1, 2} such that i ≠ k and j ≠ l, we have e ∉ K_{ij} ∪K_{kl}. Then, by (4.5.8)(ii), K_{ij} ∩ K_{kl} = {p} for some point p. Clearly p is not on L_{2} or L_{3} and, by (4.5.8)(iv), it is not on L_{1}. Hence p does not exist. Thus K_{ij} or K_{kl} has e as a point. Hence e is on K_{11} or K_{22}, and it is on K_{21} or K_{12}. Thus we have two distinct lines having two common points. This contradiction implies that (4.5.9) holds.

By (4.5.9), we may suppose that L_{2} − A contains a single point Z. Then Z ∪ e is the complement of L_{3} and so is a circuit of W that does not intersect A. Hence Z ∪ e is C or D. Moreover, A is a component of W^{∗}\[(C ∪ D) − Z] and hence of W/[(C ∪ D) − Z]. Thus A is a component of [M|(C ∪ D ∪ A)]/[(C ∪ D) − Z]. But A is a circuit of [M|(C ∪ D ∪ A)]/[C ∪ D]. Hence A is a circuit of M/[(C ∪ D) − Z], that is, A is a chord of (C ∪ D) − Z. Hence A is a chord of C or D, and (4.5.6) holds.

By (4.5.6) and Lemma 4.4, it follows that there is a partition {X_{1}, X_{2}} of E(M\e) such that X_{1} ⊇ C − e and X_{2} ⊇ D − e, and r(X_{1}) + r(X_{2}) − r(M\e) = 1. Since e is in the closure of both X_{1} and X_{2}, it follows that M is the parallel connection, with basepoint e, of matroids with ground sets X_{1} ∪ e and X_{2} ∪ e. Thus M^{∗} is a series connection, with basepoint e, of two matroids. Since B_{3} is closed under duality, the theorem follows using Lemma 4.2 and the induction assumption. □

Evidently each of the matroids that attains the bound in Theorem 1.5 is a series-parallel network. The following result is thus an immediate consequence of Theorems 1.5 and 4.5.

4.6. Corollary. Let M be a connected matroid that is not a series-parallel network. If e ∈ E(M), then

|E(M)| ≤ (c_{e}(M) − 1)(c_{e}^{∗}(M) − 1).

We conclude by noting an interesting link between the matroids attaining the bound in Theorem 1.5 and the graphs attaining the bound in Theorem 1.2. The following result was proved by Wu [17].

4.7. Theorem. Let M be a connected graphic matroid with at least two elements. Then E(M) = \frac{1}{2}c(M)c^{∗}(M) if and only if, for some k ≥ 2, there is a sequence of positive integers (m, n_{1}, n_{2}, …, n_{k}) for which n_{i} ≤ \frac{1}{2} ∑_{j=1}^{k} n_{j} for all i in {1, 2, …, k} such that either M or M^{∗} can be obtained by deleting e from the parallel connection, with basepoint e, of k matroids M_{1}, M_{2}, …, M_{k}, where each M_{i} is the cycle matroid of a graph that can be obtained from a 2-cycle containing e by a sequence of the following operations:

(a) in a cycle containing e, replacing every edge except e by two edges in parallel; and

(b) in a bond containing e, subdividing every edge except e exactly once;

where this sequence consists of n_{i} − 1 operations of type (a) and m − 1 operations of type (b).

Using Theorem 4.5, one can show that the matroids in B_{3} can be characterized in a similar way. To prevent the paper from becoming too long, we omit the details of the proof.

4.8. Corollary. Let M be a connected matroid with at least two elements and suppose e ∈ E(M). Then |E(M)| = (c_{e}(M) − 1)(c_{e}^{∗}(M) − 1) + 1 if and only if, for some k ≥ 1, there is a sequence of positive integers (m, n_{1}, n_{2}, …, n_{k}) such that M is the parallel connection, with basepoint e, of k matroids M_{1}, M_{2}, …, M_{k}, where each M_{i} is the cycle matroid of a graph that can be obtained from a 2-cycle containing e by a sequence of the following operations:

(a) in a cycle containing e, replacing every edge except e by two edges in parallel; and

(b) in a bond containing e, subdividing every edge except e exactly once;

where this sequence consists of n_{i} − 1 operations of type (a) and m − 1 operations of type (b).

Acknowledgements

The authors thank Guoli Ding for showing them a short proof of Theorem 1.5. The first author was partially supported by CNPq, CAPES, FINEP, and PRONEX 107/97. The second author was partially supported by the National Security Agency.

References

[1] Bonin, J., McNulty, J., and Reid, T.J., The matroid Ramsey number n(6, 6), Combin. Probab. Comput. 8(1999), 229–235.

[2] Denley, T. and Reid, T.J., On the number of elements in matroids with small circuits and small cocircuits, Combin. Probab. Comput., to appear.

[3] Erdős, P. and Szekeres, G., A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.

[4] Fulkerson, D.R., Networks, frames, blocking sysyems, in Mathematics of the Decision Sciences, Part 1, Lectures in Applied Math. Vol. 11, Amer. Math. Soc., Providence, R.I., 1968, pp. 303-334.

[5] Hurst, F. and Reid, T.J., Some small circuit-cocircuit Ramsey numbers for matroids, Combin. Probab. Comput. 4 (1995), 67–80.

[6] Hurst, F. and Reid, T.J., Ramsey numbers for cocircuits in matroids, Ars Combin. 45 (1997), 181–192.

[7] Lehman, A., On the width-length inequality, Math. Programming 17 (1979), 403–417.

[8] Lemos, M., k-elimination property for circuits of matroids, J. Combin. Theory Ser. B 51 (1991), 211–226.

[9] Oxley, J.G., Matroid Theory, Oxford University Press, New York, 1992.

[10] Oxley, J.G., Unavoidable minors in graphs and matroids, in Graph theory and combinatorial biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud. 7, János Bolyai Math. Soc., Budapest, 1999, pp. 279–305.

[11] Reid, T.J., Ramsey numbers for matroids, Europ. J. Combin 18 (1997), 589–595.

[12] Seymour, P.D., The matroids with the max-flow min-cut property, J. Combin. Theory Ser. B 23 (1977), 189–222.

[13] Seymour, P.D., Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), 305–354.

[14] Tutte, W.T., Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1–47.

[15] Tuza, Z., On two intersecting set systems and k-continuous Boolean functions, Discrete Appl. Math 16 (1987), 183–185.

[16] Wu, P.-L., An upper bound on the number of edges of a 2-connected graph, Combin. Probab. Comput. 6 (1997), 107–113.

[17] Wu, P.-L., Extremal graphs with prescribed circumference and cocircumference, submitted.

Departamento de Matemática, Universidade Federal de Pernambuco, Recife, Pernambuco 50740-540, Brazil

E-mail address: manoel@dmat.ufpe.br

Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803–4918, USA

E-mail address: oxley@math.lsu.edu