MATROIDS WITH MANY COMMON BASES

MANOEL LEMOS

Abstract. In [5], Lemos proved a conjecture of Mills [7]: for two (k + 1)- connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n_{1} circuit-hyperplanes and from the other by relaxing n_{2} circuit-hyperplanes, where n_{1} and n_{2} are non-negative integers such that n_{1} + n_{2} ≤ k. In this paper, we prove a similar result, where the hypothesis of the matroids being k-connected is replaced by the weaker hypothesis of being vertically k-connected.

1. Introduction

In this article, for matroid theory we shall use the notation set by Oxley in [13], which we assume familiar to the reader. We define the connectivity function of a matroid M as

ξ_{M}(X, Y) = r(X) + r(Y) − r(M),

for a partition {X, Y } of E(M). Tutte [19] said that a matroid M is n-connected, for a positive integer n, provided

ξ_{M}(X, Y) ≥ k

for every integer k and partition {X, Y } of E(M) such that k < n and

min{|X|, |Y |} ≥ k.

Lemos [5] proved, up to small modifications, the following conjecture made by Mills [7].

Conjecture 1.1. Let k be a positive integer. Suppose M_{1} and M_{2} are (k + 1)- connected matroids on a set E where |E| ≥ 2. If |B(M_{1}) △ B(M_{2})| = k, then there is an integer j ∈ [0, k] and a matroid N on E that is obtained from M_{1} and M_{2} by relaxing j and k − j circuit-hyperplanes, respectively.

Observe that, for r ≥ 1, U_{r−1,2r−1} and U_{r,2r−1} are m-connected matroids for every positive integer m. As these matroids have different rank, it follows that

|B(U_{r−1,2r−1}) △ B(U_{r,2r−1})| = |B(U_{r−1,2r−1}) ∪ B(U_{r,2r−1})| = 2 (\begin{matrix}2r − 1 \\ r \end{matrix}) = f(r).

When k = f(r), this pair of matroids is a counter-example to Conjecture 1.1. Lemos [5] proved that these are the only exceptions and that the hypothesis on the size of E can be removed from this conjecture.

In [7], Mills proved this conjecture for k = 2 and pointed out that it follows from Truemper’s results when k = 1 [17]. In general, this conjecture follows from a theorem which guarantees the same conclusion with weaker hypotheses. To state this result, we need some definitions.

The author is partially supported by CNPq, FINEP and ProNEx 107/97.

For a matroid M, the girth of M is defined as

g(M) = min{|C| : C ∈ C(M)},

where this minimum is taken to be 0, when C(M) = ∅. We say that (M, N) is a k-pair, for a non-negative integer k, when N is a matroid having the same ground set as M and |B(M) △ B(N)| ≤ k. Observe that this definition is invariant under duality; that is, (M, N) is a k-pair if and only if (M^{∗}, N^{∗}) is a k-pair. Lemos [5] proved:

Theorem 1.1. Let k be a positive integer. If (M_{1}, M_{2}) is a k-pair and

min{g(M_{1}), g(M_{1}^{∗})} ≥ k + 1,

then there is a matroid N which is obtained from M_{1} and M_{2} by relaxing n_{1} and n_{2} circuit-hyperplanes, respectively, where n_{1} and n_{2} are non-negative integers such that

n_{1} + n_{2} = |B(M_{1}) △ B(M_{2})| ≤ k.

In this theorem, if we replace the hypothesis of (M_{1}, M_{2}) to be a k-pair by to be a l-pair, for some l > k, then the conclusion does not hold, as we shall see in the next example. Let E and A be an n-element set and a r-element set, respectively, such that A ⊆ E, where 2r > n. Choose a ∈ A. Suppose that M_{1} and M_{2} are matroids over E having every r-element set as a basis with the exception of these that contains A or A \ {a}, respectively. Observe that

g(M_{1}) = r, g(M_{2}) = r − 1 and g(M_{1}^{∗}) = g(M_{2}^{∗}) = n − r.

So, M_{1} and M_{2} are (n−r)-connected, since n−r < r, by hypothesis. We have that

B(M_{1}) △ B(M_{2}) = {(A \ {a}) ∪ {b} : b ∈ E \ A}.

Hence (M_{1}, M_{2}) is a (n − k)-pair.

An n-connected matroid M such that |E(M)| ≥ 2n − 2 must satisfy

