MATROIDS HAVING SMALL CIRCUMFERENCE

BRÁULIO MAIA JUNIOR AND MANOEL LEMOS

Abstract. In this paper, we conclude the construction of all the matroids having circumference at most five. We use this result to prove a conjecture of Hochstättler and Jackson, in a special case.

1. Introduction

In this paper, we assume familiarity with matroid theory. The notation and terminology used in this article follow Oxley [22]. For a matroid M that is not free, circ(M) denotes the circumference of M, that is, the maximum cardinality of a circuit of M. In recent years, the circumference of a matroid has appeared in some bounds, for example, in an upper bound for the size of a minimally nconnected matroid and in a lower bound for the size of a n-connected matroid having a circuit whose deletion is also n-connected, for n ∈ {2, 3} (see [11, 12, 13]). Using these bounds and results about matroids with small circumference, it is possible to improve some bounds found in the literature. Lemos and Oxley [12] proved that a connected matroid M has a circuit C such that M\C is connected provided |E(M)| ≥ 3r(M). This bound is sharp, but it can be improved provided some other conditions are imposed on the matroid M. To improve it, Junior [7] needed to know all the matroids that have circumference at most five. These matroids are constructed in [7] and in this paper. Here, we deal with the most difficult case: the 3-connected matroids having both rank and circumference equal to five.

Dirac proved that a graph G has a Hamiltonian circuit provided 2d(v) ≥ |V (G)|, for every vertex v of G. Clearly, this condition is satisfied by a d-connected graph, when 2d ≥ |V (G)|. As a consequence of Dirac’s Theorem, we have that every d-connected graph, for 2d ≥ |V (G)|, has a Hamiltonian circuit. In the submitted version of [4], Hochstättler and Jackson conjectured that the same result would hold for binary matroids. That is, if 2d ≥ r(M) + 1, then a d-connected binary matroid M has a Hamiltonian circuit, which is a circuit with cardinality r(M) + 1, unless r(M) and all the circuits of M are even. As the referee provided a counter-example for it, Hochstättler and Jackson made the following conjecture.

Conjecture 1.1. Let M be a d-connected binary matroid for some integer d where

d ≥ \frac{r(M) + 1}{2}.

Then M has a circuit of size at least r(M).

With the main result of this paper, we prove this conjecture for d = 3. Moreover, we prove a strong result, where we drop the binary hypothesis from the matroid, as suggested by Hochstättler and Jackson, and we list all the matroids satisfying the hypotheses without a Hamiltonian circuit.

Let J_{10} be the matroid whose representation over GF (2) is given by the following matrix.

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \end{matrix} ]

This matroid has been considered by Oxley [18], when he characterized the binary matroids with no four-wheel as a minor. The matroid J_{10} is 3-connected and has both rank and circumference equal to five. Now, we describe the circuits of J_{10}. Label the columns of this matrix by b_{1}, b_{2}, b_{3}, b_{4}, b_{5}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5} respectively. A subset C of E(J_{10}) is a circuit of J_{10} if and only if

(1) when |C ∩ {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}}| is even, there is a 2-subset {i, j} of {1, 2, 3, 4, 5} such that C = {a_{i}, a_{j}, b_{i}, b_{j}}, or

(2) when |C ∩ {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}}| is odd, there is d_{i} ∈ {a_{i}, b_{i}}, for each i ∈ {1, 2, 3, 4, 5}, such that C = {d_{1}, d_{2}, d_{3}, d_{4}, d_{5}}.

Let J_{9} be the matroid obtained from J_{10} by deleting b_{5}. In the main result of this paper, Theorem 1.1, we prove that a 3-connected matroid having rank at most five is Hamiltonian, unless it is isomorphic to U_{1,1}, F_{7}^{∗}, AG(3, 2), J_{9}, or J_{10}. (The existence of Hamiltonian circuits in a matroid is very important: nice applications of them can be found in [2] and [3].)

Theorem 1.1. Suppose that M is a 3-connected matroid non-isomorphic to U_{1,1}, F_{7}^{∗}, AG(3, 2), J_{9}, or J_{10}. If r(M) ≤ 5, then circ(M) = r(M) + 1.

We say that a matroid M is a book when there are 3-connected rank-2 matroids M_{1}, …, M_{n}, for n ≥ 1, and an element e such that E(M_{i}) ∩ E(M_{j}) = {e}, when i ≠ j, and M = P_{e}(M_{1}, …, M_{n}). Junior [7] construct all the matroids with circumference at most five that are not 3-connected. It is not difficult to see that we need to list only these matroids that are connected and simple. Now, we state Junior’s theorem [7].

Theorem 1.2. Suppose that M is a simple connected matroid that is not 3-connec-ted. If circ(M) ≤ 5, then there are matroids N, B_{1} and B_{2} such that N is 3connected, B_{1} and B_{2} are books, E(B_{1})∩E(B_{2}) = ∅, E(B_{1})∩E(N) = {e}, E(B_{2})∩ E(N) = {f},

