The reconstruction of a matroid from its connectivity function^{∗}

Manoel Lemos and Sérgio Mota Departamento de Matemática Universidade Federal de Pernambuco Cidade Universitária Recife, PE, 50740-540, Brazil

e-mail: manoel@dmat.ufpe.br sma@dmat.ufpe.br

Abstract In this paper, we shall present an algorithm to decide when a connected matroid M is reconstructible from its connectivity function. When M is not reconstructible, this algorithm gives all the matroids with the same connectivity fucntion as M.

1 Introduction

The matroid theory terminology used in this paper will follow Oxley [4]. The connectivity function of a matroid M is defined as

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

where {X, Y } is a partition of E(M). This function is invariant under duality, since it may be written as

ξ_{M}(X, Y) = r_{M}(X) + r_{M^{∗}}(X) − |X| + 1.

In particular, a matroid and its dual have the same connectivity function. When M = M_{1} ⊕ M_{2}, then

ξ_{M}(X, Y) + 1 = ξ_{M_{1}}(X ∩ E(M_{1}), Y ∩ E(M_{1})) + ξ_{M_{2}}(X ∩ E(M_{2}), Y ∩ E(M_{2})).

∗The first author is partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, Brazil).

Thus, M_{1} ⊕ M_{2} and M_{1} ⊕ M_{2}^{∗} have the same connectivity function.

In this paper, we shall adress the problem of determining all matroids with the same connectivity function. By the last identity, we may restrict our attention to connected matroids. In this case, Cunningham conjectured that, up to duality, a connected matroid is reconstructed from its connectivity functon, that is:

Cunningham conjecture. If M and N are connected matroids over the same ground set having the same connectivity function, then M = N or M = N^{∗}.

In [5], Seymour proved the Cunningham conjecture for the class of binary matroids. In the same paper, Seymour gave a counter-example for it in general. In [1], Lemos proved that this conjecture is true provided that r(M) ≠ r(M^{∗}).

Note that

r_{M}(X) + r_{M^{∗}}(X) = r_{N}(X) + r_{N^{∗}}(X),

for every X ⊆ E, when M and N are matroids over the same ground set E having the same connectivity function. In general, we say that M = (M_{1}, M_{2}, M_{3}, M_{4}) is a quad when M_{1}, M_{2}, M_{3} and M_{4} are matroids over the same ground set, which is denoted by E(M), such that

r_{M_{1}}(X) + r_{M_{2}}(X) = r_{M_{3}}(X) + r_{M_{4}}(X),

for every X ⊆ E(M). Moreover, when M_{1} = M_{2}^{∗} and M_{3} = M_{4}^{∗}, M is said to be a s-quad.

We are setting a different notation from Lemos [1] to get a more compact description of the results. Whem X denotes a quad, X_{i} denotes the i-th coordenate of this quad, for i ∈ {1, 2, 3, 4}.

For a quad M and disjoint subsets X and Y of E(M), we define a minor of M as

M\X/Y = (M_{1}\X/Y, M_{2}\X/Y, M_{3}\X/Y, M_{4}\X/Y)

and the dual M^{∗} of M as (M_{1}^{∗}, M_{2}^{∗}, M_{3}^{∗}, M_{4}^{∗}). We shall use M|X to denote M\(E(M) \ X). In [1], Lemos have proved that

(1.1) (1.1, 1.2 and 1.3 of [1]) M\X/Y and M^{∗} are quads.

When M and N are quads such that E(M)∩E(N) = ∅, we denote by M⊕N the quad

(M_{1} ⊕ N_{1}, M_{2} ⊕ N_{2}, M_{3} ⊕ N_{3}, M_{4} ⊕ N_{4}).

Case N_{1} = N_{2} = N_{3} = N_{4} = N, M ⊕ N is also denoted by M ⊕ N. For a matroid N such that E(N) ∩ E(M) = {e}, M ⊕_{2} N denotes

(M_{1} ⊕_{2} N, M_{2} ⊕_{2} N, M_{3} ⊕_{2} N, M_{4} ⊕_{2} N),

which was proved to be a quad by Lemos in [1].

For a partitition {X, Y } of E(M), we define

ξ_{M}(X, Y) = ξ_{M_{1}}(X, Y) + ξ_{M_{2}}(X, Y).

When ξ_{M}(X, Y) = 2, then M = (M|X) ⊕ (M|Y). So, we can restrict our attention to quads satisfying ξ_{M}(X, Y) ≥ 3, for every partition {X, Y } of E(M) such that min{|X|, |Y |} ≥ 1. Such quads are called connected. M is said to be non-trivial, when {M_{1}, M_{2}} ≠ {M_{3}, M_{4}}. In [1], Lemos proved the following result:

(1.2) Suppose that M is a non-trivial connected quad. Then,