min{g(M), g(M^{∗})} ≥ n. (1.1)

As a consequence of the previous result, Lemos [5] obtained the following theorem that proves Mills’s Conjecture.

Theorem 1.2. For some positive integer k, suppose that M_{1} and M_{2} are (k + 1)- connected matroids having the same ground set E. If |B(M_{1}) △ B(M_{2})| = k, then either

(a) there is an integer j ∈ [0, k] and a matroid N on E that is obtained from M_{1} and M_{2} by relaxing j and k − j circuits-hyperplanes, respectively; or

(b) there is a positive integer r such that

2 (\begin{matrix}2r − 1 \\ r \end{matrix}) = k

and {M_{1}, M_{2}} = {U_{r−1,2r−1}, U_{r,2r−1}}.

Condition (1.1) is very strong. This happens because the definition of n-connec-ted matroid proposed by Tutte has the attractive property of being invariant under duality but it does not generalize the notion of an n-connected graph. To generalize it, we need a new definition (see [9, 10]). We say that a matroid M is vertically n-connected, for a positive integer n, provided

ξ_{M}(X, Y) ≥ k

for every integer k and partition {X, Y } of E(M) such that k < n and

min{r(X), r(Y)} ≥ k.

Observe that every vertically n-connected matroid is n-connected, but the reverse does not occur. When M is a vertically n-connected matroid such that r(M) ≥ n, then

g(M^{∗}) ≥ n. (1.2)

Note that this condition is much weaker than (1.1).

To state the main result of this paper, we need to describe an operation that generalizes the relaxation of a circuit-hyperplane. We say that a hyperplane H of a matroid M is a tip-hyperplane having tip e provided e ∈ H, r(M) ≤ |H| and M|H is obtained from M|(H \ {e}) by adding e freely. Hence

C_{e}(M|H) = {B ∪ {e} : B ∈ B(M|(H \ {e}))}.

In particular, every circuit of M|H that contains e has size equal to r(M). In section three, we shall prove that B(M) ∪ C_{e}(M|H) is the set of bases of a matroid which we say that is obtained from M by relaxing the tip-hyperplane H.

Theorem 1.3. For some positive integer k, suppose that M_{1} and M_{2} are vertically (k +1)-connected matroids having the same ground set E. If |B(M_{1})△B(M_{2})| ≤ k, then:

(i) there is a matroid N on E that is obtained from each of M_{1} and M_{2} by relaxing a sequence of tip-hyperplanes. Moreover,

B(M_{1}) △ B(M_{2}) = [B(N) \ B(M_{1})] ∪ [B(N) \ B(M_{2})]; or

(ii) for each i ∈ {1, 2}, r(M_{i}) ≤ k and M_{i} does not have disjoint cocircuits.

Suppose that M_{1} and M_{2} are matroids over the same ground set. When M_{i} does not have disjoint cocircuits, for each i ∈ {1, 2}, then M_{i} is a vertically n-connected matroid for every n. So, the pairs of matroids described in (ii) appear because we do not ask in the definition of a vertically n-connected matroid that its rank is at least n — that is, we permit small matroids to be vertically n-connected.

Observe that Theorem 1.2 is a consequence of this theorem.

2. Preliminary results

By (1.2), we need results about k-pairs having a matroid on it with large cogirth. We obtain it by combining Lemmas 1 and 2 of [5] in the following result:

Lemma 2.1. Let k be a positive integer. If (M_{1}, M_{2}) is a k-pair and g(M_{1}^{∗}) ≥ k+1, then

(i) r(M_{1}) = r(M_{2}); and (ii) I(M_{1}) ∩ C(M_{2}) ⊆ B(M_{1}).

Lemma 2.2. Let k be a positive integer. If (M_{1}, M_{2}) is a k-pair and

min{g(M_{1}^{∗}), g(M_{2}^{∗})} ≥ k + 1,

then

C = B(M_{1}) △ B(M_{2}),

where C is the set of minimal elements belonging to C(M_{1}) △ C(M_{2}).

Proof. When C ∈ C, there is an i ∈ {1, 2} such that C ∈ C(M_{i}) ∩ I(M_{3−i}). Thus, by Lemma 2.1(ii), we have that C ∈ B(M_{3−i}). Hence

C ⊆ B(M_{1}) △ B(M_{2}). (2.1)