(i) r(N) ∈ {2, 3} and M = P_{e}(N, B_{1})\X, for some X ⊆ {e}, or (ii) N is isomorphic to F_{7}^{∗} and M = P_{e}(N, B_{1})\X, for some X ⊆ {e}, or (iii) r(N) = 2 and M = P_{f}(P_{e}(N, B_{1}), B_{2})\X, for some X ⊆ {e, f}.

With the next result of Lemos and Oxley [13], we have the complete picture of the circumference for 3-connected matroids because M(K_{3,r−2}), for r ≥ 5, is a 3-connected matroid having circumference six and rank r.

Theorem 1.3. Suppose that M is a 3-connected matroid. If r(M) ≥ 6, then circ(M) ≥ 6.

With the construction of the matroids that have circumference at most five, which is completed in this paper, one can calculate the matroid Ramsey numbers n(s, t), for every s ≤ 6. Some of these numbers have been found in [1], [5], [6] and [25]. We do not compute them here, since Lemos and Oxley obtained all of them in [14]. Non-binary matroids with small circumference are also related to matroids having the k-elimination property for circuits, which has been considered in [8] and [20].

2. Know results

We need the following result from Junior [7].

Proposition 2.1. Suppose that M is a 3-connected matroid non-isomorphic to U_{1,1}, F_{7}^{∗}, or AG(3, 2). If r(M) ≤ 4, then circ(M) = r(M) + 1. Moreover, if r(M) ≥ 5, then circ(M) ≥ 5.

For a matroid M, a subset L of E(M) is said to be a Tutte-line of M when (M|L)^{∗} is a loopless matroid having rank equal to two. Observe that L has a partition {L_{1}, L_{2}, …, L_{k}}, for some k ≥ 2, which is called canonical, such that a subset C of L is a circuit of M if and only if C = L \ L_{i}, for some i ∈ {1, 2 …, k}. This Tutte-line is said to be connected when k ≥ 3. From Lemos and Oxley [13], we need the following result.

Lemma 2.1. If L is a Tutte-line of a matroid M and T is a triad of M such that T ∩ L ≠ ∅, then T meets an odd number of sets in the canonical partition of L.

The next two lemmas follow by the elimination axiom for circuits and orthogonality, which is the property that a circuit and a cocircuit of a matroid cannot have exactly one common element.

Lemma 2.2. Suppose that C is a circuit of a matroid M. If T_{1} and T_{2} are different triads of M such that T_{1} ∩ C = T_{2} ∩ C ≠ ∅, then (T_{1} ∪ T_{2}) \ C is a 2-cocircuit.

Lemma 2.3. Suppose that S is a series class of a matroid M. If S ∪X_{1} and S ∪X_{2} are circuits of M for different subsets X_{1} and X_{2} of E(M) \ S, then X_{1} ∪ X_{2} is a dependent set of M.

3. Some lemmas

In this section, we assume that M is a 3-connected matroid such that

r(M) = circ(M) = 5.

We also assume that C is a circuit of M such that |C| = circ(M). In this section, we prove that M is isomorphic to J_{9} or J_{10}. Since C spans a hyperplane of M, the contraction M/C has rank equal to one. Thus, M/C consists of loops and a single parallel class K. Observe that K is a cocircuit of M, being the complement of the hyperplane cl_{M}(C); since M is 3-connected, K has at least three elements. Let D_{M}(C) be the set of circuits of M/C other than loops. Thus, D_{M}(C) is precisely the set of 2-subsets of K; also, since M is 3-connected, no member of D_{M}(C) is a circuit of M. The next lemma is fundamental.

Lemma 3.1. If D ∈ D_{M}(C), then L = D ∪ C is a connected Tutte-line having canonical partition {D, X_{D}, Y_{D}}, where {X_{D}, Y_{D}} is a partition of C such that |X_{D}| = 2 and |Y_{D}| = 3. Moreover, D ∪ X_{D} and D ∪ Y_{D} are circuits of M.

Proof. It is not difficult to see that L is a connected Tutte-line of M. Suppose that {P_{0}, P_{1}, …, P_{k}} is the canonical partition of L, for some integer k ≥ 2. We may suppose that P_{0} = D because D = L \ C. We have

5 = circ(M) ≥ |L \ P_{i}|,

for every i ∈ {1, …, k}. So, |P_{i}| ≥ 2. As {P_{1}, …, P_{k}} is a partition of C, it follows that k = 2. Moreover, {|P_{1}|, |P_{2}|} = {2, 3}. The result follows.

As M is 3-connected, it follows that r(E(K)) ≥ 3. Let

X = {X : X is a 3-subset of E(K) that is independent in M}.

Thus, X ≠ ∅.

Lemma 3.2. If X ∈ X, then M|(C ∪ X) has at most one 2-cocircuit contained in C.