(i) (2.6 of [1]) ξ_{M}(X, Y) ≥ 4, for every partititon {X, Y } of M such that min{|X|, |Y |} ≥ 1.

(ii) (2.7 of [1]) When ξ_{M_{1}}(X, Y) = ξ_{M_{2}}(X, Y) = ξ_{M_{3}}(X, Y) = ξ_{M_{4}}(X, Y) = 2, for a partition {X, Y } of E(M) such that min{|X|, |Y |} ≥ 2, then there is a matroid N such that E(N) = X ∪ {e} or E(N) = Y ∪ {e}, for an element e ∉ E(M), and a quad N such that E(N) = (E(M)\E(N))∪{e} satisfying M = N ⊕_{2} N.

In [1], Lemos proved the next result which characterizes a quad:

(1.3) (1.4 and 1.5 of [1]) Suppose that M_{i} is a matroid having E as its ground set, for every i ∈ {1, 2, 3, 4}. (M_{1}, M_{2}, M_{3}, M_{4}) is a quad if and only if

C(M_{1}) ∪ C(M_{2}) = C(M_{3}) ∪ C(M_{4}) and C(M_{1}) ∩ C(M_{2}) = C(M_{3}) ∩ C(M_{4}).

This result is essential in Seymour’s proof that a connected binary matroid is reconstructible from its connectivity function, up to duality, in the class of binary matroids. We shall state Seymour’s original result, whose proof can be adapted to prove (1.3):

Theorem 1. Suppose that M and N are matroids such that E(M) = E(N). M and N have the same connectivity function if and only if

C(M) ∪ C^{∗}(M) = C(N) ∪ C^{∗}(N) and C(M) ∩ C^{∗}(M) = C(N) ∩ C^{∗}(N).

So, from Seymour’s result, a matroid M is reconstructible from its connectivity function, when there is no subset A of C(M) △ C^{∗}(M) such that

(F1) A ≠ ∅ and A ≠ C(M) △ C^{∗}(M);

(F2) C = C(M) △ A and C^{∗} = C^{∗}(M) △ A are, respectively, the family of circuits and the family of cocircuits of a matroid.

A subset A of C(M) △ C^{∗}(M) is called feasible for M when it satisfies (F1) and (F2). Thus, we need to answer the following question: when does M have a feasible set?

Clearly, a feasible set A for M must satisfies:

(A1) |{X, Y } ∩ A| ≠ 1, for every X, Y ∈ C(M) △ C^{∗}(M) such that X ⊂ Y.

(A2) |{X, Y }∩A| ≠ 1, for every X, Y ∈ C(M)△C^{∗}(M) such that |X ∩Y | = 1.

A subset A of C(M) △ C^{∗}(M) is called admissible for M when it satisfies (F1), (A1) and (A2). The next result determines which admissible sets are feasible.

Theorem 2. Suppose that A is an admissible set for a connected matroid M such that r(M) = r(M^{∗}). A is feasible if and only if |{X, Y } ∩ A| ∈ {0, 2}, for every

X, Y ∈ (C(M) ∩ I(M^{∗})) ∪ (C(M^{∗}) ∩ I(M))

such that X ∩ Y = ∅.

Observe that one can easily determine all the feasible sets for M using theorem 2, provided that the circuits and cocircuits of M are know.

2 Almost preserving the rank function

In this section, we shall improve the next result of Lemos [1]:

(2.1) (theorem 2 of [1]) If M is a non-trival connected quad, then

r(M_{1}) = r(M_{2}) = r(M_{3}) = r(M_{4}).

By (2.1), the condition of the rank of M in theorem 2 is not restricitive, since, for a connected matroid M, feasible sets exist only when r(M) = r(M^{∗}).

(2.2) Suppose that M is a non-trivial connected quad. If {M_{1}|A, M_{2}|A} ≠ {M_{3}|A, M_{4}|A}, then

r_{M_{1}}(A) = r_{M_{2}}(A) = r_{M_{3}}(A) = r_{M_{4}}(A)

and there is a subset B of A such that

(i) M|A = M|B ⊕ M|(A \ B);

(ii) M|B is non-trivial and connected;

(iii) M_{1}|(A \ B) = M_{2}|(A \ B) = M_{3}|(A \ B) = M_{4}|(A \ B).

Proof: We shall prove this result by induction on |E(M)|. The result is vacuously true for |E(M)| = 1. When E(M) = A, the first part of the result follows from (2.1) and for the second, we can take B = A. So, we may suppose that E(M) \ A ≠ ∅. Let e be an element of E(M) \ A.

When M\e is connected, then the result follows by induction, since

{M_{1}\e, M_{2}\e} ≠ {M_{3}\e, M_{4}\e}

because {M_{1}|A, M_{2}|A} ≠ {M_{3}|A, M_{4}|A}.

