On Mills’s conjecture on matroids with many common bases

Manoel Lemos Departamento de Matemática Universidade Federal de Pernambuco Recife, Pernambuco, 50.740-540, Brazil

e-mail: manoel@dmat.ufpe.br

Abstract In this paper, we shall prove a conjecture of Mills: 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.

1 Introduction

In this article, for matroid theory we shall use the notation set by Oxley in [2], which we assume familiar to the reader. We shall prove, up to small modifications, the following conjecture made by Mills in [1].

Conjecture 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.

For j = 0 and i ∈ {1, 2}, the matroid obtained from M_{i} by relaxing j circuits-hyperplanes is defined to be M_{i}.

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. We shall prove that these are the only exceptions and that the hypothesis on the size of E can be removed from the conjecture.

In [1], Mills proved this conjecture for k = 2 and pointed out that it follows from Truemper’s results [3] when k = 1. In general, this conjecture follows from a theorem which shall be proved in the next section and guarantees the same conclusion with weaker hypotheses.

2 The main result

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 denote by CH(M) the collection of circuit-hyperplanes of 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 [4], 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 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 property is invariant under duality; that is, (M, N) is a k-pair if and only if (M^{∗}, N^{∗}) is a k-pair.

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

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

then r(M_{1}) = r(M_{2}).

Proof: Taking the dual, when necessary, we do not lose generality by supposing that g(M_{1}) ≥ k + 1. We shall argue by contradiction. Suppose that r(M_{1}) ≠ r(M_{2}). If C is a circuit of M_{1}, then C \ {e} can be completed to a basis B_{e} of M_{1}, for every e ∈ C. Observe that

{B_{e} : e ∈ C} ⊆ B(M_{1}) ⊆ B(M_{1}) ∪ B(M_{2}) = B(M_{1}) △ B(M_{2}),

where the last equality holds because M_{1} and M_{2} do not have any bases in common. As |C| ≥ g(M_{1}) ≥ k + 1, it follows that the cardinality of the first set is at least k + 1. We arrive at a contradiction, since (M_{1}, M_{2}) is a k-pair, by hypothesis. Thus r(M_{1}) = r(M_{2}). QED

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

I(M_{1}) ∩ C(M_{2}) ⊆ B(M_{1}).

Proof: Suppose that C ∈ I(M_{1}) ∩ C(M_{2}). We need to prove only that C ∈ B(M_{1}). To conclude this we will show that C spans M_{1}. Suppose that C does not span M_{1}. So, there is a cocircuit D of M_{1} such that C ∩ D = ∅. However, as D is a cocircuit of M_{1}/C, for each d ∈ D, there is a basis B′_{d} of M_{1}/C such that B′_{d} ∩ D = {d}. Hence B′_{d} ∪ C is a basis of M_{1} for every d ∈ D. As B′_{d} ∪ C is not a basis for M_{2}, it follows that

|B(M_{1}) △ B(M_{2})| ≥ |{B′_{d} ∪ C : d ∈ D}| = |D| ≥ g(M_{1}^{∗}) ≥ k + 1.

We arrive at a contradiction because (M_{1}, M_{2}) is a k-pair. Thus C spans M_{1} and the result follows. QED

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

I(M_{1}) ∩ C(M_{2}) = B(M_{1}) ∩ CH(M_{2}).

Proof: By Lemma 1, we have that r(M_{1}) = r(M_{2}). Suppose that C ∈ I(M_{1}) ∩ C(M_{2}). By Lemma 2, it follows that |C| = r(M_{1}) and so |C| = r(M_{2}). In the next paragraph we shall prove that C ∈ CH(M_{2}).

Suppose that C ∉ CH(M_{2}). Thus cl_{M_{2}}(C) ≠ C, since |C| = r(M_{2}). Let a be an element belonging to E(M_{2}) \ C spanned by C in M_{2}. Observe that C ∪ {a} is a Tutte-line of M_{2}. Let {P_{1}, P_{2}, …, P_{n}} be the canonical partition of C ∪ {a} in M_{2}, for some n ≥ 2. Set C_{i} = (C ∪ {a}) \ P_{i}, for i ∈ {1, 2, …, n}. There is just one circuit C_{0} of M_{1} contained in C ∪ {a} because C is a basis of M_{1}, by Lemma 2. Let