Proof. Suppose that C_{1}^{∗} and C_{2}^{∗} are different 2-cocircuits of M|(C ∪ X) that are contained in C. We have two cases to deal with: either

(1) |C_{1}^{∗} ∩ C_{2}^{∗}| = 1 or

(2) C_{1}^{∗} ∩ C_{2}^{∗} = ∅. In both cases, we prove that there is a series class S of M|(X ∪ C) such that S ∪ D_{1} and S∪D_{2} are circuits of M, for different 2-subsets D_{1} and D_{2} of X. By Lemma 2.3, X is dependent in M and we arrive at a contradiction.

In this paragraph, we assume that (1) occurs. So, C_{1}^{∗} ∪ C_{2}^{∗} is contained in a series class S of M|(C ∪ X). As |S| ≥ 3, it follows that S = Y_{D}, for every 2-subset D of X, because, by Lemma 3.1, X_{D} and Y_{D} are the series class of M|(C ∪ D) contained in C. Again, by Lemma 3.1, S ∪ D is a circuit of M.

Suppose that (2) happens. For every 2-subset D of X, there is an i ∈ {1, 2} such that X_{D} = C_{i}^{∗} and C_{3−i}^{∗} ⊂ Y_{D}, by Lemma 3.1. Thus, there are different 2-subsets D_{1} and D_{2} of X and i ∈ {1, 2} such that X_{D_{1}} = X_{D_{2}} = C_{i}^{∗}. Hence D_{1} ∪ S and D_{2} ∪ S are circuits of M, where S = C_{i}^{∗}, in this case.

Lemma 3.3. If D is a 2-subset of X, where X ∈ X, then X_{D} ∪ (X \ D) is a triad of M|(C ∪ X).

Proof. Suppose that X_{D} ∪ (X \ D) is not a triad of M|(C ∪ X). As X_{D} is a 2cocircuit of M|(C ∪ D), it follows that X_{D} is a 2-cocircuit of M|(C ∪ X). So, for every 2-subset D′ of X such that D ≠ D′,

(1) X_{D} = X_{D′} or

(2) X_{D} ⊂ Y_{D′}. We prove that (2) holds. If (1) occurs, then D ∪ X_{D} and D′ ∪ X_{D} are both circuits of M, by Lemma 3.1. As X_{D} is a series class of M|(C ∪ X), it follows that X is dependent in M, by Lemma 2.3. We arrive at a contradicition and (2) happens. By Lemma 3.2, X_{D′} is not a 2-cocircuit of M|(C ∪ X). Hence T^{∗} = X_{D′} ∪ (X \ D′) is a triad of M|(C ∪ X). By (2), X_{D′} ⊂ Y_{D}. We arrive at a contradiction, by Lemma 2.1, because T^{∗} meets two sets in the canonical partition of the Tutte-line C ∪ D. The result follows.

Suppose that D_{1}, D_{2}, D_{3} are 2-subsets of a set W. Then, D_{1} △ D_{2} △ D_{3} = ∅ if and only if D_{1}, D_{2}, D_{2} are pairwise different and |D_{1} ∪ D_{2} ∪ D_{3}| = 3.

Lemma 3.4. Suppose that X ∈ X. If D_{1}, D_{2}, D_{3} are 2-subsets of X such that D_{1} △ D_{2} △ D_{3} = ∅, then X_{D_{1}} △ X_{D_{2}} △ X_{D_{3}} = ∅. Moreover, S = C \ (X_{D_{1}} ∪ X_{D_{2}} ∪ X_{D_{3}}) is a 2-cocircuit of M|(C ∪ X) and M|(C ∪ X)/e is isomorphic to F_{7}^{∗}, for both elements e ∈ S. Moreover, every circuit of M|(C ∪ X) meets X is an even number of elements.

Proof. By Lemma 3.3, for every i ∈ {1, 2, 3}, T_{i}^{∗} = X_{D_{i}} ∪ (X \ D_{i}) is a triad of M|(C ∪ X). When {i, j} is a 2-subset of {1, 2, 3}, by Lemma 2.1, T_{i}^{∗} meets all the sets in the canonical partition of the Tutte-line C ∪ D_{j}. In particular,

X_{D_{i}} ≠ X_{D_{j}} and X_{D_{i}} ∩ X_{D_{j}} ≠ ∅. (3.1)

By the elimination axiom for circuits, there is a circuit of M contained in

[(D_{1} ∪ X_{D_{1}}) ∪ (D_{2} ∪ X_{D_{2}})] \ {e} = D_{3} ∪ (X_{D_{1}} ∪ X_{D_{2}}),

where e ∈ D_{1} ∩ D_{2}. By Lemma 3.1,

X_{D_{3}} ⊆ X_{D_{1}} ∪ X_{D_{2}} or Y_{D_{3}} = X_{D_{1}} ∪ X_{D_{2}}. (3.2)

So, by equations 3.1 and 3.2, X_{D_{3}} ⊆ X_{D_{1}} ∪ X_{D_{2}}, and so

