Uniqueness of the decompositon of the rank function of a 2-polimatroid^{∗}

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

e-mail: manoel@dmat.ufpe.br

Abstract In [5], Murty and Simon asked the following question: when the rank function of a polimatroid can be decomposed as the sum of rank funcitons of matroids? Another natural question to ask is the following: when this decomposition is unique? In this paper, we shall adress the second question.

1 Introduction

We shall denote the multiset {X_{1}, X_{2}, …, X_{m}} of matroids X_{1}, X_{2}, …, X_{m} by {X}_{m}. We say that a multiset of matroids {M}_{m} is admissible, when M_{1}, M_{2}, …, M_{m} are matroids defined over the same ground set, which is denoted by E({M}_{m}), and

r_{M_{1}}({e}) + r_{M_{2}}({e}) + ⋯ + r_{M_{m}}({e}) ≤ 2,

for every e ∈ E({M}_{m}). That is, the sum of the rank function of all the matroids belonging to {M}_{m} is equal to the rank function of a 2-polimatroid P. We say that {M}_{m} defines P or that {M}_{m} is a decomposition of P. When this decompositon exists, P is said to be matroidal. We say that ({M}_{m}, {N}_{n}) is a pair, when {M}_{m} and {N}_{n} are admissible multisets of matroids, E({M}_{m}) = E({N}_{n}) and

r_{M_{1}}(X) + r_{M_{2}}(X) + ⋯ + r_{M_{m}}(X) = r_{N_{1}}(X) + r_{N_{2}}(X) + ⋯ + r_{N_{n}}(X), for every X ⊆ E({M}_{m}). That is, {M}_{m} and {N}_{n} defines the same 2polimatroid.

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

A pair ({M}_{m}, {N}_{n}) is said to be connected, when, for every partition {X, Y } of E({M}_{m}) such that min{|X|, |Y |} ≥ 1,

r_{M_{i}}(X) + r_{M_{i}}(Y) − r(M_{i}) ≥ 1,

for some i ∈ {1, 2, …, k}. That is, the matroids belonging to {M}_{m} do not have a common 1-separation. Thus, {M}_{m} defines a connected 2-polimatroid.

When M is a matroid and N a connected component of M, we denote by \overline{N} the matroid such that E(\overline{N}) = E(M), \overline{N}|E(N) = N and r(\overline{N}|E(M) \ E(N)) = 0. We define

A(M) = \{\overline{N} : N is a connected component of M and r(N) ≠ 0\}.

Observe that

r_{M}(X) = ∑_{H∈A(M)} r_{H}(X),

for every X ⊆ E. For a multiset {M}_{m}, consider the following multiset:

A({M}_{m}) = ⋃_{i=1}^{m} A(M_{i}).

Observe that ({M}_{m}, A({M}_{m})) is a pair. Two admissible multisets of matroids {M}_{m} and {N}_{n} are said to be equivalent, when

A({M}_{m}) = A({N}_{n}).

We say that a pair ({M}_{m}, {N}_{n}) is trivial, when {M}_{m} is equivalent to {N}_{n}. When ({M}_{m}, {N}_{n}) is a trivial pair, we can get {N}_{n} from {M}_{m} by moving around connected components and ignoring some loops. Thus, we shall not consider {M}_{m} and {N}_{n} different decompositons for the 2-polimatroid defined by {M}_{m}.

The size of an admissible multiset of matroids {M}_{m} is defined as

size({M}_{m}) = |A({M}_{m})|.

We define the size of a 2-polimatroid P as

size(P) = max{size({M}_{m}) : {M}_{m} decomposes P }.

In this paragraph, we shall discuss an ideia originated on Seymour’s paper [8]. For a matroid M, we define

C_{≥2}(M) = {C ∈ C(M) : |C| ≥ 2},

that is, C_{≥2}(M) is the set of circuits of M which are not loops. For an admissible multiset of matroids {M}_{m}, we define the following multiset:

C_{≥2}({M}_{m}) = ⋃_{i=1}^{m} C_{≥2}(M_{i}).

We say that a pair ({M}_{m}, {N}_{n}) is preserving when

C_{≥2}({M}_{m}) = C_{≥2}({N}_{n}).

In section three, we shall study the non-preserving connected pairs and conclude that they are very few. Essentially, there is just one of them, since all the others can be obtained from it making 2-sums of appropriated matroids, as described in the next theorem. To avoid a more cumbersome statement for it, we need to extend the 2-sum operation for matroids having more than one element. When N and M are matroids such that E(N) ∩ E(M) = {e} and E(N) \ E(M) = {f}, the 2-sum of N with M is the matroid obtained from M by renaming e by f.

Theorem 1. Let H_{1}, H_{2}, K_{1}, K_{2}, K_{3} be matroids defined over the same ground set {a, b, c} such that

H_{1} ≃ U_{2,3}, H_{2} ≃ U_{1,3}, K_{i} ≃ U_{1,2} ⊕ U_{0,1}, for every i ∈ {1, 2, 3},

and a, b, c are loops of K_{1}, K_{2}, K_{3}, respectively. When {a, b, c} ∩ E({M}_{m}) = ∅, ({M}_{m}, {N}_{n}) is a non-preserving connected pair if and only if there are connected matroids P_{a}, P_{b}, P_{c} such that x ∈ P_{x}, |E(P_{x})| ≥ 2, for every x ∈ {a, b, c}, {P_{a} \{a}, P_{b} \{b}, P_{c} \{c}} is a partition of E({M}_{m}), {M}_{m} or {N}_{n} is equivalent to

{H_{1} ⊕_{2} N_{a} ⊕_{2} N_{b} ⊕_{2} N_{c}, H_{2} ⊕_{2} N_{a} ⊕_{2} N_{b} ⊕_{2} N_{c}}

and the other admissible multiset of matroids in this pair is equivalent to