Now, let B be an element of B(M_{1}) △ B(M_{2}). So, there is an i ∈ {1, 2} such that B ∈ B(M_{i}) and, by Lemma 2.1(i), B contains a circuit C of M_{3−i}. Thus, C ∈ C. Hence, by (2.1) and Lemma 2.1(i), C = B. So,

C = B(M_{1}) △ B(M_{2})

and the result follows.

For a matroid M, a subset L of E(M) is said to be a Tutte-line, when M|L has corank equal to two and no coloops. In [18], Tutte proved that L has a partition, which we call the canonical partition of L in M, {P_{1}, P_{2}, …, P_{n}}, for some n ≥ 2, such that C(M|L) = {L \ P_{1}, L \ P_{2}, …, L \ P_{n}}. We denote by T L(M) the set of Tutte-lines of the matroid M. Following Tutte [18], we say that a set of circuits L of a matroid M is a linear subclass of M, when C(M|L) ⊆ L for every L ∈ T L(M) such that |C(M|L) ∩ L| ≥ 2.

By Lemma 2.2, the hypotheses of the next lemma is satisfied provided (M_{1}, M_{2}) is a k-pair such that min{g(M_{1}^{∗}), g(M_{2}^{∗})} ≥ k + 1. This also occurs, when M_{2} is obtained from M_{1} by relaxing some circuit-hyperplanes, or more generally, when M_{2} is obtained from M_{1} by transforming a special set of circuits each having r(M_{1}) elements into bases.

Lemma 2.3. Let M_{1} and M_{2} be matroids having the same rank and ground set such that

C = B(M_{1}) △ B(M_{2}),

where C is the set of minimal elements belonging to C(M_{1})△C(M_{2}). If C ∈ C∩C(M_{1}) and Z = cl_{M_{1}}(C), then

(i) If L is a Tutte-line of M_{1} such that L ⊆ Z and C ∩ C(M_{1}|L) ≠ ∅, then L contains just one circuit C_{L} of M_{2} and

C(M_{1}|L) \ {C_{L}} = {L \ {a} : a ∈ C_{L}} ⊆ C.

Moreover, C_{L} ∈ C(M_{1}) provided C_{L} ≠ L. (ii) C(M_{1}|Z) \ C is a linear subclass of M_{1}|Z. (iii) {D ∈ C(M_{2}) \ C(M_{1}) : D ∩ Z ∉ I(M_{1})} = C_{1} ∪ C_{2}, where

C_{1} = {L ∈ T L(M_{1}|Z) : C(M_{1}|L) ⊆ C}

C_{2} = {D∪{e} : D ∈ C∩C(M_{1}|Z), e ∈ E(M_{1})\Z and C∩C(M_{2}|(D∪{e})) = ∅}.

Proof. (i) Let C′ a circuit belonging to C(M_{1}|L) ∩ C. Note that cl_{M_{1}}(C′) = Z. As C is a basis of M_{2}, it follows that r_{M_{2}}(L) = r_{M_{1}}(L) + 1 = |L| − 1. Thus, L contains exactly one circuit C_{L} of M_{2}. We have two possibilities for C_{L}.

First, suppose that C_{L} is also a circuit of M_{1}. If C′ ∈ C(M_{1}|L)\{C_{L}}, then C′ is independent in M_{2} because C_{L} ⊈ C′ ⊂ L. So, C′ ∈ C. Hence |C′| = r(M_{1}) = |L|−1 and C′ = L \ {a}, for some a ∈ C_{L}. Thus, C(M_{1}|L) = {C_{L}} ∪ {L \ {a} : a ∈ C_{L}}.

Next, suppose that C_{L} is not a circuit of M_{1}. If C′ ∈ C(M_{1}|L) and |C′| < r(M_{1}), then, by hypothesis, C′ is also a circuit of M_{2} and so C′ = C_{L}. We have a contradiction and hence |C′| ≥ r(M_{1}) = |L| − 1, for every circuit C′ of M_{1}|L. Thus, |C′| = |L| − 1, for every circuit C′ of M_{1}|L. In particular, C(M_{1}|L) = {L \ {a} : a ∈ L}. As C_{L} is not a circuit of M_{1}, it follows that |C_{L}| ≥ r(M_{1}), by hypothesis. Hence C_{L} = L.