X_{D_{1}} △ X_{D_{2}} △ X_{D_{3}} = ∅,

and the first part of the lemma follows. By the paragraph prior to the statement of this lemma, |S| = 2.

Next, we prove that M|(C ∪X) does not have a circuit that contains X. Suppose that X ⊆ C′ ∈ C(M|(C ∪ X)). By orthogonality, C′ ∩ T_{i}^{∗} ≠ X \ D_{i}, for every i ∈ {1, 2, 3}. Thus, C′ meets C \ S in at least two elements. As |C′| ≤ circ(M) = 5, it follows that |C′| = 5 and |C′ ∩ (C \ S)| = 2. Without loss of generality, we may suppose that C′ = X ∪ X_{D_{1}} because X_{D_{1}}, X_{D_{2}} and X_{D_{3}} are all the 2-subsets of C \ S. We arrive at a contradiction, since D_{1} ∪ X_{D_{1}} is a circuit of M which is properly contained in C′. So, C′ does not exist. Thus,

C(M|(C ∪ X)) = C(M|(C ∪ D_{1})) ∪ C(M|(C ∪ D_{2})) ∪ C(M|(C ∪ D_{3})).

In particular, S is a series class of M|(C ∪ X). Moreover, all seven circuits of M|(C ∪ X)/e have four elements and the symmetric difference of any two of them is a circuit of M. So, M|(C ∪ X)/e is isomorphic to F_{7}^{∗}.

We define

Y = {Y : Y is a 4-subset of E(K) such that every 3-subset of Y belongs to I(M)}.

Note that this set may be empty. The next lemma is similar to Lemma 3.3.

Lemma 3.5. If D is a 2-subset of Y, where Y ∈ Y, then X_{D} ∪(Y \D) is a cocircuit of M|(C ∪ Y).

Proof. Suppose that Y \ D = {a, b}. For z ∈ {a, b}, taking X equal to D ∪ {z} in Lemma 3.3, we obtain that T_{z}^{∗} = X_{D} ∪ {z} is a triad of M|(C ∪ X). Suppose that T_{a}^{∗} and T_{b}^{∗} are both triads of M|(C ∪ Y). By Lemma 2.2, Y \ D is a 2-cocircuit of M|(C ∪ Y) because C ∩ T_{a}^{∗} = C ∩ T_{b}^{∗} = X_{D}. We arrive at a contradiction because Y is a cocircuit of M|(C ∪ Y). Thus, X_{D} ∪ (Y \ D) is a cocircuit of M|(C ∪ Y).

For a set Z, let K_{Z} be the complete graph having Z as vertex-set. We can view a 2-subset of Z as an edge of K_{Z}. If D_{1}, D_{2}, D_{3} are 2-subsets of Z such that D_{1} △ D_{2} △ D_{3} = ∅, then D_{1}, D_{2}, D_{3} are edges of a triangle of K_{Z}. In the next lemma, it is convinient to regard a triangle of a graph simply as a set of edges rather than as a subgraph.

Lemma 3.6. Suppose that Y ∈ Y.

(i) If Y is independent in M, then M|(C ∪ Y) is isomorphic to J_{9}. (ii) If Y is a circuit of M, then C contains a non-trivial series class S of M|(C ∪

Y) and M|(C ∪ Y)/e is isomorphic to AG(3, 2), for both elements e ∈ S.

Proof. Consider the function ϕ : E(K_{Y}) → E(K_{C}) such that ϕ(D) = X_{D}. This function can be extended to a subset T of E(K_{Y}) by setting ϕ(T) = {ϕ(D) : D ∈ T }. By Lemma 3.4 and the comments before this lemma, this function takes a triangle of K_{Y} into a triangle of K_{C}. We prove that either

(1) there is an injective function ψ : Y → C such that ϕ(D) = {ψ(d) : d ∈ D} or (2) there is a triangle T′ of K_{C} such that ϕ(T) = T′, for every triangle T of K_{Y}.

Suppose that there are different triangles T_{1} and T_{2} of K_{Y} such that ϕ(T_{1}) = ϕ(T_{2}). Let T_{3} be another triangle of K_{Y}. As T_{3} meets T_{1} and T_{2} in different edges, it follows that ϕ(T_{3}) meets ϕ(T_{1}) in at least two edges. Thus, ϕ(T_{3}) = ϕ(T_{1}). In this case, we have (2). So, we may suppose that ϕ(T_{1}) ≠ ϕ(T_{2}), when T_{1} and T_{2} are different triangles of K_{Y}. In this case, it is easy to see that we have (1).

Suppose that (1) happens. In this case, we can label the elements of C by a_{1}, a_{2}, a_{3}, a_{4}, a_{5} and the elements of Y by b_{1}, b_{2}, b_{3}, b_{4} such that ψ(b_{i}) = a_{i}, for every i ∈ {1, 2, 3, 4}. We prove that C(M|(C ∪ Y)) = C_{4} ∪ C_{5} ∪ {{b_{1}, b_{2}, b_{3}, b_{4}, a_{5}}}, where