When M\e is not connected, then, by (1.2), there is a matroid N and a quad N such that E(N) = X ∪ {f}, for some X ⊂ E(M), E(N) = (E(M) \ X) ∪ {f} and M = N ⊕_{2} N, where f ∉ E(M) and {e, f} is contained in a series class of N. As M is connected, it follows that N is a connected quad. Observe that N is a non-trivial quad, since

M_{i}|A = M_{i}|(A ∩ X) ⊕ M_{i}|(A \ X) = N|(A ∩ X) ⊕ N_{i}|(A \ X).

By induction, the first part of the result holds for N and hence

r_{N_{1}}(A \ X) = r_{N_{2}}(A \ X) = r_{N_{3}}(A \ X) = r_{N_{4}}(A \ X).

As r_{M_{i}}(A) = r_{N}(A ∩ X) + r_{N_{i}}(A \ X), the first part of the result follows for M. By induction, the second part of the result also holds for N, and there is a subset B of A \ X such that

(i) N|(A \ X) = N|B ⊕ N|(A \ (X ∪ B));

(ii) N|B is non-trivial and connected;

(iii) N_{1}|(A\(X ∪B)) = N_{2}|(A\(X ∪B)) = N_{3}|(A\(X ∪B)) = N_{4}|(A\(X ∪B)).

The second part of the result also follows for M because N|B = M|B, N|(A\ (B ∪X)) = M|(A\(B ∪X)) and N|(A\(B ∪X))⊕M|(A∩X) = M|(A\B).

(2.3) If M is a non-trivial connected quad, then

{r_{M_{1}}(A), r_{M_{2}}(A)} = {r_{M_{3}}(A), r_{M_{4}}(A)},

for every A ⊆ E(M).

Proof: The result follows when {M_{1}|A, M_{2}|A} = {M_{3}|A, M_{4}|A}. So, we may suppose that this is not the case. By (2.2), it follows that r_{M_{1}}(A) = r_{M_{2}}(A) = r_{M_{3}}(A) = r_{M_{4}}(A).

Observe that the previous result says that the rank function is locally preserved in a non-trivial connected quad M, that is,

{r_{M_{1}}(A), r_{M_{2}}(A)} = {r_{M_{3}}(A), r_{M_{4}}(A)}, for every A ⊆ E(M).

Cunningham conjecture may be extended to this context as: for a non-trivial connected quad M, is it true that

{r_{M_{1}}, r_{M_{2}}} = {r_{M_{3}}, r_{M_{4}}}?

So, (2.3) is the closest positive answer that we can get in general for Cunningham conjecture.

In view of (2.3), when M is a non-trivial connected quad, then the rank functions of M_{3} and M_{4} are obtained mixing the rank functions of M_{1} and M_{2}, that is, there is a family R of subsets of E(M) such that