{(L_{a} ⊕ K_{1}\a) ⊕_{2} N_{b} ⊕_{2} N_{c}, (L_{b} ⊕ K_{2}\b) ⊕_{2} N_{a} ⊕_{2} N_{c}, (L_{c} ⊕ K_{3}\c) ⊕_{2} N_{a} ⊕_{2} N_{b}},

where L_{x} is a matroid over P_{x} \ {x} such that r(L_{x}) = 0, for every x ∈ {a, b, c}.

As the non-preserving pairs are rare and well described, the rest of the paper shall be dedicated to prove results about preserving pairs. In section four, we shall prove the following theorem:

Theorem 2. If ({M}_{m}, {N}_{n}) is a non-trivial preserving connected pair, then there is a pair ({M′}_{2}, {N′}_{2}) such that {M}_{m} is equivalent to {M′}_{2} and {N}_{n} is equivalent to {N′}_{2}.

Thus, when a connected 2-polimatroid has non-equivalent decompositons, we can reorganize the matroids on these decompositons moving around connected components and ignoring loops, in such way that at the end we get only two matroids in each decompositon, unless these decompositions forms a non-preserving pair.

Now one example to show that theorem 2 is quite surprising: for each vertex v of the complete graph K_{n}, let M_{v} be a matroid such that E(M_{v}) = E(K_{n}), M_{v}|st(v) is a connected component of M and r_{M_{v}}(E(K_{n}) \ st(v)) = 0. When n ≥ 2, then {M_{v} : v ∈ V (K_{n})} is an admissible multiset of matroids which is not equivalent to one having less that n matroids.

A vector M = (M_{1}, M_{2}, M_{3}, M_{4}) with four matroids defined on the same ground set E is called a quad when these matroids satisfies:

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

for every X ⊆ E. M is said to be non-trivial, when {M_{1}, M_{2}} ≠ {M_{3}, M_{4}}. So, theorem 1 and theorem 2 reducess the problem of uniqueness of decomposition of a connected 2-polimatroid to the study of non-trivial quads.

In [3], Lemos and Mota shall present an algorithm to decide when a vector with two matroids (M_{1}, M_{2}) can beginning a non-trivial quad. Moreover, this algorithm gives all the possibilities for the others two matroids that completes that quad. Thus, the algorithm, theorem 1 and theorem 2 solves the uniqueness problem of decomposition of the rank function of a 2-polimatroid as the sum of rank function of matroids.

We shall have the following corollaries from these theorems, which guaranties uniqueness in many cases:

Corollary 1. If P is a connected matroidal 2-polimatroid such that size(P) ≥ 4, then the decompositon of P is unique.

Corollary 2. Suppose that P = (E, ρ) is a connected matroidal 2-polimatroid such that ρ(E) is odd. If the decomposition of P is not unique, then P has only two non-equivalent decompositions which forms a non-preserving pair.

Corollary 3. Suppose that P = (E, ρ) is a connected matroidal 2-polimatroid. If ρ(e) = 1, for some e ∈ E, then the decomposition of P is unique.

We say that a 2-polimatroid is binary when it decomposes as an admissible multiset of binary matroids.

Corollary 4. If P is a connected binary 2-polimatroid, then it has at most two non-equivalent decompositions.

Now, we give an example to show that a connected 2-polimatroid can have arbitrary large number of non-equivalent decompositions: let H be a family of subsets of a set E such that |H| = r and |H ∪ H′| ≥ r + 2, for every H, H′ ∈ H such that H ≠ H′. For Z ⊆ H, let M(Z) be the matroid having E as ground set and every subset of E with r elements not belonging to Z as a basis. When {X , Y} ≠ {H, ∅} is a partition of H, then ({M(H), M(∅)}, {M(X), M(Y)}) is a non-trivial pair.

2 Tutte’s geometry

In this section, we shall present some results from Tutte’s geometry. We shall use Tutte’s geometry, since it is natural to work with it when one is dealing with circuits.

We say that L is a Tutte-line of a matroid M, when L is the uniun of circuits of M and r^{∗}(M|L) = 2. P is said to be a Tutte-plane of M, when P is the uniun of circuits of M and r^{∗}(M|P) = 3. Every Tutte-line has a partition {L_{1}, L_{2}, …, L_{k}}, which is called canonical, such that C is a circuit of M contained in L if and only if C = L \ L_{i}, for some i ∈ {1, 2, …, k}. We say that a Tutte-line L or a Tutte-plane P is connected, when M|L or M|P is connected, respectively. When a line L is connected, its canonical partition has at least three sets. Now, we shall present some results of Tutte’s geometry.

(2.1) (4.26 of [9]) Suppose that P is a connected Tutte-plane of a matroid M. If C is a circuit of M contained in P, then there are at least two connected Tutte-lines of M contained in P which contains C.

(2.2) (4.171 of [9]) Suppose that P is a Tutte-plane of a matroid M. If L and L′ are different Tutte-lines of M contained in P, then L ∩ L′ contains exactly one circuit of M.

(2.3) (4.35 of [9]) Suppose that M is a connected matroid. If C and D are different circuits of M, then there is a sequence

C = C_{0}, C_{1}, C_{2}, …, C_{n} = D

of circuits of M such that C_{i−1} ∪ C_{i} is a connected Tutte-line of M, for every i ∈ {1, 2, …, n}.

Now, we shall present a result of Lehman. Before the introduction of its statement, we remember that the set of all circuits of a matroid M which contains an element e is denoted by C_{e}(M).

(2.4) (4.3.2 of [6]) Suppose that M and N are connected matroids defined on the same ground set. If C_{e}(M) = C_{e}(N), then N = M.

3 The non-preserving case

Throughout this section, we shall suppose that ({M}_{m}, {N}_{n}) is a pair. When X and Y are disjoint subsets of E({M}_{m}), then