(ii) If L is a Tutte-line of M_{1}|Z containing at least one circuit that belongs to C, then, by (i), it contains at most one circuit that does not belong to C which is C_{L} when C_{L} ≠ L. By definition, L = C(M_{1}|Z) \ C is a linear subclass of M_{1}|Z.

(iii) If C′ ∈ {D ∈ C(M_{2}) \ C(M_{1}) : D ∩ Z ∉ I(M_{1})}, then C′ contains properly a circuit C′′ of M_{1}|Z. So, C′′ ∈ C and |C′| = |C′′| + 1. When C′ ⊆ Z, then C′ is a Tutte-line of M_{1}|Z and, by (i), C(M_{1}|C′) ⊆ C. So, C′ ∈ C_{1}. Thus, we may suppose that C′ ⊈ Z. As C′′ ⊆ Z ∩ C′ and |C′| = |C′′| + 1, it follows that C′ \ Z = {e}. Hence C′ = C′′ ∪ {e} and C′ ∈ C_{2}.

Next, we prove that C′′ ∪ {e} is a circuit of M_{2}, for every e ∉ Z and C′′ ∈ C ∩ C(M_{1}|Z) such that C(M_{2}|(C′′ ∪ {e})) ∩ C = ∅. This happens because C′′ ∪ {e} is dependent in M_{2}, C′′ is a basis of M_{2}, every circuit of M_{2}|(C′′ ∪ {e}) having at most r(M_{1}) = r(M_{2}) elements is also a circuit of M_{1} and Z does not span e in M_{1}. So, every set belonging to C_{2} is a circuit of M_{2}. With similar arguments, we conclude that every set belonging to C_{1} is a circuit of M_{1} and the result follows.

3. A generalization of the relaxation

We say that a circuit C of a matroid M is large, when r(M) = |C|. Let LC(M) and CH(M) be the sets of large circuits of M and circuit-hyperplanes of M, respectively. Thus, CH(M) ⊆ LC(M). Kahn proved that, for each X ⊆ CH(M), there is a matroid M_{X} such that

B(M_{X}) = B(M) ∪ X .

We say that M_{X} is obtained from M by relaxing the circuit-hyperplanes belonging to X. Moreover,

CH(M_{X}) = CH(M) \ X .

By this identity, one can arrive at the matroid M_{X} by relaxing the circuit-hy-perplanes belonging to X one at each time — this construction is independent of the chosen order for relaxing the circuit-hyperplanes. To see the relevance of this construction we refer, for example, to [3, 4, 6, 7, 8, 11, 12, 14, 16, 19]. In this section, we shall discuss an extension of this construction, where we take X to be a set of large circuits of M which must satisfies a special condition. In the previous subsection, we obtained the necessary conditions that X must satisfy and, in this section, we shall prove that these conditions are also sufficient.

We say that Z is a nest of a matroid M, when Z = cl_{M}(C), for some C ∈ LC(M). Observe that Z = cl_{M}(C′), for every C′ ∈ LC(M) such that C′ ⊆ Z. When a circuit-hyperplane C′′ of M is contained in a nest Z of M, then Z = C′′.

Suppose that C is a large circuit of a matroid M. Let Z be the nest of M that contains C. In this subsection, we shall consider a liner subclass L of M|Z satisfying

L ≠ C(M|Z) and C(M|Z) \ HAM(M|Z) ⊆ L,

where HAM(H) denotes the set of Hamiltonian circuits of a matroid H. (The existence of Hamiltonian circuits in a matroid is very important: nice applications of them can be found in [1, 2].) A linear subclass of M|Z satisfying these conditions will be called admissible. Now, we shall construct a family of sets, similar to the family described in Lemma 2.3(iii), and prove that it is a family of circuits of a matroid. We set

S_{L} = {C′ ∪ {e} : C′ ∈ C(M|Z) \ L and e ∈ E(M) \ Z}
T_{L} = {L : L ∈ T L(M|Z) and C(M|L) ∩ L = ∅}

We shall prove that

C_{L} = [C(M) \ (C(M|Z) \ L)] ∪ S_{L} ∪ T_{L}

is the set of circuits of a matroid, which we shall denote by M_{Z,L}. We say that this matroid is obtained from M by relaxing the nest Z along the admissible linear subclass L of M|Z. Thus, B(M_{Z,L}) = B(M) ∪ (C(M|Z) \ L).