(r_{M_{3}}(X), r_{M_{4}}(X)) = \{ \begin{matrix}(r_{M_{1}}(X), r_{M_{2}}(X)) & when X ∈ R \\ (r_{M_{2}}(X), r_{M_{1}}(X)) & when X ∉ R \end{matrix}

In the next section, we shall define an operation of mix between the rank functions of two matroids, that is, we prove that for some R this identity gives rise to a pair of rank functions of matroids. This operation of mix will be enough to characterize the quads, as we shall prove in section four.

3 The mix of two matroids

Suppose that M_{1} and M_{2} are matroids on the same ground set E such that

ξ_{M_{1}}(X, Y) + ξ_{M_{2}}(X, Y) ≥ 3,

for every partition {X, Y } of E satisfying min{|X|, |Y |} ≥ 1.

We define

X = {X ⊆ E : r_{M_{1}}(X) ≠ r_{M_{2}}(X)}.

Let G_{M_{1},M_{2}} be a simple graph whose vertex set is X and, for X, Y ∈ X, XY is an edge of this graph if and only if

(i) X ⊂ Y; or

(ii) X ∩ Y ∉ X , X ∪ Y ∉ X and |X △ Y | = 2.

Let {A, B} be a partition of X such that AB ∉ E(G_{M_{1},M_{2}}) for every A ∈ A and B ∈ B. We define two functions:

r_{3}(X) = \{ \begin{matrix}r_{M_{1}}(X) & when X ∉ A \\ r_{M_{2}}(X) & when X ∈ A \end{matrix} and r_{4}(X) = \{ \begin{matrix}r_{M_{2}}(X) & when X ∉ A \\ r_{M_{1}}(X) & when X ∈ A \end{matrix}

Observe that these functions are also given by

r_{3}(X) = \{ \begin{matrix}r_{M_{1}}(X) & when X ∈ B \\ r_{M_{2}}(X) & when X ∉ B \end{matrix} and r_{4}(X) = \{ \begin{matrix}r_{M_{2}}(X) & when X ∈ B \\ r_{M_{1}}(X) & when X ∉ B \end{matrix}

Note that the definition of mix is algorithmic, but it depends on the rank functions of the matroids involved. In section five, we shall look to the mix in terms of circuits and hyperplanes, getting a more efficient algorithm for its computation.

(3.1) r_{3} and r_{4} are rank functions of matroids, which are denoted by M_{3} and M_{4}, respectively.

Proof: By symmetry, it is enough to prove that r_{3} is the rank function of a matroid. To demonstrate this, we need to verify the following (1.4.14 of [4]):

(1) r_{3}(∅) = 0;

(2) r_{3}(X) ≤ r_{3}(Y), when X ⊆ Y;

(3) r_{3}(X ∪ {e}) ≤ r_{3}(X) + 1;

(4) r_{3}(X ∪ {e, f}) = r_{3}(X), when r_{3}(X ∪ {e}) = r_{3}(X ∪ {f}) = r_{3}(X).

First, observe that the next affirmation follows from the definition of r_{3}:

(3.2) When X ∈ X and r_{3}(X) = r_{M_{i}}(X), for i ∈ {1, 2}, then r_{3}(Y) = r_{M_{i}}(Y) for every Y such that X ⊆ Y or Y ⊆ X.

Observe that (1) is trivial. Now, we shall prove (2). Suppose that (2) is not true, that is, there are sets X and Y such that X ⊆ Y and r_{3}(X) > r_{3}(Y). By definition, r_{3}(X) = r_{M_{i}}(X), for some i ∈ {1, 2}. Thus, r_{3}(Y) = r_{M_{3−i}}(Y). Hence

r_{M_{3−i}}(X) ≤ r_{M_{3−i}}(Y) = r_{3}(Y) < r_{3}(X) = r_{M_{i}}(X) ≤ r_{M_{i}}(Y).

So, X and Y belong to X and we arrive at a contradiction by (3.2).

Now, we shall stablish (3). When (3) fails, by (2), there is a set X and an element e such that r_{3}(X ∪ {e}) > r_{3}(X) + 1. By definition, r_{3}(X) = r_{M_{i}}(X), for some i ∈ {1, 2}. Thus, r_{3}(X ∪ {e}) = r_{M_{3−i}}(X ∪ {e}), r_{3}(X) ≠ r_{M_{3−i}}(X) and r_{3}(X ∪ {e}) ≠ r_{M_{i}}(X ∪ {e}), otherwise r_{3}(X ∪ {e}) − r_{3}(X) ∈ {0, 1}. Thus, X, X ∪ {e} ∈ X. We arrive at a contradiction, by (3.2).

In this paragraph, we shall prove (4). Suppose that (4) is not true, that is, there is a set X and elements e and f such that r_{3}(X ∪ {e, f}) ≠ r_{3}(X) and r_{3}(X ∪ {e}) = r_{3}(X ∪ {f}) = r_{3}(X). By (3.2), X ∉ X and X ∪ {e, f} ∉ X. So,

r_{3}(X) = r_{M_{1}}(X) = r_{M_{2}}(X) and
r_{3}(X ∪ {e, f}) = r_{M_{1}}(X ∪ {e, f}) = r_{M_{2}}(X ∪ {e, f}).

Thus, |cl_{M_{i}}(X) ∩ {e, f}| = 1, for i ∈ {1, 2}, and r_{3}(X ∪ {e, f}) = r_{3}(X) + 1. Without loss of generality, we may suppose that

r_{3}(X) = r_{3}(X ∪ {e}) = r_{M_{1}}(X ∪ {e}) = r_{M_{2}}(X ∪ {e}) − 1 and

r_{3}(X) = r_{3}(X ∪ {f}) = r_{M_{2}}(X ∪ {f}) = r_{M_{1}}(X ∪ {f}) − 1.

We arrive at a contradiction, since X ∪ {e} and X ∪ {f} belong to X and X and X ∪ {e, f} does not belong to X. By definition, (X ∪ {e})(X ∪ {f}) is an edge of G_{M_{1},M_{2}}.

We say that {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}} — a pair of matroids {M_{1}, M_{2}} can have more than one mix. Observe that {M_{3}, M_{4}} = {M_{1}, M_{2}}, when A = ∅ or B = ∅. This is always the case when E ∈ X, since EX is an edge of G_{M_{1},M_{2}}, for every X ∈ X \ {E}. By our construction, we have that

(3.3) If {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}}, then (M_{1}, M_{2}, M_{3}, M_{4}) is a connected quad.

In the next section, we shall prove that all the quads can be obtained as in the previous proposition.

(3.4) Suppose that {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}}, M_{1} = M_{2}^{∗} and r(M_{1}) = r(M_{2}). Then, X ∈ X if and only if E \ X ∈ X.

Proof: As M_{1} and M_{2} have the same connectivity function, it follows that

r_{M_{1}}(X) + r_{M_{1}}(E \ X) − r(M_{1}) = r_{M_{2}}(X) + r_{M_{2}}(E \ X) − r(M_{2}).

Thus,

r_{M_{1}}(X) − r_{M_{2}}(X) = r_{M_{2}}(E \ X) − r_{M_{1}}(E \ X)

and the result follows.

(3.5) Suppose that {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}}, M_{1} = M_{2}^{∗} and r(M_{1}) = r(M_{2}). Then, M_{3} = M_{4}^{∗} if and only if |{A, E \A}∩A| ∈ {0, 2}, for every A ⊆ E.

Proof: This result follows from the equivalence between the next affirmations:

(i) M_{3} = M_{4}^{∗};

(ii) r_{M_{4}}(X) = |X| + r_{M_{3}}(E \ X) − r(M_{3}), for every X ⊆ E;

(iii) for every X ⊆ E, there is an i ∈ {1, 2} such that r_{M_{3}}(X) = r_{M_{i}}(X) and r_{M_{3}}(E \ X) = r_{M_{i}}(E \ X);

(iv) |{X, E \ X} ∩ A| ∈ {0, 2}, for every X ⊆ E.

The equivalences between (i) and (ii) is immediate and between (iii) and (iv) follows from (3.4).

In this paragraph, we shall prove that (ii) and (iii) are equivalent. For X ⊆ E, we have that

|X| + r_{M_{3}}(E \ X) − r(M_{3}) = |X| + r_{M_{i}}(E \ X) − r(M_{i}) = r_{M_{3−i}}(X),

for some i ∈ {1, 2}, where the last identity occurs because M_{1} = M_{2}^{∗}. Thus, by (3.4), r_{M_{3}}(X) = r_{M_{i}}(X) if and only if r_{M_{4}}(X) = r_{M_{3−i}}(X). Hence, we have the equivalence between (ii) and (iii).

We say that {M_{3}, M_{4}} is a s-mix of {M_{1}, M_{2}}, when M_{1} = M_{2}^{∗}, r(M_{1}) = r(M_{2}), A ≠ ∅, A ≠ X and A ∈ A if and only if E \ A ∈ A, for every A ⊆ X. So, by (3.5),

(3.6) If {M_{3}, M_{4}} is a s-mix of {M_{1}, M_{2}}, then (M_{1}, M_{2}, M_{3}, M_{4}) is a connected non-trivial s-quad.

4 A characterization of connected quads

In this section, we shall present a characterization of the non-trivial connected quads, using the construction of the mix which was defined in the previous section.

(4.1) Suppose that M_{i} is a matroid having E as its ground set, for every i ∈ {1, 2, 3, 4}. (M_{1}, M_{2}, M_{3}, M_{4}) is a connected quad if and only if {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}}.