C_{4} = {{a_{i}, a_{j}, b_{i}, b_{j}} : {i, j} is a 2-subset of {1, 2, 3, 4}}

and C′ ∈ C_{5} if and only if a_{5} ∈ C′ ⊆ C∪Y, |C′∩{a_{i}, b_{i}}| = 1, for every i ∈ {1, 2, 3, 4}, and |C′ ∩ {b_{1}, b_{2}, b_{3}, b_{4}}| ∈ {0, 2}. By Lemma 3.1, C_{4} ∪ C_{5} is the set of circuits of M|(C ∪ Y) that intersects Y in at most two elements.

In this paragraph, we prove that C′ = Y ∪ {a_{5}}, when C′ ∈ C(M|(C ∪ Y)) \ (C_{4} ∪ C_{5}). By Lemma 3.4, every circuit of M|(C ∪ Y) intersects Y in an even number of elements. Thus, C′ must contain Y because C′ ∉ C_{4} ∪ C_{5}. There is an i ∈ {1, 2, 3, 4, 5} such that C′ ⊆ Y ∪ {a_{i}}, since circ(M) = 5. We prove that i ∉ {1, 2, 3, 4}. Suppose that i ∈ {1, 2, 3, 4}. By symmetry, we do not loose generality supposing i = 1. There is a circuit C′′ of M such that

C′′ ⊆ (C′ ∪ {a_{1}, a_{2}, b_{1}, b_{2}}) \ {b_{1}} = {a_{1}, a_{2}, b_{2}, b_{3}, b_{4}}.

By Lemma 3.5, {b_{1}, b_{2}, a_{3}, a_{4}} is a cocircuit of M|(C ∪ Y). By orthogonality, we have that b_{2} ∉ C′′. Hence C′′ ⊆ {a_{1}, a_{2}, b_{3}, b_{4}} is a proper subset of the circuit {b_{3}, b_{4}} ∪ Y_{{b_{3},b_{4}}} = {a_{1}, a_{2}, b_{3}, b_{4}, a_{5}}. We arrive at a contradiction. Hence i ∉ {1, 2, 3, 4}. Thus, C′ = Y ∪ {a_{5}}.

To conclude that M|(C ∪ Y) is isomorphic to J_{9}, we need to prove only that Y ∪ {a_{5}} is a circuit of M. If Y ∪ {a_{5}} is not a circuit of M, then, by the previous paragraph, Y ∪ {a_{5}} is an independent set of M. As r(M) = 5, it follows that Y ∪ {a_{5}} is a basis of M. So, there is a circuit C′′ of M such that a_{4} ∈ C′′ ⊆ Y ∪ {a_{4}, a_{5}}. By the previous paragraph, C′′ ∈ C_{4} ∪ C_{5}. Hence |C′′ ∩ Y | = 2 and C′′ ∈ C_{4}. We arrive at a contradiction and M|(C ∪ Y) is isomorphic to J_{9}.

Now, suppose that (2) holds. It is not difficult to see that X_{D} = X_{Y \D} for every 2-subsets D of Y. Consider

S = ⋂_{D} Y_{D},

where the intersection is taken over all 2-subsets D of Y. So, |S| = 2. To conclude that S is a series class of M|(C ∪ Y) we need only prove that Y is a circuit of M, since S is a series class of M|(C ∪ (Y \ {y})), by Lemma 3.4, for every y ∈ Y. Suppose that Y is not a circuit of M. First, we prove that Y ∪{b} is a circuit of M, for every b ∈ C \ S. Choose a 2-subset D of Y such that b ∈ X_{D}, say X_{D} = {a, b}. Hence D ∪ X_{D} and (Y \ D) ∪ X_{Y \D} = (Y \ D) ∪ X_{D} are circuits of M. So, there is a circuit C′ of M such that

C′ ⊆ [(D ∪ X_{D}) ∪ ((Y \ D) ∪ X_{D})] \ {a} = Y ∪ {b}.

Now, we prove that C′ = Y ∪ {b}. If C′ ≠ Y ∪ {b}, then there is y ∈ Y \ C′. Hence C′ is a circuit of M|(C ∪ (Y \ {y})) such that C′ ∩ C = {b}. We arrive at a contradiction by Lemma 3.4. Thus, C′ = Y ∪ {b}. Next, we prove that Y ∪ {e} is a circuit of M, for both elements e ∈ S. Let D′ be a 2-subset of Y. Suppose that Y_{D′} = S ∪ {b}. So, there is a circuit C′′ of M such that

e ∈ C′′ ⊆ [(Y ∪ {b}) ∪ (D′ ∪ Y_{D′})] \ {b} = Y ∪ S.