Suppose that C_{1} and C_{2} are different sets belonging to C_{L}. We need to show only that

(C_{1} ∪ C_{2}) \ {e}

contains an element of this family, for every e ∈ C_{1} ∩ C_{2}. First, we shall prove a lemma.

Lemma 3.1. If X ⊆ E(M) and |X| = r(M) + 1, then X contains a member of C_{L}.

Proof. Observe that X contains a circuit C′ of M. If C′ also belongs to C_{L}, then the result follows. So, we may suppose that C′ does not belong to this family. Thus, C′ ∈ C(M|Z) \ L. In particular, |X \ Z| ≤ 1. When X \ Z = {e}, then X = C′ ∪ {e} and X belongs to S_{L}. So, we may suppose that X is contained in Z. In this case, X is a Tutte-line of M|Z. Moreover, we may suppose that every circuit of M contained in X belongs to C(M|Z) \ L, otherwise the result follows. Hence X belongs to T_{L} and the result follows.

By Lemma 3.1, we may suppose that |C_{1} ∪C_{2}| ≤ r(M)+1, otherwise (C_{1} ∪C_{2})\ {e} has at least r(M) + 1 elements and contains an element of C_{L}. As C_{1} and C_{2} are different, it follows that |C_{i}| ≤ r(M), for every i ∈ {1, 2}. Hence

{C_{1}, C_{2}} ⊆ L ∪ (C(M) \ C(M|Z)).

So, there is circuit C_{3} of M such that

C_{3} ⊆ (C_{1} ∪ C_{2}) \ {e}.

If |C_{3}| < r(M), then C_{3} belongs to C_{L} because C(M|Z) \ HAM(M|Z) ⊆ L. So, we may suppose that |C_{3}| = r(M) and that C_{3} ∈ C(M|Z)\L. Hence C_{1}∪C_{2} = C_{3}∪{e} is a Tutte-line. As C_{3} ⊆ Z, it follows that C_{1} ∪ C_{2} ⊆ Z, since Z is a closed set in M. In particular, {C_{1}, C_{2}} ⊆ L. By the definition of a linear subclass, we have that C_{3} ∈ L because both C_{1} and C_{2} belongs to L. We have a contradiction. Thus, C_{L} is a family of circuits of a matroid that is different of M because L ≠ C(M|Z).

When max{|C′| : C′ ∈ L} < r(M), then

L = C(M|Z) \ HAM(M|Z) = C(M_{Z,L}|Z) \ HAM(M_{Z,L}|Z). (3.1)

That is, M_{Z,L}|Z and M|Z have the same non-spanning circuits. Matroids having the same non-spanning circuits have been considered by Oxley an Wittle in [15]. We are not using theirs results here, since, there are cases where the condition stated at the beginning of this paragraph does not hold and (3.1) is not true.

The next lemma has a straitforward proof. So, it will be omitted. In it, we show that loops are irrelevant to our construction.

Lemma 3.2. Suppose that r(M) ≥ 2. If l is a loop of M|Z, then l is a loop of M_{Z,L}. Moreover,

(i) Z \ {l} is a nest of M\l. (ii) L \ {{l}} is an admissible linear subclass of (M\l)|(Z \ {l}). (iii) M_{Z,L}\l = (M\l)_{Z\{l},L\{{l}}}.

Now, we shall prove the last result of this section.

Lemma 3.3. If Z′ is a nest of M different of Z, then Z′ is a nest of M_{Z,L}. Moreover, M|Z′ = M_{Z,L}|Z′.

Proof. First, we shall prove that

LC(M_{Z,L}) = LC(M) \ (C(M|Z) \ L). (3.2)

As r(Z ∩ Z′) < r(M) − 1, it follows that every large circuit of M contained in Z′ has at most r(M)−2 elements belonging to Z. That is, this circuit is a large circuit of M_{Z,L}. Thus, (3.2) holds because every large circuit of M that do not belong to C(M|Z) is contained in a nest of M different of Z.

Observe that every element of S_{L} intersects Z′ in at most r(M)−1 elements and every element of T_{L} instersects Z′ in at most r(M)−2 elements. Hence |C \Z′| ≥ 2, for every C ∈ S_{L} ∪ T_{L}. So, C(M|Z′) = C(M_{Z,L}|Z′) and Z′ is closed in M_{Z,L}. The result follows.