Proof: By (3.3), the “if” part of this result follows. So, we need to prove only the “only if ” part. Suppose that (M_{1}, M_{2}, M_{3}, M_{4}) is a connected quad. Observe that this quad must be non-trivial, otherwise {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}}.

To conclude that {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}}, we just need to prove that:

(4.2) If X, Y ∈ X , XY ∈ E(G_{M_{1},M_{2}}) and r_{M_{1}}(X) = r_{M_{j}}(X), for j ∈ {3, 4}, then r_{M_{1}}(Y) = r_{M_{j}}(Y).

By (2.2), (4.2) is true when X ⊆ Y or Y ⊆ X. So, we may suppose that X \ Y = {e}, Y \ X = {f}, X ∩ Y ∉ X and X ∪ Y ∉ X. When (4.2) does not hold, we must have that r_{M_{1}}(Y) = r_{M_{7−j}}(Y). As X ∩ Y and X ∪ Y do not belong to X, it follows that

r_{M_{1}}(X ∩ Y) = r_{M_{2}}(X ∩ Y) = r and r_{M_{1}}(X ∪ Y) = r_{M_{2}}(X ∪ Y) = s,

for some integers r and s. Thus,

{r_{M_{1}}(X), r_{M_{2}}(X)} = {r_{M_{1}}(Y), r_{M_{2}}(Y)} = {r, r + 1},

since |X \ Y | = |Y \ X| = 1 and X, Y ∈ X. So, s = r + 1. Without loss of generality, we may suppose that

r_{M_{1}}(X) = r_{M_{2}}(Y) = r and r_{M_{1}}(Y) = r_{M_{2}}(X) = r + 1,

otherwise, there is an i ∈ {1, 2} such that

r_{M_{i}}(X ∩ Y) = r_{M_{i}}(X) = r_{M_{i}}(Y) = r_{M_{i}}(X ∪ Y) − 1,

which is contrary to the fact that M_{i} is a matroid.

So, there is an i ∈ {3, 4} such that

r_{M_{i}}(X ∩ Y) = r_{M_{i}}(X) = r_{M_{i}}(Y) = r_{M_{i}}(X ∪ Y) − 1,