Observe that Y ⊂ C′′ because, for every y ∈ Y, every circuit of M|(C ∪ (Y \ {y})) that meets S must intersect C in three elements, by Lemma 3.4. As circ(M) = 5, it follows that C′′ = Y ∪ {e}. In summary, Y ∪ {f} is a circuit of M, for every f ∈ C. Thus, Y spans C ∪ Y in M. We arrive at a contradiction because r(Y ∪ C) = r(C) + 1 = 5. Hence Y is a circuit of M and S is a series class of M|(C ∪ Y). It is not difficult to see that M|(C ∪ Y)/e is isomorphic to AG(3, 2), for both elements e ∈ S.

Lemma 3.7. The matroid M\cl_{M}(C) is triangle-free.

Proof. Suppose that T is a triangle of M such that T ∩cl_{M}(C) = ∅. Choose X ∈ X such that |X∩T | = 2. Set Z = X∪T. Let D be a 2-subset of X such that D ≠ T ∩X. By Lemma 3.3, (X \ D) ∪ X_{D} is a triad of M|(C ∪ X). By orthogonality with T, C^{∗} = (Z \ D) ∪ X_{D} is a cocircuit of M|(C ∪ Z). Consider the circuit C′ = D ∪ Y_{D} of M. By Lemma 3.4, cl_{M|(C∪X)}(C′) = C′. If T \ X ⊆ cl_{M|(C∪Z)}(C′), then there is circuit C′′ of M such that T \X ⊆ C′′ ⊆ C′ ∪(T \X). We arrive at a contradiction, by orthogonality, because C^{∗} ∩ C′′ = T \ X. So, cl_{M|(C∪Z)}(C′) = C′. We define Y′ by replacing C by C′ in the definition of Y, that is,

Y′ = {Y : Y is a 4-subset of E(K′) such that every 3-subset of Y belongs to I(M)},

where K′ denotes the connected component of M/C′ having rank equal to one. If

(C ∪ Z) \ C′ = X_{D} ∪ (Z \ D) = C^{∗}

belongs to Y′, then M|(C′ ∪ C^{∗}) is isomorphic to J_{9} or is a series extension of AG(3, 2), by Lemma 3.6 applied taking C′ instead of C. In both cases, we arrive at a contradiction because T is a triangle of M|(C′ ∪ C^{∗}). So, C^{∗} ∉ Y′ and C^{∗} contains a triangle T′ of M. We arrive at a contradiction, by Lemma 3.1, because T′ is a circuit of M|(C ∪(Z \D)). Thus, T does not exist and the result follows.

Lemma 3.8. cl_{M}(C) = C.

Proof. Suppose that g ∈ cl_{M}(C) \ C. Choose X ∈ X. We prove that (X \ D) ∪ X_{D} is a triad of M|(C ∪ X ∪ {g}), for every 2-subset D of X. If (X \ D) ∪ X_{D} is not a triad of M|(C ∪ X ∪ {g}), for some 2-subset D of X, then, by Lemma 3.3, C^{∗} = (X \ D) ∪ X_{D} ∪ {g} is a cocircuit of M|(C ∪ X ∪ {g}). As C′ = D ∪ Y_{D} is a circuit of M with cardinality five and C′ ∩ C^{∗} = ∅, it follows that M|(C′ ∪ C^{∗}) is isomorphic to J_{9} or is a series extention of AG(3, 2), by Lemmas 3.6 and 3.7 applied to C′ instead of C. We arrive at a contradiction because these two matroids do not have a circuit spanning any element which does not belong to it. Hence (X\D)∪X_{D} is a triad of M|(C ∪ X ∪ {g}), for every 2-subset D of X.

Observe that S = ∩Y_{D}, where the intersection is taken over the 2-subsets D of X, is a series class of M|(C ∪ X), by Lemma 3.4. Let B be a basis of C such that S ⊆ B. As g ∈ cl_{M}(B), there is a circuit C′′ of M such that g ∈ C′′ ⊆ B ∪ {g}.

If D is a 2-subset of X such that X_{D} ⊈ B, then X_{D} ∩ C′′ = ∅, by orthogonality with the triad (X \ D) ∪ X_{D} of M|(C ∪ X ∪ {g}). Hence C′′ = S ∪ {g}. Thus, cl_{M}(S) \ S = cl_{M}(C) \ C.

In this paragraph, we prove that r(E(M)\cl_{M}(C)) ≥ 4. Suppose that r(E(M)\ cl_{M}(C)) = 3. So, E(M) \ cl_{M}(C) ⊆ cl_{M}(X). As S is a series class of M|(C ∪ X), it follows that

1 + r(M) = r(X ∪ (C \ S)) + r(S).

As S spans cl_{M}(C) \ C and X spans E(M) \ cl_{M}(C) in M, we have that

1 + r(M) = r((E(M) \ cl_{M}(C)) ∪ (C \ S)) + r(S ∪ (cl_{M}(C) \ C)).