This lemma is very important because we can fix a set of nests of M and for each nest in this family we can choose an admissible liner subclass of M restricted to this nest, when it exists. When we relax one of these nests along its admissible linear subclass, the other nests are nests of the resulting matroid and the admissible linear subclasses associated with them retains this property in the new matroid. So, we can continue with the process (and the order is irrelevant). Thus, this construction behaves similarly as the relaxing of a set of circuits-hyperplanes. Moreover, it agrees with it when every nest is a circuit-hyperplane.

4. A result similar to Theorem 1.1

In this section, we shall prove a result that plays a similar role in the proof of Theorem 1.3 as did Theorem 1.1 in the proof of Theorem 1.2.

Theorem 4.1. Let k be a positive integer. If (M_{1}, M_{2}) is a k-pair and

min{g(M_{1}^{∗}), g(M_{2}^{∗})} ≥ k + 1,

then there is a matroid N which is obtained from M_{i}, for both i ∈ {1, 2}, by relaxing a sequence of nests (each along an admissible linear subclass of M_{i} restricted to it) such that

B(M_{1}) △ B(M_{2}) = (B(N) \ B(M_{1})) ∪ (B(N) \ B(M_{2})).

Proof. We prove this result by induction on |B(M_{1}) △ B(M_{2})|. When |B(M_{1}) △ B(M_{2})| = 0, we have that M_{1} = M_{2}. In this case, we take N = M_{1} = M_{2} and the result follows. So, we may suppose that |B(M_{1}) △ B(M_{2})| > 0. By Lemma 2.2, C = B(M_{1})△B(M_{2}), where C is the set of minimal elements belonging to C(M_{1})△C(M_{2}). In particular, C ≠ 0. Choose C ∈ C. Without loss of generality, we may suppose that C ∈ C(M_{1}). Set Z = cl_{M_{1}}(C). By Lemma 2.3, L = C(M_{1}|Z) \ C is a linear subclass of M_{1}|Z. Observe that this linear subclass is admissible in M_{1}|Z. Let N_{1} be the matroid obtained from M_{1} by relaxing the nest Z along the linear subclass L of M_{1}|Z. Thus,

B(N_{1}) = B(M_{1}) ∪ (C(M_{1}|Z) \ L) = B(M_{1}) ∪ (C ∩ C(M_{1}|Z)).

As C = B(M_{1}) △ B(M_{2}), it follows that C ∩ C(M_{1}|Z) ⊆ B(M_{2}) \ B(M_{1}) and so

B(N_{1}) △ B(M_{2}) = [B(M_{1}) △ B(M_{2})] \ [C ∩ C(M_{1}|Z)].

The result follows by induction because |B(N_{1}) △ B(M_{2})| < |B(M_{1}) △ B(M_{2})| and B(N_{1}) \ B(M_{1}) = C ∩ C(M_{1}|Z).

Next, we will prove a result similar to Theorem 1.2 for vertically (k+1)-connected matroids, namely Theorem 1.3. This result will be a consequence of Theorem 4.1 and a lemma that will be proved in the next section: it describes the structure of the admissible linear subclasses of M_{i} restricted to a nest, when (M_{1}, M_{2}) is a k-pair that satisfies the hypothesis of Theorem 4.1. The linear subclasses are quite simple: it is the set of circuits contained in the nest that do not contain an element. This is a very strong structural result, since linear subclasses are closed related to one-element lifts of matroids, as we will explain in the next paragraph.

When M is a matroid and L is a linear subclass of M, we can obtain an oneelement lift of M using this linear subclass. Choose e ∉ E(M). Consider the following family of sets:

L ∪ {C ∪ {e} : C ∈ C(M) \ L} ∪ {L ∈ T L(M) : C(M|L) ∩ L = ∅}.

This family is a family of circuits of a matroid N such that N/e = M. Moreover, any one-element lift of M is obtained in this way. Thus, when this linear subclass is the set of circuits of M that do not contain an element, say f, then the lift of M that we obtain using this linear subclass is the one obtained from M by inserting e in series with f (when f is not a coloop of M).

5. Proof of the main result

Lemma 5.1. Let C be a large circuit of a matroid M. If Z = cl_{M}(C) and L is an admissible linear subclass of M|Z such that

|C(M|Z) \ L| ≤ |C|,