since r_{M_{1}}(X) = r_{M_{j}}(X) and r_{M_{1}}(Y) = r_{M_{7−j}}(Y). Again, we arrive at a contradiction.

As a consequence of (2.1), (3.5), (3.6) and (4.1), we have that:

(4.3) Suppose that M_{i} is a matroid having E as its ground set, for every i ∈ {1, 2, 3, 4}. (M_{1}, M_{2}, M_{3}, M_{4}) is a connected non-trivial s-quad if and only if {M_{3}, M_{4}} is a s-mix of {M_{1}, M_{2}}.

By the previous result, a connected matroid M is reconstructible from its connectivity function if and only if {M, M^{∗}} does not have a s-mix.

The explicit construction of all quads looks unlikely, since there are a lot of constructions which produce them, even in the case of s-quads (1-sum of squads, 2-sum of a s-quad with a identity self-dual matroid, the truncated lift of a s-quad — replace every entry of the quad by its truncated lift). Moreover, the construction made by Seymour [5] can be extended for a large class of paving matroids, giving non-trivial examples of s-quads, where we can apply all these operations to get more exotic examples.

5 Another way to compute the mix

In this section, we shall discuss the operation of mix as a permutation of circuits or hyperplanes of the two matroids involved in this operation.

Suppose that M_{1} and M_{2} are matroids on the same ground set E such that r(M_{1}) = r(M_{2}) and

ξ_{M_{1}}(X, Y) + ξ_{M_{2}}(X, Y) ≥ 1

for every partition {X, Y } of E such that min{|X|, |Y |} ≥ 1.

(5.1) If X is a maximal subset of E such that r_{M_{1}}(X) ≠ r_{M_{2}}(X), then X is spanning in M_{i} and a hyperplane of M_{3−i}, for some i ∈ {1, 2}.

Proof: Without loss of generality, we may suppose that r_{M_{1}}(X) > r_{M_{2}}(X). As r(M_{1}) = r(M_{2}), it follows that X ≠ E. By the maximality of X, it follows that r_{M_{1}}(X ∪ {e}) = r_{M_{2}}(X ∪ {e}), for every e ∈ E(M) \ X. Thus, r_{M_{1}}(X) = r_{M_{2}}(X)+1, X spans e in M_{1} and X does not span e in M_{2}. So, X is a spanning set of M_{1} and a hyperplane of M_{2}.

We may write the dual of this result as:

(5.2) If X is a minimal subset of E such that r_{M_{1}}(X) ≠ r_{M_{2}}(X), then X is independent in M_{i} and a circuit of M_{3−i}, for some i ∈ {1, 2}.

We shall consider the following subsets of X:

H = (H(M_{1}) ∩ S(M_{2})) ∪ (H(M_{2}) ∩ S(M_{1}))
C = (C(M_{1}) ∩ I(M_{2})) ∪ (C(M_{2}) ∩ I(M_{1}))

A sequence v_{0}, v_{1}, v_{2}, …, v_{n} of vertices of a graph G is said to be a path of G, when v_{i}v_{i+1} ∈ E(G) for every i ∈ {0, 1, 2, …, n − 1}. When v_{0}, v_{1}, v_{2}, …, v_{n} and w_{0}, w_{1}, w_{2}, …, w_{m} are paths of G such that v_{n} = w_{0}, we say that

v_{0}, v_{1}, v_{2}, …, v_{n}, w_{1}, w_{2}, …, w_{m}

is the concatenation of these paths.

(5.3) If X, Y ∈ C ∪ H belong to the same connected component of G_{M_{1},M_{2}}, then there is a path joining X to Y in G_{M_{1},M_{2}} which is the concatenation of paths of the following types:

(i) C, H, for C ∈ C and H ∈ H;

(ii) H, C, for C ∈ C and H ∈ H;

(iii) H, A, B, H′, for H, H′ ∈ H and A, B ∈ X satisfying A ⊆ H, B ⊆ H′, AB ∈ E(G_{M_{1},M_{2}}) and |A \ B| = |B \ A| = 1.

Proof: Suppose that

X = X_{0}, X_{1}, X_{2}, X_{3}, …, X_{n−1}, X_{n} = Y

is a path that joins X to Y in G_{M_{1},M_{2}}. We shall insert vertices in this path in the following way:

(i) When X_{i} ⊂ X_{i+1} or X_{i+1} ⊂ X_{i}, then, by (5.1), there is an H_{i} ∈ H such that X_{j} ⊆ H_{i}, for j ∈ {i, i + 1}. Insert H_{i} between X_{i} and X_{i+1}.

(ii) When H_{i} and H_{i+1} do not exist, then, by (5.1), there is a K_{i+1} ∈ H such that X_{i+1} ⊆ K_{i+1}. Insert K_{i+1}, X_{i+1}, in this order, between X_{i+1} and X_{i+2}.