B′ = {C_{i} : i ∈ {1, 2, …, n} and C_{0} ⊈ C_{i}}.

So, B′ ⊆ I(M_{1}) ∩ C(M_{2}). Thus, by Lemma 2, B′ ⊆ B(M_{1}). So,

B′ ⊆ B(M_{1}) △ B(M_{2}).

Hence there is an integer l such that |B′| = l ≤ k, since (M_{1}, M_{2}) is a k-pair. Say, B′ = {C_{1}, …, C_{l}}. As |C_{i}| = |C| = r(M_{1}), for every i ∈ {1, …, l}, it follows that P_{i} = {a_{i}}, for some a_{i} ∈ E(M_{2}). Hence {a_{1}, …, a_{l}} ⊆ C_{0}. If j > l, then C_{0} ⊆ C_{j} and C_{0} ∩ P_{j} = ∅. Thus C_{0} = {a_{1}, …, a_{l}}. We arrive at a contradiction because

k ≥ l = |C_{0}| ≥ g(M_{1}) ≥ k + 1.

So, C ∈ CH(M_{2}). That is,

I(M_{1}) ∩ C(M_{2}) ⊆ CH(M_{2}).

From the previous paragraph and Lemma 2, we have that

I(M_{1}) ∩ C(M_{2}) ⊆ B(M_{1}) ∩ CH(M_{2}).

As every element in B(M_{1}) ∩ CH(M_{2}) belongs to I(M_{1}) ∩ C(M_{2}), then we have equality in this inclusion and the result follows. QED

Recall that a matroid is paving if it has no circuits of size less than r(M).

Lemma 4. 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 either

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

(b) M_{1} is a uniform matroid and M_{2} is a paving matroid having the same rank as M_{1}, which is equal to k or |E(M_{1})| − k. Moreover,

{C : C ∈ C(M_{2}) and |C| = r(M_{2})} = CH(M_{2}).

Proof: We shall assume that (a) does not hold and we shall prove (b). Observe that the hypotheses and the conclusions of this lemma are invariant under duality. Thus we can suppose that g(M_{2}) ≤ k. Let C be a circuit of M_{2} such that |C| = g(M_{2}). Observe that C ∈ I(M_{1}), since g(M_{1}) ≥ k + 1. Hence, by Lemma 3, C ∈ B(M_{1}) ∩ CH(M_{2}). So,

r(M_{1}) = |C| = g(M_{2}) ≤ k ≤ g(M_{1}) − 1 ≤ c(M_{1}) − 1 ≤ r(M_{1}),

where c(M_{1}) denotes the circumference of M_{1}; that is, the size of the largest circuit of M_{1}. Thus, all inequalities in the previous display are actually equalities. Since

g(M_{1}) = c(M_{1}) = r(M_{1}) + 1,

we have that M_{1} is a uniform matroid. Moreover, as k = g(M_{2}) = r(M_{1}), it follows from Lemma 1 that M_{2} is a paving matroid and r(M_{2}) = r(M_{1}) = k.

Now suppose that C ∈ C(M_{2}) and |C| = r(M_{2}). Since r(M_{2}) = g(M_{2}) = k, the set C is independent in M_{1} as g(M_{1}) ≥ k + 1. It follows from Lemma 3 that C ∈ CH(M_{2}). QED

Lemma 5. 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

B(M_{i}) \ B(M_{3−i}) = CH(M_{3−i}) \ CH(M_{i}),

for every i ∈ {1, 2}.

Proof: When M_{1} and M_{2} are as in (b) of Lemma 4, then Lemma 5 follows because

CH(M_{1}) = B(M_{2}) \ B(M_{1}) = ∅ and
CH(M_{2}) = {C : C ∈ C(M_{2}) and |C| = r(M_{2})} = B(M_{1}) \ B(M_{2}).

So we may suppose that min{g(M_{2}), g(M_{2}^{∗})} ≥ k + 1. Hence, by symmetry, it suffices to prove this result for i = 1.

Let B ∈ B(M_{1}) \ B(M_{2}). So, there is a circuit C of M_{2} such that C ⊆ B. As C ∈ I(M_{1}) ∩ C(M_{2}), it follows, by Lemma 3, that C ∈ B(M_{1}) ∩ CH(M_{2}). That is, B(M_{1}) \ B(M_{2}) ⊆ CH(M_{2}) \ CH(M_{1}).