then there is a series class S of M|Z such that C(M|(Z \ S)) = L.

Proof. When |Z \ C| = 0, we take S = Z. When |Z \ C| = 1, then Z is a Tutte-line of M. If Z does not contain a circuit of L, then every circuit of M contained in Z is large. Thus, C(M|Z) = {Z \ {a} : a ∈ Z}. So,

|C| + 1 = |Z| = |C(M|Z)| = |C(M|Z) \ L| ≤ |C|,

where the last inequality follows by hypothesis. We arrive at a contradiction. Hence Z contains a circuit D of L. Observe that S = Z \ D is a series class of M|Z with the desired property. So, we may suppose that |Z \ C| ≥ 2.

For each z ∈ Z \ C, C ∪ {z} is a Tutte-line of M. By the first paragraph, let C_{z} be the circuit of C ∪ {z} that belongs to L. By Lemma 2.3(i), we have that (C ∪ {z}) \ {w} is a circuit of M|Z that does not belong to L, for every w ∈ C_{z}. Set

C_{z} = {(C ∪ {z}) \ {w} : w ∈ C_{z} \ {z}}.

Observe that every circuit belonging to C_{z} contains exactly one element not belonging to C, namely z. Hence C_{z} ∩ C_{w} = ∅, when z ≠ w. Thus,

|C(M|Z) \ L| ≥ |{C}| + ∑_{z∈Z\C} |C_{z}| = 1 + ∑_{z∈Z\C} |C ∩ C_{z}|.

By hypothesis, we have that

|C| ≥ |C(M|Z) \ L| ≥ 1 + ∑_{z∈Z\C} |C ∩ C_{z}| ≥ 1 + | ⋃_{z∈Z\C} C ∩ C_{z}| .

In particular, we have that

| ⋃_{z∈Z\C} C ∩ C_{z}| ≤ |C| − 1.

So,

W = ⋃_{z∈Z\C} C ∩ C_{z}

is a proper subset of C. As C \ W is contained in a series class of M|C and W spans Z \ C in M|Z, it follows that C \ W is contained in a series class S of M|Z. Note that S = C \ W because every element of W belongs C_{z}, for some z ∈ Z \ C, and so it could not belong to the series class S.

Now, we shall prove that L ⊆ C(M|(Z \S)). Suppose that D ∈ L\C(M|(Z \S)). So, S ⊆ D. By Lemma 3.43 of [20], there is a Tutte-line L of M|Z such that D ⊂ L and C(M|L) ∩ L = {D}. Hence, by Lemma 2.3(i),

C = {L \ {d} : d ∈ D} ⊆ C(M|Z) \ L.

As C is disjoint of C_{z}, since the circuits in the first set contains S and the circuits in the second set does not contain S, for every z ∈ Z \ C, it follows that

|C(M|Z) \ L| ≥ |{C}| + |C| + ∑_{z∈Z\C} |C_{z}| = 1 + |D| + ∑_{z∈Z\C} |C ∩ C_{z}|.

We arrive at a contradiction, by hypothesis, because

|C(M|Z) \ L| ≥ 1 + |D| + |W | ≥ 1 + |S| + |W | = 1 + |C|.

So, L ⊆ C(M|(Z \ S)).

The result follows provided we prove that C(M|(Z \ S)) ⊆ L. Suppose that D is a circuit of M|(Z \S) such that D ∉ L. By Lemma 3.43 of [20] applied to the linear subclass C(M|(Z \ S)), there is a Tutte-line L of M|Z such that D ∪ S ⊆ L. As every circuit of M|L different of D contains S and no circuit of M|Z that contains S belongs to L, it follows that no circuit of M|L belongs to L. We arrive at a contradiction by the first paragraph and the result follows.

Proof of Theorem 1.3. We shall divide the proof of this result in two cases:

Case 1. max{r(M_{1}), r(M_{2})} ≤ k.

First, we shall prove that M_{i} does not have disjoint cocircuits, for both i ∈ {1, 2}. Let C_{1}^{∗} and C_{2}^{∗} be disjoint cocircuits of M_{i}, say i = 1. Consider the hyperplanes H_{1} = E \ C_{1}^{∗} and H_{2} = E \ C_{2}^{∗}. Observe that