{M\X/Y }_{m} denotes the multiset {M_{1}\X/Y, M_{2}\X/Y, …, M_{m}\X/Y }.

We shall define a minor of ({M}_{m}, {N}_{n}) as

({M}_{m}, {N}_{n})\X/Y = ({M\X/Y }_{m}, {N\X/Y }_{n}).

We denote ({M}_{m}, {N}_{n})\(E({M}_{m}) \ X) and {M\(E({M}_{m}) \ X)}_{m} by ({M}_{m}, {N}_{n})|X and {M|X}_{m}, respectively. We shall use the next result along this paper without refering to it.

(3.1) ({M}_{m}, {N}_{n})\X/Y is a pair.

Proof: When Z ⊆ E({M}_{m}) \ (X ∪ Y), we have that

∑_{i=1}^{m} r_{M_{i}\X/Y} (Z) = ∑_{i=1}^{m}[r_{M_{i}}(Z ∪ Y) − r_{M_{i}}(Y)]

= ∑_{i=1}^{m} r_{M_{i}}(Z ∪ Y) − ∑_{i=1}^{m} r_{M_{i}}(Y)

= ∑_{i=1}^{n} r_{N_{i}}(Z ∪ Y) − ∑_{i=1}^{n} r_{N_{i}}(Y)

= ∑_{i=1}^{n}[r_{N_{i}}(Z ∪ Y) − r_{N_{i}}(Y)] = ∑_{i=1}^{n} r_{N_{i}\X/Y} (Z)

(3.2) If M_{i}|X is loopless, for some i ∈ {1, 2, …, m}, then {M|X}_{k} is equivalent to {M_{i}|X, K}, for some matroid K.

Proof: As r_{M_{i}}({e}) = 1, for every e ∈ X, it follows that

r_{M_{1}}({e}) + ⋯ + r_{M_{i−1}}({e}) + r_{M_{i+1}}({e}) + ⋯ + r_{M_{m}}({e}) ≤ 1.

Thus, there is a matroid K such that every connected component N of M_{j} satisfying r(N) ≠ 0, for j ≠ i, is also a connected component of K.

Observe that every chain of elements of C_{≥2}({M}_{m}) has size one or two, otherwise there are three elements C_{1}, C_{2} and C_{3} of C_{≥2}({M}_{m}) such that C_{1} ⊂ C_{2} ⊂ C_{3}. Thus,

r_{M_{1}}({e}) + r_{M_{2}}({e}) + ⋯ + r_{M_{m}}({e}) ≥ 3,

for every element e ∈ C_{1}, since e cannot be a loop in M_{i}, when C_{j} ∈ C(M_{i}). Moreover, an element of C_{≥2}({M}_{m}) can have multiplicity at most two. When this happens, it does not contains or it is not contained in another element of C_{≥2}({M}_{m}). We denote by C_{min}({M}_{m}) the multiset of minimal elements of C_{≥2}({M}_{m}). Note that an element has multiplicity two in C_{min}({M}_{m}) if and only if is has multiplicity two in C_{≥2}({M}_{m}).

For a matroid K, we shall define

δ(K) = r(K) − ∑_{e∈E(K)} r_{K}({e}).

The following observation is fundamental in the proof of the next lemma:

(3.3) For a matroid K, δ(K) ≤ 0. Moreover, δ(K) = 0 if and only if C_{≥2}(K) = ∅ and δ(K) = −1 if and only if |C_{≥2}(K)| = 1.

(3.4) C_{min}({M}_{m}) = C_{min}({N}_{n}).

Proof: By symmetry, we need only to prove that C_{min}({M}_{m}) ⊆ C_{min}({N}_{n}). Let C be an element of C_{min}({M}_{m}). For X ⊆ C, observe that

∑_{i=1}^{m} δ(M_{i}|X) = ∑_{i=1}^{m} (r_{M_{i}}(X) − ∑_{x∈X} r_{M_{i}}({x}))

= ∑_{i=1}^{m} r_{M_{i}}(X) − ∑_{i=1}^{m} ∑_{x∈X} r_{M_{i}}({x})

= ∑_{i=1}^{m} r_{M_{i}}(X) − ∑_{x∈X} ∑_{i=1}^{m} r_{M_{i}}({x})

= ∑_{i=1}^{n} r_{N_{i}}(X) − ∑_{x∈X} ∑_{i=1}^{n} r_{N_{i}}({x})

= ∑_{i=1}^{n} (r_{N_{i}}(X) − ∑_{x∈X} r_{N_{i}}({x})) = ∑_{i=1}^{n} δ(N_{i}|X)

Now, we shall prove that:

Step 1: C_{≥2}({N|X}_{n}) = ∅, for every X ⊂ C.

When X ⊂ C, C_{≥2}(M_{i}|X) = ∅, for every i ∈ {1, 2, …, m}, since C ∈ C_{min}({M}_{m}). By (3.3), we have that

0 = ∑_{i=1}^{m} δ(M_{i}|X) = ∑_{i=1}^{n} δ(N_{i}|X).

Thus, by (3.3), δ_{N_{i}}(X) = 0 and C_{≥2}(N_{i}|X) = ∅, for every i ∈ {1, 2, …, n}.

So, for every i ∈ {1, 2, …, m} and j ∈ {1, 2, …, n}, C_{≥2}(M_{i}|C) ∈ {∅, {C}} and C_{≥2}(N_{j}|C) ∈ {∅, {C}}. Thus, the result follows when we stabilish:

Step 2: |C_{≥2}({M|C}_{m})| = |C_{≥2}({N|C}_{n})|.

From (3.3) and step 1, we have that

−|C_{≥2}({M|C}_{m})| = ∑_{i=1}^{m} δ(M_{i}|X) = ∑_{i=1}^{n} δ(N_{i}|X) = −|C_{≥2}({N|C}_{n})|

and the result follows.

We define the following multiset