We arrive at a contradiction because M is 3-connected and {(E(M) \ cl_{M}(C)) ∪ (C \ S), S ∪ (cl_{M}(C) \ C)} is a partition of E(M). Hence r(E(M) \ cl_{M}(C)) ≥ 4.

Suppose that Y is a 4-subset of E(M) \ cl_{M}(C) and that r(Y) = 4. By Lemma 3.6, M|(C ∪ Y) is isomorphic to J_{9}. So, for each 3-subset X of Y, there is S_{X}, which is the non-trivial series class of M|(C ∪ X), such that S_{X} ∪ {g} is a circuit of M, by the second paragraph. Hence S_{X} ∪ S_{X′} contains a circuit of M, when X ≠ X′, which is properly contained in C. We arrive at a contradiction and g does not exist.

Corollary 3.1. E(M) \ C is a cocircuit of M.

Proof. By Lemma 3.8, cl_{M}(C) = C. As r(M) = r(C) + 1, it follows that C is a hyperplane of M. Thus, E(M) \ C is a cocircuit of M.

Lemma 3.9. If Y ⊆ E(M) \ C is a 4-circuit of M, then E(M) = C ∪ Y.

Proof. Suppose that Y ≠ E(M) \ C. By Lemma 3.6(ii), there is a 2-subset S of C such that S is a series class of M|(C ∪Y).We prove that r(E(M)\C) > 3. Suppose that r(E(M) \ C) = 3. By Lemmas 3.7 and 3.8, we have that M|(E(M) \ C) is isomorphic to U_{3,|E(M)\C|}. Thus, S is a series class of M because Y spans E(M)\C. We arrive at a contradiction because M is 3-connected. Hence r(E(M) \ C) ≥ 4.

Let Z be a 4-element subset of E(M) \ C such that r(Z) = 4 and |Z ∩ Y | = 3. Choose a 2-subset D of Z such that Z \ Y ⊆ D. As D ∪ Y_{D} is a circuit of M having five elements, it follows, by Corollary 3.1, that

C^{∗} = (C ∪ Y ∪ Z) \ (D ∪ Y_{D}) = X_{D} ∪ (Y \ D)

is a cocircuit of M|(C ∪ Y ∪ Z). By Lemma 3.6(i) applied to M|(C ∪ Z), we have that |X_{D} ∩ S| = 1. By Lemma 3.6(ii) applied to M|(C ∪ Y), for each 2-subset W of C \ S, there is a partition {D_{1}, D_{2}} of Y such that X_{D_{1}} = X_{D_{2}} = W. Choose W and D_{1} such that W ∩ X_{D} = ∅ and |(Y \ D) ∩ D_{1}| = 1. So,

(D_{1}∪X_{D_{1}})∩C^{∗} = (D_{1}∪X_{D_{1}})∩[X_{D}∪(Y \D)] = [(Y \D)∩D_{1})]∪(X_{D_{1}} ∩X_{D}) = (Y \D)∩D_{1}.

We arrive at a contradiction, by orthogonality, because D_{1} ∪ X_{D_{1}} is a circuit of M.

Corollary 3.2. If Y ∈ Y, then Y is independent in M.

Proof. Suppose that Y is a circuit of M. Thus, by Lemma 3.9, E(M) = C ∪ Y. We arrive at a contradiction to the fact that M is 3-connected because, by Lemma 3.6(ii), M is a non-trivial series extension of AG(3, 2).

Lemma 3.10. Suppose that Z is a 5-subset of E(M) \ C such that Z \ {f} is independent in M, for every f ∈ Z. Then M|(C ∪ Z) is isomorphic to J_{10}. In particular, Z is an independent set of M.

Proof. For each f ∈ Z, by Lemma 3.6(i), there is a function ψ_{f} : Z \ {f} → C such that

(3.3) if D = {a, b} is a 2-subset of Z \ {f}, then X_{D} = {ψ_{f}(a), ψ_{f}(b)}.

When f and g are different elements of Z, then the restrictions of ψ_{f} and ψ_{g} to Z \ {f, g} agree, by equation (3.3). Hence there is a function ψ : Z → C such that ψ_{f} is the restriction of ψ to Z \ {f}, for every f ∈ Z.