(iii) When H_{0} does not exist, then, by (5.1), there is a K_{0} ∈ H such that X_{0} ⊆ K_{0}. Insert X_{0}, K_{0}, in this order, in the begining of the path.

(iv) When H_{n−1} does not exist, then, by (5.1), there is a K_{n} ∈ H such that X_{n} ⊆ K_{n}. Insert K_{n}, X_{n}, in this order, in the end of the path.

When H_{i−1} and H_{i} exist, then, by (5.2), there is a C_{i} ∈ C such that C_{i} ⊆ X_{i}. Replace X_{i} by C_{i}. Oberve that the path at the end of these constructions has the desired properties — when H_{0} exists and X_{0} is a hyperplane, then X_{0} = H_{0} and we ignore X_{0}; we may need to ignore X_{n} also.

Now, we shall define two new sets:

H′ = H(M_{1}) △ H(M_{2}) and C′ = C(M_{1}) △ C(M_{2}).

Observe that C ⊆ C′ and that H ⊆ H′. By (5.1) and (5.2), when C′ ∈ C′ \ C and H′ ∈ H′ \ H, then there is a C ∈ C such that C ⊂ C′ and a H ∈ H such that H′ ⊂ H.

Let H_{M_{1},M_{2}} be a graph whose vertex set is equal to C′ ∪ H′ and XY is an edge of this graph when

(i) X, Y ∈ C′ and X ⊂ Y;

(ii) X, Y ∈ H′ and X ⊂ Y;

(iii) X ∈ C, Y ∈ H and X ⊆ Y;

(iv) X, Y ∈ H, M_{1}|(X ∩Y) = M_{2}|(X ∩Y) and there is e ∈ X \Y and f ∈ Y \X such that {e, f} ⊆ cl_{M_{1}}(X ∩ Y) △ cl_{M_{2}}(X ∩ Y).

(5.4) If X ∈ V (H_{M_{1},M_{2}}) \ V (G_{M_{1},M_{2}}), then d_{H_{M_{1},M_{2}}} (X) = 1.

Proof: As X ∉ X, it follows that X ∈ (C′ \C)∪(H′ \H) and r_{M_{1}}(X) = r_{M_{2}}(X). When X ∈ C(M_{i}), for some i ∈ {1, 2}, then X contains just one circuit of C(M_{3−i}), since X has the same rank in both M_{1} and M_{2}. Hence d_{H_{M_{1},M_{2}}} (X) = 1. A similar argument holds when X ∈ H(M_{i}), for some i ∈ {1, 2}.

(5.5) Suppose that X and Y belong to V (H_{M_{1},M_{2}}) ∩ V (G_{M_{1},M_{2}}). X and Y belong to the same connected component of H_{M_{1},M_{2}} if and only if X and Y belong to the same connected component of G_{M_{1},M_{2}}.

Proof: First, we shall prove the “only if” part of this result. Suppose that

X = X_{0}, X_{1}, X_{2}, X_{3}, …, X_{n−1}, X_{n} = Y

is a simple path which joins X and Y in H_{M_{1},M_{2}}. By (5.4), it follows that X_{i} ∈ V (G_{H_{1},H_{2}}) for every i. If X_{i}X_{i+1} is not an edge of G_{H_{1},H_{2}}, then X_{i}, X_{i+1} ∈ H, M_{1}|(X_{i} ∩ X_{i+1}) = M_{2}|(X_{i} ∩ X_{i+1}) and there are e ∈ X_{i} \ X_{i+1} and f ∈ X_{i+1} \ X_{i} such that {e, f} ⊆ cl_{M_{1}}(X_{i} ∩ X_{i+1}) △ cl_{M_{2}}(X_{i} ∩ X_{i+1}). So, ((X_{i} ∩ X_{i+1}) ∪ {e})((X_{i} ∩ X_{i+1}) ∪ {f}) is an edge of G_{M_{1},M_{2}}. When this happens, we insert between X_{i} and X_{i+1} the vertices (X_{i} ∩ X_{i+1}) ∪ {e}, (X_{i} ∩ X_{i+1}) ∪ {f} in this order. Repeat this operation for every i in this situation. The final path is a paht in G_{M_{1},M_{2}} which joins X to Y.

Now, we shall prove the “if” part of this result. Suppose that

X = X_{0}, X_{1}, X_{2}, X_{3}, …, X_{n−1}, X_{n} = Y

is a simple path which joins X and Y in G_{M_{1},M_{2}}. By (5.4), we may choose this path such that it is a concanation of paths of the following types: (i) C, H, for C ∈ C and H ∈ H; (ii) H, C, for C ∈ C and H ∈ H; (iii) H, A, B, H′, for H, H′ ∈ H and A, B ∈ X satisfying |A \ B| = |B \ A| = 1. Observe that (i) and (ii) are paths of H_{M_{1},M_{2}}. So, we shall replace every path of type (iii) by H, H′, when M_{1}|(H ∩ H′) = M_{3}|(H ∩ H′), or by H, X, H′, for some X ∈ C such that X ⊆ H ∩ H′. At the end, we get a path from H_{M_{1},M_{2}} which joins X to Y.