C_{uni}({M}_{m}) = C_{≥2}({M}_{m}) \ C_{≥2}({N}_{n}).

We define C_{uni}({N}_{n}) similarly. In (3.7), we shall describe the nice behaviour of the elements of C_{uni}({M}_{m}). To do this, we need to prove some preliminary lemmas.

(3.5) If C ∈ C_{uni}({M}_{m}) and C′ ∈ C_{uni}({N}_{n}), then C ⊈ C′ and C′ ⊈ C.

Proof: We shall argue by contradiction and we assume that the result fails. Without loss of generality, we may suppose that C ⊆ C′. By definition of these multisets, we have that C ⊂ C′. By (3.2), there are matroids K and K′ such that {M|C}_{m} and {N|C}_{n} are equivalent to {M_{i}|C, K} and {N_{j}|C, K′}, respectively, where C is a circuit of M_{i} and C′ is a circuit of N_{j}. If C′′ ∈ C_{≥2}({M}_{m}) is contained in C and C′′′ ∈ C_{≥2}({N}_{n}) is contained in C′, then C′′ ∈ C_{min}({M}_{m}) and C′′′ ∈ C_{min}({N}_{n}). So, by (3.4), C′′ and C′′′ belongs to C_{≥2}({M}_{m})∩C_{≥2}({N}_{n}). Thus, K and K′ have the same circuits and K = K′. We arrive at a contradiction, since M_{i}|C ≠ M_{j}|C, and the result follows.

(3.6) For i ∈ {1, 2, …, m}, if L is a Tutte-line of M_{i} having canonical partition {L_{1}, L_{2}, L_{3}} such that C_{j} = L\L_{j} is a circuit of N_{j}, for every j ∈ {1, 2, 3}, then L ∈ C_{uni}({M}_{m}).

Proof: By (3.2), there is a matroid K such that E(K) = L and {M|L}_{m} is equivalent to {M_{i}|L, K}. For j ∈ {1, 2, 3}, observe that r(N_{j}|L_{j}) = 0 because r_{N_{k}}({e}) = 1, for every e ∈ L_{j} and k ∈ {1, 2, 3} \ {j}. Thus, C_{≥2}(N_{i}|L) = {C_{i}}. Hence C_{≥2}({N|L}_{n}) = {C_{1}, C_{2}, C_{3}}. Observe that

r_{K}(L) = (∑_{j=1}^{3} r_{N_{j}}(L)) − r_{M_{i}}(L) = (∑_{j=1}^{3}(|L \ L_{j}| − 1)) − (|L| − 2) = |L| − 1.

Hence C_{≥2}({N|L}_{n}) △ C_{≥2}({M_{i}|L, K}) = {C}, for some circuit C of K. So, C ∈ C_{uni}({M}_{m}). When L = C, then the result follows. We may suppose that there is e ∈ L \ C. In this case, we arrive at a contradiction, since r_{H}(L \ {e}) = r_{H}(L), for every H ∈ {K, N_{1}, N_{2}, N_{3}} and r_{M_{i}}(L) = r_{M_{i}}(L \ {e}) + 1.

(3.7) If C ∈ C_{uni}({M}_{m}), then C is a Tutte-line of M_{i} containing exactly three circuits of M_{i}, for some i ∈ {1, 2, …, m}, and these circuits are circuits of different N_{j}.

Proof: We do not loose generality when we suppose that C is a circuit of M_{1}. By (3.2), {M|C}_{m} is equivalent to {M_{1}|C, K}. By (3.4) and (3.5), we have that

C_{≥2}({M_{1}|C, K}) △ C_{≥2}({N|C}_{n}) = {C}.  (1)

Thus,

C_{≥2}(K) = C_{≥2}({N}_{n}).  (2)

Observe that K has a connected component H such that r(H) > 0 and H is not a connected component of N_{i}, for every i ∈ {1, 2, …, n}, otherwise A({K′, K}) = A({N|C}_{n}), where K′ is a matroid over C such that r(K′) = |C|.

In this paragraph, we shall prove that H has circuits C′ and C′′ such that

{C′, C′′} ⊈ C(N_{i}), for every i ∈ {1, 2, …, n}.  (3)

If (3) does not occur, then C(H) ⊆ C(N_{i}), for some i ∈ {1, 2, …, n}, since every element of C_{≥2}({N}_{n}) has multiplicity one, by (2). So, N_{i} has a connected component H′ such that C(H) ⊆ C(H′). By (2), C(H′) ⊆ C(K). Hence C(H′) = C(H) and H = H′. We arrive at a contradiction and (3) follows. Now, we shall prove that:

Step 1: There are circuits C_{1} and C_{2} of H such that C_{1} ∪ C_{2} is a connected Tutte-line of H, C_{1} is a circuit of N_{i} and C_{2} is a circuit of N_{j}, for j ≠ i, say i = 1 and j = 2.

By (3), there are circuits C′ and C′′ of H such that, for every i ∈ {1, 2, …, n}, {C, C′′} ⊈ C(N_{i}). So, by (2.3), there is a sequence of circuits of H

C′ = D_{0}, D_{1}, D_{2}, …, D_{k} = C′′

such that D_{i−1} ∪ D_{i} is a connected Tutte-line of H, for every i ∈ {1, 2, …, k}. Thus, for some i ∈ {1, 2, …, k}, {D_{i−1}, D_{i}} ⊈ C(N_{j}), for every j ∈ {1, 2, …, n}. Take C_{1} = D_{i−1} and C_{2} = D_{i}.

Let {L_{1}, L_{2}, …, L_{k}} be the canonical partition of L = C_{1} ∪ C_{2}. We may suppose that C_{1} = L \ L_{1} and C_{2} = L \ L_{2}. As L is connected, it follows that k ≥ 3. By (1), we have that