Let C ∈ CH(M_{2}) \ CH(M_{1}). We shall prove that C ∈ I(M_{1}). Suppose that C ∉ I(M_{1}). Let C′ be a circuit of M_{1} such that C′ ⊆ C. Hence C′ = C, otherwise C′ ∈ I(M_{2}) and, by Lemma 3 applied to the k-pair (M_{2}, M_{1}), C′ ∈ B(M_{2}). Since C ∈ CH(M_{2}) \ CH(M_{1}), and Lemma 1 implies that r(M_{1}) = r(M_{2}), it follows that there is an a ∈ E(M_{1}) \ C such that C spans a in M_{1}. Let {P_{1}, P_{2}, …, P_{n}} for some n ≥ 2 be the canonical partition of the Tutte-line C ∪{a} in M_{1}. We may suppose that P_{1} = {a}. Observe that C_{i} = (C ∪{a})\P_{i} is independent in M_{2}, for every i ∈ {2, …, n}, because C does not span a in M_{2}. By Lemma 3 applied to the k-pair (M_{2}, M_{1}), it follows that C_{i} is a circuithyperplane of M_{1} and a basis of M_{2}, for i ∈ {2, …, n}. So |C_{i}| = |C| for every i ∈ {1, 2, …, n}. In particular, |P_{i}| = 1, for every i ∈ {1, 2, …, n}. Thus n = |C|+1 ≥ g(M_{2})+1 ≥ k +2. We arrive at a contradiction to the assumption that (M_{1}, M_{2}) is a k-pair because

{C_{2}, …, C_{n}} ⊆ B(M_{2}) \ B(M_{1}).

As a result of this contradiction, we conclude that C ∈ I(M_{1}). Moreover, as Lemma 1 implies that r(M_{1}) = r(M_{2}) = |C|, we have that C ∈ B(M_{1}). Thus CH(M_{2}) \ CH(M_{1}) ⊆ B(M_{1}) \ B(M_{2}), and the result follows. QED

Theorem 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.

Proof: By Lemma 5, we have that

B(M_{i}) \ B(M_{3−i}) = CH(M_{3−i}) \ CH(M_{i}),  (∗)

for every i ∈ {1, 2}. For i ∈ {1, 2}, suppose that

n_{i} = |CH(M_{i}) \ CH(M_{3−i})|.

Let N_{i} be the matroid obtained from M_{i} by relaxing the circuit-hyperplanes belonging to CH(M_{i}) \ CH(M_{3−i}). By (∗), we have that N_{1} = N_{2}; call this matroid N. Again, by (∗), we obtain

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

where the last inequality follows because (M_{1}, M_{2}) is a k-pair. Thus, the result follows. QED We say that a matroid M is square, when

|E(M)| − 2r(M) ∈ {−1, 0, 1}.

The next result follows from Corollary 8.1.8 of [2]:

Lemma 6. If M is a (k + 1)-connected matroid and |E(M)| < 2k, then M is a square uniform matroid. QED

Using the previous lemma, we can prove the next result, which removes the bound on the size of E from Conjecture 1 and excludes the few counter-examples to it.

Theorem 2. For some positive integer k, suppose that M_{1} and M_{2} are (k + 1)- connected matroids having the same ground set. 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}^{∗} is a square uniform matroid having 2r − 1 elements.

Proof: When |E(M)| ≥ 2k, then min{g(M_{1}), g(M_{1}^{∗})} ≥ k + 1 and the result follows from Theorem 1. So we may suppose that |E(M)| ≤ 2k−1. Then Lemma 6 implies that M_{1} and M_{2} are square uniform matroids. As E(M_{1}) = E(M_{2}) and M_{1} ≠ M_{2}, it follows that M_{1} = M_{2}^{∗} and |E(M_{1})| = 2r−1, for some positive integer r. Observe that

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

because r(M_{1}) ≠ r(M_{2}) and so B(M_{1}) △ B(M_{2}) = B(M_{1}) ∪ B(M_{2}). QED

Acknowledgments

The author was partially supported by CNPq, FINEP and PRONEX 107/97. The author also thanks the referees for the valuable suggestions that improved this article.

References

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

[2] J. G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.

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

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