As a consequence of (5.5), we have the following:

(5.6) {M_{3}, M_{4}} is a mix of {M_{1}, M_{2}} if and only if there is a partition {A, B} of V (H_{M_{1},M_{2}}) such that AB ∉ E(H_{M_{1},M_{2}}), for every A ∈ A and B ∈ B, and

C(M_{3}) = (C(M_{1})\A)∪(C(M_{2})∩B) and C(M_{4}) = (C(M_{1})∩A)∪(C(M_{2})\B).

A similar result holds for hyperplanes. Now we shall prove theorem 2.

Proof of theorem 2: By (5.5) and (4.3), a s-mix is determineted by a partition {A, B} of the vertex set of H_{M,M^{∗}} such that A ≠ ∅, B ≠ ∅ and AB ∉ E(H_{M,M^{∗}}^{s}), for every A ∈ A and B ∈ B, where H_{M,M^{∗}}^{s} is the graph obtained from H_{M,M^{∗}} by adding the edges XY, for every X ∈ V (H_{M,M^{∗}}) and Y = E(M) \ X.

Now, we shall consider the following graph:

G_{1} = H_{M,M^{∗}}^{s}/(E(H_{M,M^{∗}}^{s}) \ E(H_{M,M^{∗}})).

Observe that we can label naturaly the vertices of G_{1} using the elements of C′, since every edge that was contracted joins a vertex belonging to C′ to its complement which belongs to H′. Moreover, there is a natural bijection between the connected components of G_{1} and H_{M,M^{∗}}^{s}.

As A ∩ V (G_{1}) is a feaseble set, it follows that it must be admissible and (A2) must hold. So, the graph G_{2} obtained from G_{1} by adding all the edges XY such that X, Y ∈ C′ and |X ∩ Y | = 1 has the same number of connected components as G_{1}.

Now, we shall prove that the graph G_{3} obtained from G_{2} by deleting all the edges XY of H_{M,M^{∗}} such that X, Y ∈ H, M|(X ∩ Y) = M^{∗}|(X ∩ Y) and there is e ∈ X \ Y and f ∈ Y \ X such that {e, f} ⊆ cl_{M}(X ∩ Y) △ cl_{M^{∗}}(X ∩ Y) has the same number of connected components of G_{2}.

Without loss of generality, we may suppose that X is a hyperplane of M. Observe that f ∈ cl_{M^{∗}}(X ∩ Y), otherwise there is a circuit C_{1} of M such that f ∈ C_{1} ⊆ (X ∩ Y) ∪ {f} and C_{1} ∩ (E(M) \ X) = {f}. So, there is a cocircuit D of M such that f ∈ D ⊆ (X ∩ Y) ∪ {f}. Hence, by hypothesis, there is a circuit C of M such that e ∈ C ⊆ (X ∩ Y) ∪ {e}. Thus, by orthogonality, Y is a hyperplane of M^{∗}.

We shall prove that C, D ∈ C. Suppose that C ∉ C or D ∉ C, say C ∉ C. As M|(X ∩ Y) = M^{∗}|(X ∩ Y), it follows that C is a cocircuit of M or C contains a cocircuit D_{1} of M such that e ∈ D_{1}. In both cases, we arrive at a contradiction, by orthogonality, since (E(M) \ Y) ∩ C = {e}.

By orthogonality, we have that C′ = E(M) \ Y and D′ = E(M) \ X both belong to C′. Let C′′ and D′′ be elements of C such that C′′ ⊆ C′ and D′′ ⊆ D′. Observe that C′′C′, when C′′ ⊂ C′, D′′D′, when D′′ ⊂ D′, C′′D, D′′C, C′C and D′D are edges of G_{2}. As XY is the edge C′D′ of G_{2}, we do not increase the number of connected components of G_{2} when we delete it.

Now, we shall describe the edges of G_{3}: (i) XY such that X ∈ C, Y ∈ C′ and X ⊂ Y; (ii) XY such that X, Y ∈ C and X ∩ Y = ∅; and (iii) XY such that X, Y ∈ C′ and |X ∩ Y | = 1. So, theorem 2 follows.

6 References

[1] M.Lemos, Matroids having the same connectivity function, Discrete Mathematics 131 (1994) 153-161.

[2] M.Lemos, On the connectivity function of a binary matroid, submited.

[3] M.Lemos, Uniqueness of the decomposition of the rank fuction of a 2polimatroid, submited.

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

[5] P.D.Seymour, On the connectivity funcion of a matroid, Journal of Combinatorial Theory Series B 45 (1988) 25-30.