C_{≥2}({M|L}_{m}) \ {C} = C_{≥2}({N|L}_{n}) = C(H|L) = {L \ L_{1}, L \ L_{2}, …, L \ L_{k}}.

Step 2: For every i ∈ {1, 2, …, n}, |C(H|L) ∩ C(N_{i}|L)| ≤ 1.

Suppose that step 2 is not true. So, there is an i ∈ {1, 2, …, n} such that |C(H|L) ∩ C(N_{i}|L)| ≥ 2, say i = 2. Let C_{3} be a circuit of N_{2}|L different from C_{2}. Observe that (C_{2} ∪ C_{3}) \ e, for e ∈ L_{1}, does not contains a circuit of N_{2}|L, otherwise this circuit would be C_{1}. We arrive at a contradiction and the result follows.

Without loss of generality, we may suppose that C_{i} = L \ L_{i} is a circuit of N_{i}, for i ∈ {1, 2, …, k}. As an element e of E({M}_{m}) cannot be a loop in at most two N_{i}’s, it follows that k = 3. By (3.6), L ∈ C_{uni}({M}_{m}). Thus, L = C.

(3.8) Suppose that m = 2, L is a connected Tutte-line of M_{2} and r([M_{1}|L]^{∗}) ≤ 1. If C_{uni}({M|L}_{m}) = ∅, then L is a Tutte-line of N_{i} having the same canonical partition as in M_{2}, for some i ∈ {1, 2, …, n}.

Proof: By (3.7), C_{≥2}({N|L}_{n}) ⊆ C_{≥2}({M|L}_{m}), since m = 2. Hence, by hypothesis,

C_{≥2}({N|L}_{n}) = C_{≥2}({M|L}_{m}).

Suppose that {L_{1}, L_{2}, …, L_{k}} is the canonical partition of L in M_{2}. Consider the set X = {i : C(N_{i}) ∩ C(M_{2}|L) ≠ ∅}.

In this paragraph, we shall prove that |X| ≤ 2. Suppose that |X| ≥ 3. If k ≥ 4, then, for l ∈ {1, 2, 3}, there are i_{l} and j_{l} such that |{i_{1}, i_{2}, i_{3}}| = |{j_{1}, j_{2}, j_{3}}| = 3 and C_{j_{l}} ∈ C(N_{i_{l}}) ∩ C(M_{2}|L). Hence

∑_{i∈X} r_{N_{i}}({e}) ≥ 3,

for every e ∈ C_{j_{1}} ∩ C_{j_{2}} ∩ C_{j_{3}}. We arrive at a contradiction. Thus, k = 3 and we arrive at a contradiction by (3.6). So, |X| ≤ 2.

If |X| = 1, then the result follows. Thus, we may suppose that |X| = 2. We can order the sets on the canonical partition of L in M_{2} and the matroids in {N}_{n} such that C_{1}, …, C_{t} are circuits of N_{1} and C_{t+1}, …, C_{k} are circuits of N_{2}. Without loss of generality, we may suppose that t ≥ 2. Hence L is a Tutte-line of N_{1} having canonical partition {L_{1}, …, L_{t}, L \ (L_{1} ∪ ⋯ ∪ L_{t})}. If t = k − 1, then C′ = C_{k}, where C′ is the circuit of M_{1}|L, and the result follows. So, we may suppose that t ≤ k − 2. Observe that C′ = L_{1} ∪ ⋯ ∪ L_{t}. Similarly, we have that C′ = L_{t+1} ∪ ⋯ ∪ L_{k} and we arrive at a contradiction.

If K is a matroid and Z ⊆ E(K), a Z-arc of K is a minimal non-empty subset A ⊆ E(K) \ Z such that there is a circuit C of K with C \ Z = A and C ∩ Z ≠ ∅. A fundamental for A is a circuit C such that C \ Z = A, where A is a Z-arc. We denote by arc_{K}(Z) the set of all Z-arcs of K. When A ∈ arc_{K}(Z) and P ⊆ Z, we say that A → P in K if there is a Z-fundamental for A included in A ∪ P. For its negation, we write A ↛ P.

(3.9) Suppose that L ∈ C_{uni}({M}_{m}). If L is a circuit of M_{1}, L is a Tutte-line of M_{2} and A is a L-arc of M_{2} which does not contain properly a L-arc of M_{1}, then C_{uni}({M}_{m}) ∩ C(M_{1}|(L ∪ A)) ≠ {L}.

Proof: Suppose that C_{uni}({M}_{m}) ∩ C(M_{1}|(L ∪ A)) = {L}. Without loss of generality, we may suppose that E({M}_{m}) = L ∪ A. Choose a ∈ A. By (3.2), there is a matroid K such that {M/(A \ {a})}_{m} is equivalent to {M_{2}/(A \ {a}), K}. Observe that L ∪ {a} is a connected Tutte-plane of M_{2}/(A \ {a}), since A is a L-arc of M_{2}. As A does not contain properly a L-arc of M_{1}, it follows that L is a circuit of K and r(K^{∗}) ≤ 2. Moreover, a is a loop of K or a coloop of K or L ∪ {a} is a Tutte-line of K.

By (3.7), we may suppose that C(M_{2}|L) = {C_{1}, C_{2}, C_{3}} and that C_{i} is a circuit of N_{i}, for every i ∈ {1, 2, 3}. By (2.1), it follows that there is a connected Tutte-line L′_{i} of M_{2}/(A \ {a}) such that C_{i} ⊂ L′_{i} ⊂ L ∪ {a} and L′_{i} ≠ L. Hence |C(M_{1}/(A \ {a})|L′_{i})| ≤ 1, since L′_{i} ⊂ L ∪ {a}. Thus, applying (3.8) to the pair ({M}_{m}, {N}_{n})/(A\{a})|L′_{i}, we have that L′_{i} is a connected line of N_{i}/(A\{a}). We arrive at a contradiction because a ∈ L′_{i}, for every i ∈ {1, 2, 3}, and hence r_{N_{1}}({a}) + r_{N_{2}}({a}) + r_{N_{3}}({a}) = 3.