By Lemma 3.6(i), when C′ ≠ Z and C′ ⊆ C ∪Z, then C′ is a circuit of M|(C ∪Z) if and only if there is a 2-subset {a, b} of Z such that C′ = {a, b, ψ(a), ψ(b)} or |C′ ∩ {a, ψ(a)}| = 1, for every a ∈ Z, and |C′ ∩ Z| is even. Moreover, these are the circuits of M|(C ∪ Z) which have at most four elements in common with Z. Hence M|(C ∪ Z) is isomorphic to J_{10} unless Z is a circuit of M. Suppose that Z is a circuit of M. Thus, Z ∪ {a} is a Tutte-line of M, for every a ∈ C, since (Z \ {ψ^{−1}(a)} ∪ {a} is a circuit of M. So, (Z \ {b}) ∪ {a} contains a circuit of M, for every a ∈ C and b ∈ Z. We arrive at a contradiction by Lemma 3.6(i).

Proposition 3.1. Suppose that M is a 3-connected matroid. If r(M) = circ(M) = 5, then M is isomorphic to J_{9} or J_{10}.

Proof. From Lemma 3.8, we have cl_{M}(C) = C. By Lemma 3.7 and Corollary 3.2, every circuit of M\C has five elements because circ(M) = 5. If |E(M) \ C| ≤ 5, then the result follows from Lemmas 3.4, 3.6 and 3.10. So, we may suppose that |E(M) \ C| ≥ 6. By Lemma 3.10, every 5-subset of E(M) \ C is independent in M. Hence E(M) \ C is independent in M, otherwise it contains a circuit with at least six elements. We have a contradiction because r(M) = 5 and the result follows.

4. The main results

Note that Theorem 1.1 is a consequence of Propositions 2.1 and 3.1. In this section, we prove a result that is strong than Conjecture 1.1 in the case d = 3.

Theorem 4.1. Suppose that d = 3. Let M be a d-connected matroid non-isomor-phic to U_{1,1}, F_{7}^{∗}, AG(3, 2), J_{9}, or J_{10}. If

d ≥ \frac{r(M) + 1}{2},

then M has a circuit of size r(M) + 1.

Proof. As d = 3, it follows that r(M) ≤ 5. Thus, the result follows from Theorem 1.1

When M is isomorphic to F_{7}^{∗}, AG(3, 2), J_{9}, or J_{10}, then M has a circuit of size equal to r(M). Moreover, every circuit of M having size equal to r(M) is a circuithyperplane of M. To see the relevance of circuits which are also hyperplanes we refer, for example, to [9], [10], [15], [16], [17], [19], [21], [23] and [24].

Acknowlegements

The authors thank the referee for pointing out some mistakes and suggesting improvements. The second author was partially supported by CNPq, FINEP and PRONEX 107/97.

References

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

[2] G. Ding, B. Oporowski, J. Oxley and D. Vertigan, Unavoidable minors of large 3-connected binary matroids, J. Combin. Theory Ser. B 66 (1996), 334-360.

[3] G. Ding, B. Oporowski, J. Oxley and D. Vertigan, Unavoidable minors of large 3-connected matroids, J. Combin. Theory Ser. B 71 (1997), 244-293.

[4] W. Hochstättler and B. Jackson, Large circuits in binary matroids of large cogirth I, J. Combin. Theory Ser. B 74 (1998), 35-52.

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

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

[7] B.M. Junior, Connected matroids with a small circumference, submitted.

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

[9] M. Lemos, Non-binary matroids having at most three non-binary elements, Combin. Probab. Comput. 3 (1994), 355-369.

[10] M. Lemos, Non-binary matroids having four non-binary elements, Ars Combin. 46 (1997), 97-117.

[11] M. Lemos and J. Oxley, On packing minors into connected matroids, Discrete Math. 189 (1998), 283-289.

[12] M. Lemos and J. Oxley, On removable circuits in graphs and matroids, J. Graph Theory 30 (1999), 51-66.

[13] M. Lemos and J. Oxley, On size, circumference and circuit removal in 3-connected matroids, Discrete Math. 220 (2000), 145-157.

[14] M. Lemos and J. Oxley, A sharp bound on the size of a connected matroid, Trans. Amer. Math. Soc., to appear.

[15] A.D. Mills, On matroids with many common basis, Discrete Math. 203 (1999), 195-205.

[16] A.D. Mills and J.G Oxley, A class of non-binary matroids with many binary minors, Discrete Math. 207 (1999), 173-187.

[17] B. Oporowski, J. Oxley and G. Whittle, On the excluded minors for the matroids that are either binary or ternary, submitted.

[18] J.G. Oxley, The binary matroids with no 4-wheel minor, Trans. Amer. Math. Soc. 301 (1987), 63-75.

[19] J.G. Oxley, A characterization of the ternary matroids with no M(K_{4})-minor, J. Combin. Theory Ser. B 42 (1987), 212-249.

[20] J.G. Oxley, On circuit exchange properties for matroids, Europ. J. Combin. 9 (1988), 331-336.

[21] J.G. Oxley, A characterization of a class of non-binary matroids, J. Combin. Theory Ser. B 49 (1990), 181-189.

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

[23] J.G. Oxley, Structure theory and connectivity for matroids, Contemporary Mathematics 197 (1996), 129-170.

[24] J. Oxley and G. Whittle, On weak maps of ternary matroids, Europ. J. Combin. 19 (1998), 377-389.

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

Departamento de Matemática e Estatística, Universidade Federal da Paraíba, Campina Grande, Paraíba, 58105-305, Brazil

   E-mail address: bmj@dme.ufpb.br

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

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