ξ_{M_{1}}(C_{1}^{∗}, H_{1}) = r_{M_{1}}(C_{1}^{∗}) + r_{M_{1}}(H_{1}) − r(M_{1})
= r_{M_{1}}(C_{1}^{∗}) + [r(M_{1}) − 1] − r(M_{1})
= r_{M_{1}}(C_{1}^{∗}) − 1

We also have that C_{1}^{∗} ⊆ H_{2} and so r_{M_{1}}(C_{1}^{∗}) ≤ r_{M_{1}}(H_{2}) = r(M_{1}) − 1. Hence

min{r_{M_{1}}(C_{1}^{∗}), r_{M_{1}}(H_{1})} ≥ r_{M_{1}}(C_{1}^{∗}).

We arrive at a contradiction because r_{M_{1}}(C_{1}^{∗}) ≤ k and M_{1} is (k + 1)-connected. Thus, M_{i} does not have disjoint cocircuits, for both i ∈ {1, 2}. In particular, M_{1} and M_{2} are vertically n-connected for every positive integer n. We have (ii).

Case 2. max{r(M_{1}), r(M_{2})} ≥ k + 1.

Without loss of generality, we may suppose that r(M_{1}) ≥ k + 1. Let C_{1}^{∗} be a cocircuit of M_{1} and H_{1} = E \ C_{1}^{∗}. Similarly to the previous case, we have that ξ_{M_{1}}(C_{1}^{∗}, H_{1}) = r_{M_{1}}(C_{1}^{∗}) − 1. Moreover,

min{r_{M_{1}}(C_{1}^{∗}), r_{M_{1}}(H_{1})} = min{r_{M_{1}}(C_{1}^{∗}), r(M_{1}) − 1} ≥ min{r_{M_{1}}(C_{1}^{∗}), k}.

As M_{1} is vertically (k + 1)-connected, it follows that r_{M_{1}}(C_{1}^{∗}) ≥ k + 1. Thus, g(M_{1}^{∗}) ≥ k + 1. By Lemma 2.1(i), r(M_{1}) = r(M_{2}). We can repeat the previous argument to M_{2} and we conclude also that g(M_{2}^{∗}) ≥ k+1. By Theorem 4.1, there is a matroid N which is obtained from M_{i}, for both i ∈ {1, 2}, by relaxing a sequence of nests (each along an admissible linear subclass of M_{i} restricted to it) such that

B(M_{1}) △ B(M_{2}) = (B(N) \ B(M_{1})) ∪ (B(N) \ B(M_{2})).

Let Z be a nest of M_{i} that was relaxed along an admissible linear subclass L of M_{i}|Z to originate N. We have that

|C(M_{i}|Z) \ L| ≤ |B(N) \ B(M_{i})| ≤ |B(M_{1}) △ B(M_{2})| ≤ k < r(M_{i}) = |C|,

where C is a large circuit of M_{i} contained in Z. By Lemma 5.1, we have that L is the set of circuits of M_{i}|Z that do not meet a series class S. If e ∈ S, then Z is a tip-hyperplane of M_{i} having tip e. The result follows.

References

[1] 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.

[2] 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.

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

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

[5] M. Lemos, On Mills’s conjecture on matroids with many common bases, Discrete Math., to appear.

[6] M. Lemos, J.G. Oxley and T.J. Reid, On the 3-connected matroids that are minimal having a fixed restriction, Graphs and Combinatorics, 16, 285-318.

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

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

[9] J.G. Oxley, On a matroid generalization of graph connectivity, Math. Proc. Camb. Phil. Soc. 90 (1981), 207-214.

[10] J.G. Oxley, On matroid connectivity, Quart. J. Math. Oxford Ser. (2) 32 (1981), 193-208.

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

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

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

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

[15] J. Oxley and G. Whittle, A note on the non-spanning circuits of a matroid, Europ. J. Combin. 12 (1991), 259-261.

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

[17] K. Truemper, Alpha-balanced graphs and matroids, J. Combin. Theory Ser. B 32 (1982), 112-139.

[18] W.T. Tutte, Lectures on matroids, Journal of Research of the National Bureau of Standards Series B 69 (1965), 1-47.

[19] W.T. Tutte, Connectivity in matroids, Canad. J. Math. 18 (1966), 1301-1324.

[20] W.T. Tutte, Introduction to the Theory of Matroids, Elsevier, New York, 1971.

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

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