(3.10) Suppose that L is a circuit of M_{1}, L is a Tutte-line of M_{2} having canonical partition {L_{1}, L_{2}, L_{3}} and C_{i} = L \ L_{i} is a circuit of N_{i}, for every i ∈ {1, 2, 3}. Then, arc_{M_{1}}(L) = arc_{M_{2}}(L). Moreover, there is a partition {A_{1}, A_{2}, A_{3}} of arc_{M_{1}}(L) such that

(i) arc_{N_{i}}(L) = arc_{M_{1}}(L) \ A_{i}, for every i ∈ {1, 2, 3};

(ii) for every i ∈ {1, 2, 3} and {i, j, k} = {1, 2, 3}, if A ∈ A_{i}, then A → L_{i} in K, for every K ∈ {M_{1}, M_{2}, N_{j}, N_{k}}.

Proof: Observe that L_{i} is a set of loops of N_{i}, for every i ∈ {1, 2, 3}, and that L ∈ C_{uni}({M}_{m}). When A ∈ arc_{M_{i}}(L), for some i ∈ {1, 2}, then M_{i}|(L ∪ A) is connected. By (3.2), {M|(L ∪ A)}_{m} is equivalent to {M_{i}|(L ∪ A), K_{A}}, for some matroid K_{A} defined on L ∪ A.

Step 1: C_{≥2}({N|(L ∪ A)}_{n}) ⊆ C_{≥2}({M|(L ∪ A)}_{m}), when A ∈ arc_{M_{1}}(L) ∪ arc_{M_{2}}(L).

As A is a L-arc of M_{i}, for some i ∈ {1, 2}, by (3.7), it follows that

C_{≥2}({N|(L ∪ A)}_{n}) ⊆ C_{≥2}({M_{i}|(L ∪ A), K_{A}}),

since |{M_{i}|(L ∪ A), K_{A}}| = 2 and the step follows.

Observe that arc_{M_{1}}(L) = arc_{M_{2}}(L) follows from the next step:

Step 2: If A is a minimal set belonging to arc_{M_{1}}(L)∪arc_{M_{2}}(L), then A belongs to arc_{M_{1}}(L) ∩ arc_{M_{2}}(L).

Suppose that this step fails. Choose a minimal set A of arc_{M_{1}}(L)∪arc_{M_{2}}(L) which does not belong to arc_{M_{1}}(L)∩arc_{M_{2}}(L). We have two cases to deal with:

(a) A ∈ arc_{M_{1}}(L) \ arc_{M_{2}}(L); or (b) A ∈ arc_{M_{2}}(L) \ arc_{M_{1}}(L). In both cases, for i ∈ {1, 2}, {a} is a L-arc of M_{i}|(L ∪ A)/(A \ {a}) if and only if A is a L-arc in M_{i}. Now, we shall prove that

C_{≥2}({M|(L ∪ A)/(A \ {a})}_{m}) △ C_{≥2}({N|(L ∪ A)/(A \ {a})}_{n}) = {L}. (1)

By setp 1, we need only to prove that C_{uni}({M|(L ∪ A)/(A \ {a})}_{m}) = {L}. In both cases, a is a loop or coloop of K_{A}/(A\{a}). By (3.7), if C ∈ C_{uni}({M|(L∪ A)/(A \ {a})}_{m}), then a ∉ C. So, C = L and we have (1).

Suppose that (a) occurs. Let L = D_{0}, D_{1}, D_{2}, …, D_{s} be the circuits of M_{1}|(L ∪ A)/(A \ {a}) contained in L ∪ {a}. As D_{i} ∪ D_{j} contains L, when i ≠ j, and L_{i} is a set of loops of N_{i}, it follows that each N_{i}|(L ∪ A)/(A \ {a}) has at most one D_{j} as a circuit. Thus, by (1), we may suppose that s = 2 and D_{i} is a circuit of N_{i}|(L ∪ A)/(A \ {a}). Hence, by (1), C_{i} ∩ D_{i} = ∅, otherwise C_{i} ∪ D_{i} contains another circuit of M_{1}|(L ∪ A)/(A \ {a}). So, (D_{1} ∪ D_{2}) ∩ L_{3} = ∅ and we arrive at a contradiction. When (ii) happens, we arrive at a contradiction by (3.9) and (1). Thus, step 2 follows.

Step 3: If A ∈ arc_{M_{1}}(L), then, there is an i ∈ {1, 2, 3}, such that A ∈ arc_{K}(L) and A → L_{i} in K, for every K ∈ {M_{1}, M_{2}, N_{j}, N_{k}}, where {i, j, k} = {1, 2, 3}.

By step 2, for every A ∈ arc_{M_{1}}(L), P = A ∪ L is a Tutte-line of M_{1} and P is a Tutte-plane of M_{2}. By (3.9), there is L′ ∈ C_{uni}({M}_{m}) ∩ C(M_{1}|P) such that L ≠ L′. By (3.7), L′ is a Tutte-line of P. Thus, the circuit of M_{2} contained in L ∩ L′, which exists by (2.2), must be equal to C_{i}, for some i ∈ {1, 2, 3}, say i = 1.

First, we shall determine the structure of the Tutte-plane P of M_{2} using the Tutte-lines L and L′ of M_{2}. By (3.7), we may suppose that the other circuits contained in L′ are C′_{2} and C′_{3}, with C′_{i} being a circuit of N_{i}, for i ∈ {2, 3}. By (2.1), there is a connected Tutte-line L′_{i} contained in P such that C′_{i} ⊂ L′_{i} and L′_{i} ≠ L′. The circuit of M_{2} contained in L′_{i} ∩ L is C_{2} or C_{3}. Observe that L′_{i} does not contains a circuit of N_{1}, since A is a set of loops of N_{1} and every circuit of M_{2}|L′_{i} different of C_{j} contains A. By (3.7), C_{uni}({M}_{m}) ∩ C(M_{1}|L′_{i}) = ∅. Hence, by (3.8) applied to the pair ({M_{1}|P, M_{2}|P }, {N|P }_{n}), L′_{i} is a Tutteline of N_{2} or N_{3} having the same canonical partition. Thus, L′_{i} = C_{i} ∪ C′_{i}, for i ∈ {2, 3}.

Let C be the circuit of M_{2} contained in L′_{2} ∩ L′_{3}, which exists by (2.2). So, C is a circuit of both N_{2} and N_{3}. Hence C is a circuit of both M_{1} and M_{2}. Moreover, C ∩ (L_{2} ∪ L_{3}) = ∅. Hence A → L_{1} in H, for H ∈ {M_{1}, M_{2}, N_{2}, N_{3}} because C is a circuit of all these matroids and A ⊂ C ⊆ A ∪ L_{1}. We have stablished step 3.

So, we get the partition {A_{1}, A_{2}, A_{3}} of arc_{M_{1}}(L) setting:

A_{i} = {A ∈ arc_{M_{1}}(L) : A → L_{i}},

for i ∈ {1, 2, 3}, and the result follows, from step 1, step 2 and step 3.

For the proof of theorem 1, we need the following result of Seymour:

(3.11) (3.8 of [7]) Let K be a matroid, let Z ⊆ E(K), and let {P_{1}, P_{2}} be a partition of Z. Then either there is a Z-arc A such that A ↛ P_{1}, A ↛ P_{2}, or there is a partition {X_{1}, X_{2}} of E(K) such that X_{i} ∩ Z = P_{i}(i = 1, 2) and

r(X_{1}) + r(X_{2}) − r(K) = r(P_{1}) + r(P_{2}) − r(Z).

We shall apply Seymour’s result only in the case that Z ≠ ∅. Looking in the proof of this result, one concludes that X_{i} is choosen such that

X_{i} = ⋃{P_{i} ∪ A : A ∈ arc_{Z}(K) and A → P_{i} in K}.

So, when we refer to this result, we are supposing that the partitions are taken as described above.

Proof of theorem 1: As ({M}_{m}, {N}_{n}) is non-preserving, it follows that C_{uni}({M}_{m}) ≠ ∅ or C_{uni}({N}_{n}) ≠ ∅, say C_{uni}({M}_{m}) ≠ ∅. Chose C ∈ C_{uni}({M}_{m}). Without loss of generality, we may suppose that C is a circuit of M_{1}. By (3.7), C is a line of M_{i}, for some i ≥ 2, say i = 2. Moreover, we may suppose that the canonical partition of C in M_{2} is {L_{1}, L_{2}, L_{3}} and C_{i} = L \ L_{i} is a circuit of N_{i}, for i ∈ {1, 2, 3}, say. Now, we shall define

X_{i} = ⋃{A ∪ L_{i} : A ∈ arc_{M_{1}}(C) and A → L_{i} in M_{1}}.

By (3.10), we have that {X_{1}, X_{2}, X_{3}} is a partition of E({M}_{m}), otherwise {E({M}_{m}) \ (X_{1} ∪ X_{2} ∪ X_{3}), X_{1} ∪ X_{2} ∪ X_{3}} is a 1-separation of M_{i}, for every i ∈ {1, 2, …, m}. By (3.11), when |X_{i}| ≥ 1, we have that {X_{i}, E({M}_{m})} is an exact 2-separation of M_{1}, M_{2} and N_{j}, for j ≠ i. The result follows, since the matroids that are decomposed using these 2-separations and has X_{i} in its ground set are equal, by (3.8)(ii) and (2.4).

4 The preserving case

Throughout this section, we shall suppose that ({M}_{m}, {N}_{n}) is a non-trivial preserving pair. We shall denote E({M}_{m}) by E. Let ρ be the rank function of the 2-polimatroid P defined by this pair.

(4.1) If ρ(e) = 1, for some e ∈ E, then A({M}_{m}) ∩ A({N}_{n}) ≠ ∅.

Proof: Let M_{i} and N_{j} be matroids such that r_{M_{i}}({e}) = r_{N_{j}}({e}) = 1. Let M′ and N′ be the connected component of M_{i} and N_{j} that contains e, respectively. As e is a loop of M_{k} and N_{l}, for every k ≠ i and l ≠ j, it follows that M′ and N′ have the same circuits containing the element e, since ({M}_{m}, {N}_{n}) is preserving. Thus, M′ = N′, by (2.4).

(4.2) If P is connected, then A({M}_{m}) ∩ A({N}_{n}) = ∅.

Proof: Suppose that A = A({M}_{m}) ∩ A({N}_{n}). Observe that (A({M}_{m}) \ A, A({N}_{n}) \ A) is a non-trivial preserving pair which defines a 2-polimatroid P′ having rank function ρ′. By (4.1), ρ′({e}) ≠ 1, for every e ∈ E. So, X = {e ∈ E : ρ′({e}) = 0} and Y = {e ∈ E : ρ′({e}) = 2} is a partition of E. As X is a set of loops, for every matroid in (A({M}_{m}) ∪ A({N}_{n})) \ A, and Y a set of loops, for every matroid in A, it follows that {X, Y } is a 1-separation for the 2-polimatroid P, when X ≠ ∅ and Y ≠ ∅. So, X = ∅ or Y = ∅. Thus, X = ∅, otherwise ({M}_{m}, {N}_{n}) is trivial.

For the proof of theorem 2, we need the following result of Lemos:

(4.3) (2.12 of [2]) If (M_{1}, M_{2}, M_{3}, M_{4}) is a non-trivial connected quad, then there is at most one i ∈ {1, 2, 3, 4} such that M_{i} is not a connected matroid. Moreover, when M_{i} is not connected, it has exactly two connected components.

Proof of theorem 2: For a matroid H, we denote by loop(H) the set of its loops. Now, we shall consider a maximal member S of

S = {E \ loop(H) : H ∈ A({M}_{m}) ∪ A({N}_{n})}.

Without loss of generality, we may suppose that M_{1}|S is connected. By (3.2), there is a matroid K such that {M|S}_{m} is equivalent to {M_{1}|S, K}.

In this paragraph, we shall prove that {N|S}_{n} is also equivalent to an admissible multiset containing two matroids. Suppose that this is not the case, and let {K}_{p} be an admissible multiset of matroids equivalent to {N|S}_{n} having p minimum. Thus, p ≥ 3. For each i ∈ {1, 2, …, p}, set L_{i} = E \ loop(K_{i}). So, for {i, j} ⊂ {1, 2, …, p}, L_{i} ∩ L_{j} ≠ ∅, otherwise we could replace K_{i} and K_{j} by K_{i}|L_{i} ⊕ K_{j}|L_{j} ⊕ K_{i}|(loop(K_{i}) ∩ loop(K_{j})) in the admissible multiset {K}_{p} and we arrive at a contradiction by the choice of p. Choose an element a_{ij} belonging to L_{i} ∩ L_{j}. Observe that a_{ij} ∈ loop(K_{l}), for l ∉ {i, j}. Let L be a connected Tutte-line of M_{1}|S containing {e_{12}, e_{13}, e_{23}}. So, |C(N_{i}) ∩ C(M_{1}|L)| ≤ 1 and L contains only three circuits of M_{1}. We arrive at a contradiction, by (3.6).

Let ({M′}_{2}, {N′}_{2}) be a pair such that {M|S}_{m} and {N|S}_{n} are equivalent to {M′}_{2} and {N′}_{2}, respectively. So, (M′_{1}, M′_{2}, N′_{1}, N′_{2}) is a quad. It must be non-trivial, otherwise M′_{1} = N′_{1}, say, and by the choice of S, M′_{1} and N′_{1} are connected components of some matroid in {M}_{m} and {N}_{n}, recpectively. But this is contrary to (4.2). By (4.3), M′_{1} and M′_{2} are connected or N′_{1} and N′_{2} are connected, say M′_{1} and M′_{2} are connected. Thus, by the choice of S, for i ∈ {1, 2}, M′_{i} is a connected component of M_{i}. So, S is a separator for both M_{1} and M_{2}. Hence {S, E \ S} is a 1-separation for P, unless S = E. The result follows.

5 The proof of the colloraries

Throughout this section, we shall suppose that ({M}_{m}, {N}_{n}) is a non-trivial pair which defienes a connected 2-polimatroid P. We shall denote E({M}_{m}) by E. Let ρ be the rank function of P. First, we shall state a result of Lemos [?]:

(5.1) (theorem 2 of [1]) If (M_{1}, M_{2}, M_{3}, M_{4}) is a non-trivial connected quad, then

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

(5.2) If ({M}_{m}, {N}_{n}) is non-preserving, then it is the unique pair defining P.

Proof: By theorem 1, we may suppose that m = 2 and n = 3. Let ({M′}_{m}, {N′}_{n}) be another non-trivial pair that defines P. When ({M′}_{m′}, {N′}_{n′}) is non-preseving, we may suppose that m′ = 2 and n′ = 3. By theorem 1, {N′}_{n′} is equivalent to {N}_{n}. So, (M_{1}, M_{2}, M′_{1}, M′_{2}) is a non-trivial connected quad. We arrive at a contaridiction, by (5.1), because r(M_{1}) ≠ r(M_{2}). Thus, ({M′}_{m′}, {N′}_{n‘}) is preserving. By theorem 2, we may suppose that m′ = n′ = 2. In this case, we also arrive at the same contradiction, by (5.1), since (M_{1}, M_{2}, M′_{1}, M′_{2}) is a non-trivial connected quad.

All the corollaries are imediate consequences of (5.2) and theorem 1 in the case that ({M}_{m}, {N}_{n}) is non-preseving. Thus, we may suppose that every pair of admissible multisets which decomposes P is preserving. By theorem 2, we do not loose generality, if we suppose that m = n = 2. So, (M_{1}, M_{2}, N_{1}, N_{2}) is a non-trivial quad.

(5.3) (2.2 of [2]) If (M_{1}, M_{2}, M_{3}, M_{4}) is a non-trivial connected quad, then M_{i} is loopless, for every i ∈ {1, 2, 3, 4}.

Corollary 1 follows (4.3). Corollary 2 from (5.1). Corollary 3 from (5.3). Corollary 4 from (4.2) of Lemos [2]. We shall not state the last result of Lemos here, since it envolves some tecnical definitions. The interested reader should consult the original paper. Moreover, the binary connected 2-polimatroid with two non-equivalent decompositions are completely described by Lemos result.

6 Acknowledgements

The author would like to thank Professor James Oxley for some discussions on the topic of this paper and all the staff of the Department of Mathematics of Louisiana State University for their hospitality.

7 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 to publication.

[3] M.Lemos and S.Mota, The reconstruction of a matroid from its connectivity function, in preparation.

[4] L.Lovász and M.Plummer, Matching Theory, North-Holand, Amsterdan, 1986.

[5] U.S.R.Murty and I.Simon, A β-function that is not a sum of rank functions of matroids, Problèmes Combinatoiries et Théorie des Graphes (eds. J.- C.Bermond, J.-C.Fournier, M. Las Vergnas and D. Sotteau), Editions du CNRS, Paris, 1978, 305-306.

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

[7] P.D.Seymour, Decomposition of regular matroids, Journal of Combinatorial Theory Series B 28 (1980), 305-359.

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

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