Lobachevskii Journal of Mathematics

http://ljm.ksu.ru
ISSN 1818-9962

Vol. 26, 2007, 5–15 \begin{matrix}c \\ ◯ \end{matrix} H. Azanchiler

H. Azanchiler

A CHARACTERIZATION OF THE BASES OF LINE-SPLITTING MATROIDS

(submitted by M. M. Arslanov)

Abstract. In [1] the author extended n-line splitting from graphs to binary matroids and characterized the circuits of the result matroid, i.e. line-splitting matroid (es-splitting). In this paper, we characterize dependent, independent and base sets in line-splitting matroid M_{X}^{e}. Moreover, we determine rank function of M_{X}^{e}.

1. Introduction

Fleischner [2] introduced the idea of splitting a vertex of degree at least three in a connected graph and Raghunathan, Shikare and Waphare [4] extended the splitting operation from graphs to binary matroids. Shikare, Azadi and Waphare [6] further generalized this operation and also in [7] extended the n-point splitting operation from graphs to a binary matroid. Moreover, in [5] Shikare and Azadi determined the base of splitting matroids and the author in [1] extended the n-line splitting operation [8] from graphs to the binary matroids by the following way.

Definition 1.1. Let M be a binary matroid on a set S and X be a subset of S, e ∈ X. Suppose that A is a matrix over GF (2), that represents the matroid M. Let A_{X}^{e} be the matrix that is obtained by adjoining an extra row to A with this row being zero everywhere except in the columns corresponding to the elements of X, where it takes the value 1 and then adjoining two columns a and γ to the resulting matrix such that the column a is zero everywhere except in the last row (new row), where it takes the value 1, and γ is a sum of two column vectors corresponding to a and e.

Let M_{X}^{e} be the vector matroid of the matrix A_{X}^{e}. We say that M_{X}^{e} has been obtained from M by splitting e and X in M. The transition from M to M_{X}^{e} is called splitting of M with respect to e and X. For convenience, we say that M_{X}^{e} is an element-set splitting (es-splitting) matroid.

Proposition 1.1 ([1]). Let M = (S, C) be a binary matroid, X ⊆ S, e ∈ X, and a, γ ∉ S. Then M_{X}^{e} = (S ∪ {a, γ}, C_{X}^{e}), where C_{X}^{e} = C_{0} ∪ C_{1} ∪ C_{2} ∪ C_{3} ∪ {Δ} with Δ = {e, a, γ} and

C_{0} ={C ∈ C | C contains an even number of elements of X};
C_{1} =the set of minimal members of {C_{1} ∪ C_{2} | C_{1}, C_{2} ∈ C, C_{1} ∩ C_{2} = ∅

and each C_{1} and C_{2} contains an odd number of element of X such that C_{1} ∪ C_{2} contains no member of C_{0}};

C_{2} ={C ∪ {a} | C ∈ C and C contains an odd number of elements of X}.
C_{3} =C_{31} ∪ C_{32} ∪ C_{33},

where

C_{31} ={C ∪ {e, γ}, | C ∈ C, e ∉ C and C contains an odd number

of elements of X},

C_{32} ={(C \ e) ∪ {γ} | C ∈ C, e ∈ C and C contains an odd number

of elements of X},

C_{33} ={(C \ e) ∪ {a, γ} | C ∈ C, e ∈ C and C \ e contains an odd number

of elements of X}.

The terminology from matroid theory which we use can be obtained from Oxely [3].

2. Independent Set in M_{X}^{e}

Next theorem characterize the dependent set in es-splitting matroid M_{X}^{e}. Theorem 2.1. Let M be a binary matroid on a set S and D be a dependent set in M. Then D is dependent in M_{X}^{e} if and only if D does not contain precisely one circuit of M containing an odd number of elements of X. Proof. Let D be a dependent set in M and suppose D does not contain precisely one circuit of M containing an odd number of elements of X. Then we have the following two cases:

(i) D contains a circuit C of M with even number of elements of X. Then C is a circuit of M_{X}^{e} and is contained in D. Therefore, D is dependent set in M_{X}^{e}.

(ii) D contains at least two circuits, say C and C′, with odd number of elements of X. Then

CΔC′ = C_{1} ∪ C_{2} ∪ … ∪ C_{m}.

If for any of the 1 ≤ i ≤ m, C_{i} contains an even number of elements of X, then it is a circuit in M_{X}^{e} and is contained in D. Suppose there is no such C_{i}. Let C_{j} and C_{k} be two circuits each of which contains an odd number of elements of X. If C_{j} ∪ C_{k} contains a member of C_{0}, say C′′, then C′′ ⊆ D and we are done. Otherwise C_{j} ∪ C_{k}, or a minimal member of C_{1}, contained in it, is a circuit of M_{X}^{e} contained in D.

Conversely, let D be a dependent set of M which is also dependent in M_{X}^{e}. Since D ⊆ S, a or γ or both do not belong to D. Suppose C is a circuit of M_{X}^{e} contained in D. Then C contains an even number of elements of X. We have two cases:

(i) C is a circuit of M containing an even number of elements of X. (ii) C is a disjoint union of two circuits of M each of which contains

an odd number of elements of X.

In both cases D cannot contain precisely one circuit of M containing an odd number of elements of X. □

Lemma 2.2. Every independent set in M is independent in M_{X}^{e}.

Remark 2.3. Converse of the lemma is not true. By Theorem 2.1, every circuit of M containing an odd number of element of X is a independent set of M_{X}^{e}.

The next theorem characterizes the independent sets of M_{X}^{e}.

Theorem 2.4. Let I ⊆ S ∪ {a, γ}. Then I is independent in M_{X}^{e} if and only if one of the following conditions hold.

(1) I = I_{1} ∪J, where I_{1} is an independent set in M and J ∈ {ϕ, {a}}.

(2) I = I_{1} ∪ {γ}, where I_{1} is an independent set in M and no circuit of M is contained in I_{1} ∪ {e}.

(3) I = (I_{1} \ {e}) ∪ {a, γ}, where I_{1} is an independent set in M containing e.

(4) I = (∪_{i=1}^{m}C_{i}) ∪ J, where J ∈ {ϕ, {γ}}, each C_{i} contains an odd number of element of X, C_{i} ∩ C_{j} ≠ ϕ, i ≠ j, i, j = 1, 2, …, m, I contains no member of C_{0}, and I ∪ {e} contains no circuit of M other than C_{i} for i = 1, 2, …, m.

Proof. (1) Let I_{1} be an independent set in M. By Lemma 2.2, I_{1} is independent in M_{X}^{e}. Thus, I = I_{1} ∪ J, where J = ϕ, is independent in M_{X}^{e}. Further, by Definition 1.1 of A_{X}^{e}, I_{1} ∪ {a} is an independent set in M_{X}^{e}.

(2) We show that I_{1} ∪{γ} is independent in M_{X}^{e}, where I and γ satisfy conditions in (2). On the contrary, suppose I_{1} ∪ {γ} is dependent in M_{X}^{e} and let C′ be a circuit of M_{X}^{e} contained in I_{1}∪{γ}. We have the following cases:

(i) C′ ∈ C_{0} or C_{1}. Then C′ ⊆ I_{1} and we know C′ is a circuit or contains a circuit of M. This shows that I_{1} is dependent in M, a contradiction.

(ii) C′ ∈ C_{2}. Then C′ = C ∪ {a}, where C is a cocircuit of M. But then C ⊆ I_{1}, a contradiction.

(iii) C′ ∈ C_{3}. Then C′ = C_{1} ∪ {e, γ} or C′ = (C_{2} \ {e}) ∪ {γ} or C′ = (C_{3} \ {e}) ∪ {a, γ}, where C_{1}, C_{2}, C_{3} are circuits in M and C_{1}, C_{2} and C_{3}\{e} each contain an odd number of elements of X. Consequently, C_{1} ∪ {e, γ} ⊆ I_{1} ∪ {γ} implies that C_{1} ⊆ I_{1}. (C_{2} \ {e}) ∪ {γ} ⊆ I_{1} ∪ {γ} implies C_{2} \{e} ⊆ I_{1}; and (C_{3} \{e})∪{a, γ} ⊆ I_{1} ∪{γ} implies C_{3} \{e} ⊆ I_{1}, contradictions to hypotheses in (2).

(3) Let I_{1} be an independent set in M containing e. We show that (I_{1} \ {e}) ∪ {a, γ} is independent in M_{X}^{e}. On the contrary, suppose (I_{1} \ {e}) ∪ {a, γ} is dependent in M_{X}^{e}. By similar argument as in (2), we get contradictions.

(4) Let C_{1}, C_{2}, … and C_{m} be circuits in M, where each C_{i} contains an odd number of elements of X and C_{i} ∩C_{j} ≠ ϕ for i ≠ j, i, j = 1, 2, …, m. Clearly each C_{i} is independent in M_{X}^{e} and I_{1} = ∪_{i=1}^{m}C_{i} is independent in M_{X}^{e}. Further, γ ∉ ∪_{i=1}^{m}C_{i} and by hypothesis, I = (∪_{i=1}^{m}C_{i})∪{γ} contains no circuit of C_{0} and I ∪ {e} contains no circuit of M other than C_{i} for i = 1, 2, …, m. Therefore, I is a independent set in M_{X}^{e}.

Conversely, let I ⊆ S ∪ {a, γ} be an independent set in M_{X}^{e}. We have the following cases:

(I) Let I ∩ {a, γ} = ϕ. Then I ⊆ S and we have two subcases:

(i) I be independent in M. Then I_{1} = I.

(ii) I be dependent set in M. Let C_{1}, C_{2}, …, C_{m} be the circuits of M, contained in I. Then each C_{i} must contain an odd number of elements of X and C_{i} ∩ C_{j} ≠ ϕ for i ≠ j. If I − (C_{1} ∪ C_{2} ∪ … ∪ C_{m}) = ϕ, then I = C_{1} ∪ C_{2} ∪ … ∪ C_{m} is independent in M_{X}^{e} such that I does not contain a member of C_{0} and I ∪ {e} does not contain any circuit of M other than C_{i} for i = 1, 2, …, m. Thus, I is of type (4), where J = ϕ. If I − (C_{1} ∪ C_{2} ∪ … ∪ C_{m}) ≠ ϕ then I = (C_{1} ∪ C_{2} ∪ … ∪ C_{m}) ∪ Y, where Y ⊆ S ∪ {a, γ}, Y ∩ {a, γ} = ϕ, so Y ⊆ S. But Y does not contain a circuit of M with even number of elements of X, and also Y does not contain any C_{i} for i = 1, 2, …, m, thus Y = ϕ; a contradiction.

(II) Suppose I ∩ {a, γ} ≠ ϕ. We have the following cases:

(i) a ∈ I and γ ∉ I. Then I −{a} is independent in M, if I −{a} = I_{1}, then I = I_{1} ∪ {a}.

(ii) Let a ∉ I and γ ∈ I. We show that I − {γ} is independent in M. On the contrary, suppose I − {γ} contains a circuit say C of M. Then C ⊆ (I − {γ}) ∪ {e} and (C \ {e}) ∪ {γ} ⊆ I. But (C \ {e}) ∪ {γ} is a circuit of M_{X}^{e} contained in I, a contradiction. So, if I − {γ} = I_{1} then I = I_{1} ∪ {γ}. Now, suppose I − {γ} contains more than one circuit of M, say C_{1}, C_{2}, …, C_{m}, where each C_{i} contains an odd number of elements of X and C_{i} ∩ C_{j} ≠ ϕ for i ≠ j, i, j = 1, 2, …, m. Thus C_{1} ∪C_{2} ∪…∪C_{m} ⊆ I −{γ} and ∪_{i=1}^{m}C_{i} ⊆ (I −{γ})∪{e}. Consequently, ((∪_{i=1}^{m}C_{i}) \ {e}) ∪ {γ} ⊆ I. For 1 ≤ j ≤ m, (C_{j} \ {e}) ∪ {γ} is a circuit of M_{X}^{e}, contained in ((∪_{i=1}^{m}C_{i}) \ {e}) ∪ {γ}, that is, in I; a contradiction. So I = (∪_{i=1}^{m}C_{i}) ∪ {γ} is a independent set in M_{X}^{e}. Moreover, I ∪ {e} contains no circuit of M other than C_{i}, i = 1, 2, …, m. Thus I is of type (4), where j = {γ}.

(iii) Let a, γ ∈ I. Then we show that I − {a, γ} is independent in M. On the contrary, suppose I − {a, γ} contains a circuit say C of M. Thus C ⊆ (I − {a, γ}) ∪ {e} and (C \ {e}) ∪ {a, γ} ⊆ I. But (C \ {e}) ∪ {a, γ} is a circuit of M_{X}^{e}, where C contains an odd number of elements of X. If C contains an even number of elements of X, then C ⊆ I; a contradiction. We conclude that I_{1} = (I | {a, γ}) ∪ {e} is independent in M and I = (I_{1} \ {e}) ∪ {a, γ}. I is of type (3). This completes the proof of the theorem. □

3. Bases in M_{X}^{e}

In the next theorem, we characterize the bases of the matroid M_{X}^{e} in terms of the bases of M. Theorem 3.1. Let B be a collection of bases of M. A subset B′ of S ∪ {a, γ} is a base of M_{X}^{e} if and only if one of the following conditions hold:

(1) B′ = B ∪ {a}

(2) B′ = B ∪ {γ}, where B ∈ B and no circuit C of M containing e contains an odd number of elements of X such that C \ {e} ⊆ B.

(3) B′ = (B\{e})∪{a, γ}, where B ∈ B, no circuit C of M containing e contains an odd number of elements of X such that C \{e} ⊆ B.

(4) B′ = B ∪ {z}, where B ∈ B, z ∈ S − B and the fundamental circuit of M contained in B ∪ {z} contains an odd number of elements of X.

Proof. (1) Let B be a base of M. Then B is independent in M and, by Lemma 2.2, B is independent in M_{X}^{e}. Further, by Theorem 2.4, B ∪ {a} is independent in M_{X}^{e}. Then

r′(B ∪ {a}) = |B ∪ {a}| = |B| + 1 = r(M) + 1 = r′(M_{X}^{e}).

Thus, B′ = B ∪ {a} is a base of M_{X}^{e}.

(2) Let B ∪ {γ} satisfies the conditions in (2). We show that B ∪ {γ} is independent in M_{X}^{e}. On the contrary, suppose B ∪ {γ} is dependent in M_{X}^{e} and C′ is a circuit of M_{X}^{e} contained in B ∪ {γ}. If C′ ∈ C_{0} or C_{1}, then C′ ⊆ B and this leads to a contradiction. If C′ = C ∪ {a}, where C is a circuit in M and a ∉ C, then C ∪ {a} ⊆ B ∪ {γ} implies C ∪ {a} ⊆ B and again C ⊆ B; a contradiction. If C′ ∈ C_{2}, then C′ = C_{1} ∪ {e, γ}, C′ = (C_{2} \ {e}) ∪ {γ} or C′ = (C_{3} \ {e}) ∪ {a, γ}. If C_{1} ∪ {e, γ} ⊆ B ∪ {γ}, then C_{1} ∪ {e} ⊆ B, that is, C_{1} ⊆ B. If (C_{2} \ {e}) ∪ {γ} ⊆ B ∪ {γ}, then C_{2} \ {e} ⊆ B, that is, C_{2} ⊆ B. If (C_{3} \ {e}) ∪ {a, γ} ⊆ B ∪ {γ}, then (C_{3} \ {e}) ∪ {a} ⊆ B or C_{3} ⊆ {e}, contradictions to hypothesis in (2). Further,

r′(B ∪ {γ}) = | B ∪ {γ} | = |B| + 1 = r(M) + 1 = r′(M_{X}^{e}).

This shows that B ∪ {γ} is a base of M_{X}^{e}.

(3) Let (B\{e})∪{a, γ} satisfies the conditions in (3). By the argument similar to one as given above, we show that it is a independent subset of M_{X}^{e}. Moreover,

r′(B \ {e}) ∪ {a, γ} = | (B \ {e}) ∪ {a, γ} | = | B | + 1
= r(M) + 1 = r′(M_{X}^{e}).

Thus, (B \ {e}) ∪ {a, γ} is a base of M_{X}^{e}.

(4) Let B ∪ {z}, where z ∈ S − B, satisfies the condition given in (4). By Theorem 4.2.7, B ∪ {z} is independent in M_{X}^{e} and so

r′(B ∪ {z}) = r′(M_{X}^{e}).

Therefore B ∪ {z} is a base for M_{X}^{e}.

Conversely, let B′ be a base for M_{X}^{e}. We consider the following cases:

(I) Let a ∈ B′ and γ ∉ B′. Then B′ − {a} is independent in M_{X}^{e}. We show that B′ − {a} is also independent in M. On the contrary, suppose B′ − {a} contains a circuit C of M. We have two subcases.

(i) C contains an even number of elements of X. Then C ⊆ B′; a contradiction.

(ii) C contains an odd number of elements of X. Then C ⊆ B′ − {a} and C ∪ {a} ⊆ B′; a contradiction, because C ∪ {a} is a circuit of M_{X}^{e}. Next,

r(B′ − {a}) = | B′ − {a} | = | B′ | − 1 = r′(M_{X}^{e}) − 1 = r(M).

Therefore, B′ − {a} is a base for M.

(II) Let a ∉ B′ and γ ∈ B′. We show that B′ − {γ} is a base for M. Firstly, we prove that B′ − {γ} is independent in M. On the contrary, suppose B′ − {γ} is dependent in M. Let C be a circuit of M, contained in B′ − {γ}. We have two subcases:

(i) Let C contains an even number of elements of X. Then C is a circuit of M_{X}^{e} and C ⊆ B′ − {γ}. But C ⊆ B′, is a contradiction.

(ii) Let C contains an odd number of elements of X. Then C ⊆ B′ − {γ} and so C \{e} ⊆ B′−{γ}. This implies that (C \{e})∪{γ} ⊆ B′ which is a contradiction, since (C \ {e}) ∪ {γ} is a circuit of M_{X}^{e}. Secondly, B′ − {γ} is maximal independent in M, follows from the fact that r(B′ − {γ}) = r(M).

(III) Let a, γ ∈ B′. We show that (B′ \ {a, γ}) ∪ {e} is a base for M. Clearly e ∉ B′, for e ∈ B′ implies that {e, a, γ} ⊆ B′ and this is a contradiction.

Firstly, we show that (B′ − {a, γ}) ∪ {e} is independent in M. On the contrary, suppose it is dependent in M and let C be a circuit of M contained in (B′ \ {a, γ}) ∪ {e}. We have two subcases:

(i) C contains an even number of elements of X. Then C is a circuit of M_{X}^{e} and C ⊆ (B′ \ {a, γ}) ∪ {e}. Thus (C \ {e}) ∪ {a, γ} ⊆ B′; a contradiction because (C \ {e}) ∪ {a, γ} is a circuit of M_{X}^{e}.

(ii) C contains an odd number of elements of X and C ⊆ (B′\{a, γ})∪ {e}. Hence (C \ {e}) ∪ {γ} ⊆ B′. But (C \ {e}) ∪ {γ} is a circuit of M_{X}^{e}, so we get a contradiction. Further, (B′ \ {a, γ}) ∪ {e} is maximal independent in M, since

r((B′ \ {a, γ}) ∪ {e}) = | (B′ \ {a, γ}) ∪ {e}|
= | B′ | − 1 = r′(M_{X}^{e}) − 1 = r(M).

(IV) Let a, γ ∉ B′. Then B′ ⊆ S and B′ is not independent in M since r′(B′) = r′(M_{X}^{e}) = r(M) + 1. Thus B′ is dependent in M. So there is a circuit C of M contained in B′. If C contains an even number of elements of X, then C is a circuit of M_{X}^{e} and we get a contradiction. So C must contain an odd number of elements of X and suppose x_{i} be an element of X contained in C. Then B = B′ − {x_{i}} is a base of M. □

4. Rank Function of M_{X}^{e}

Lemma 4.1. Let M be a binary matroid on S and M_{X}^{e} be a es-splitting of M with ground set S ∪ {a, γ}. Let r and r′ be the rank functions of M and M_{X}^{e}, respectively. Then for Z ⊆ S the following properties hold:

(1) r′(Z ∪ {a}) = r(Z) + 1

(2) r′(Z ∪ \{a, γ\}) = \{ \begin{matrix}r(Z) + 1 & if & e ∈ Z \\ r(Z) + 2 & if & e ∉ Z \end{matrix}

Proof. (1) Let T be a base for A in M. Then r(Z) = | T |. We show that T ∪ {a} is a base for Z ∪ {a} in M_{X}^{e}. On the contrary, suppose T ∪ {a} is dependent in M_{X}^{e} and C is circuit of M_{X}^{e} contained in T ∪ {a}. We consider the following cases:

(i) C ∈ C_{0} or C_{1}. Then C ⊆ T ∪{a} and hence C ⊆ T; a contradiction. (ii) C ∈ C_{2}. Then C = C_{1} ∪ {a}, where C_{1} is a circuit in M. Conse-

quently C_{1} ⊆ T gives a contradiction.

(iii) Let C ∈ C_{3}. Then there is a circuit of M, say C_{1} with C_{1} ⊆ T, a contradiction.

Now, we prove that T ∪ {a} is a maximal independent set in M_{X}^{e}. On the contrary, suppose T ∪{a}∪{z} is maximal independent in M_{X}^{e}, where z ∈ Z − (T ∪ {a}). Then T ∪ {z} ∪ {a} ⊆ Z ∪ {a}. Thus T ∪ {z} ⊆ Z, a contradiction. Now,

r′(Z ∪ {a}) = | T ∪ {a} | = | T | + 1 = r(Z) + 1.

By the same argument as above, we can show that

r′(Z ∪ {γ}) = r(Z) + 1.

(2) Let T be a base for Z in M. Then r(Z) = | T |. We have the following two cases:

(I) Let e ∈ T. Then we claim that (T \ {e}) ∪ {a, γ} is a base for Z ∪ {a, γ} in M_{X}^{e}. On the contrary, suppose that it is dependent set of M_{X}^{e} and contains a circuit C of M_{X}^{e}. We have the following subcases:

(i) Let C ∈ C_{0} or C_{1}. Then C ⊆ (T \ {e}) ∪ {a, γ} implies that C ⊆ T \ {e} ⊆ T; a contradiction.

(ii) Let C ∈ C_{2} and C = C_{1} ∪ {a}, where C_{1} is a circuit of M. Then C_{1} ∪ {a} ⊆ (T \ {e}) ∪ {a, γ} and C_{1} ⊆ T \ {e} ⊆ T; a contradiction.

(iii) Let C ∈ C_{3} and C = (C_{1} \ e) ∪ {a, γ}, e ∈ C_{1}, where C_{1} is a circuit in M. Clearly C_{1} ⊆ T again; a contradiction. Now, we show that (T \ {e}) ∪ {a, γ} is maximal independent in M_{X}^{e}. On the contrary, suppose (T \ {e}) ∪ {a, γ} ∪ {z} for z ∈ Z is maximal. Then (T \ {e}) ∪ {z} ⊆ Z\{e} ⊆ T ∪{z} ⊆ Z. Consequently, T ∪{z} ⊆ Z; a contradiction. If e ∈ T, then (T \ {e}) ∪ {a, γ} is a base for Z ∪ {a, γ} in M_{X}^{e} and hence

r′(Z ∪ {a, γ}) = | T \ {e} | + | {e, γ} | = | T | + 1 = r(Z) + 1.

(II) Let e ∉ T. Then we show that T ∪{a, γ} is a base for Z ∪{a, γ} in M_{X}^{e}. We prove that T ∪ {a, γ} is maximal independent in M_{X}^{e}. On the contrary, suppose it is dependent in M_{X}^{e}. By the same argument as in case (I), we obtain a contradiction. Thus T ∪ {a, γ} is base of Z ∪ {a, γ}. Finally,

r′(Z ∪ {a, γ}) = | T ∪ {a, γ} | = | T | + | {a, γ} |
= | T | + 2 = r(Z) + 2.

This completes the proof. □

Lemma 4.2. If Z ⊆ S, then

r′(Z) = \{ \begin{matrix}r(Z) + 1 & if Z contains a circuit of M, containing \\ & an odd number of elements of X; \\ r(Z) & otherwise. \end{matrix}

Proof. Let Z ⊆ S. We have the following cases:

(1) Suppose Z does not contain any circuit of M. Then Z is independent in M, and by Lemma 2.2, it is independent in M_{X}^{e} and hence r′(Z) = | Z | = r(Z).

(2) Suppose Z does not contain a circuit of M containing an odd number of elements of X. Suppose Z contains a circuit say C, containing an even number of elements of X. Then C is a circuit in M_{X}^{e} and Z is dependent in M, as well as in M_{X}^{e}. Consequently, a base of Z in M is also a base of it in M_{X}^{e}. Thus, r′(Z) = r(Z).

(3) Let Z contains a circuit of M, say C containing an odd number of elements of X. For α ∈ C, the set C −{α} is independent in M|Z. Now, we extend C −{α} to a base T of Z. Let T = (C −{α})∪{β_{1}, β_{2}, …, β_{k}}, where β_{i} ∈ Z, i = 1, 2, …, k, is a base of Z in M. Then

r(Z) = | T | = | C | − 1 + k.  (∗)

On the other hand, C is independent in M_{X}^{e} and T′ = C∪{β_{1}, β_{2}, … β_{k}} is independent in M_{X}^{e}. If T′ is not a base of Z in M_{X}^{e}, then T′′ = C ∪ {β_{1}, β_{2}, …, β_{k}, δ} for some δ ∈ Z is independent subset of Z in M_{X}^{e}. Now C ∪ {β_{1}, β_{2}, …, β_{k}} is a dependent subset of Z in M. Let C′ be a circuit of M contained in it. We have the following cases:

(i) C′ contains an even number of elements of X. Then C′ is a circuit of M_{X}^{e} with C′ ⊆ C ∪ {β_{1}, β_{2}, …, β_{k}} a, contradiction.

(ii) C′ contains an odd number of element of X. Consider

CΔC′ = C′_{1} ∪ C′_{2} ∪ … ∪ C′_{m},  (∗∗)

where C′_{i} are circuits of M and C′_{i} ∩ C′_{j} = ϕ, i ≠ j and i, j = 1, 2, …, m. If some C′_{i} contains an even number of elements of X, then it leads to a contradiction. If not, consider the circuits C′_{j}, C′_{k} from (**). Then either C′_{j} ∪ C′_{k} is a circuit or a subset of it, is a circuit of M_{X}^{e} contained in T′′. We conclude that T′ must be a maximal independent subset of Z in M_{X}^{e}. Now,

r′(Z) = | T′ | = | C ∪ {β_{1}, β_{2}, …, β_{k}}| = |C| + k.  (∗ ∗ ∗)

From (∗) and (∗ ∗ ∗), we deduce that r′(Z) = r(Z) + 1. This completes the proof. □

Corollary 4.3. Let M = (S, r) and M_{X}^{e} = (S ∪ {a, γ}, r′) be matroids with usual meaning. Let J = {a, γ}. If Y ⊆ S ∪ {a, γ}, then

r′(Y) = \{ \begin{matrix}r(Y) + 1, & if | Y ∩ J | = 0 and Y contains a circuit \\ & of M containing an odd number \\ & of elements of X; \\ r(Y), & if | Y ∩ J | = 0 and Y does not contain \\ & any circuit of M containing odd \\ & number of elements of X; \\ r(Y ∩ S) + 1, & if | Y ∩ J | = 1 or | Y ∩ J | = 2, e ∈ Y; \\ & and \\ r(Y ∩ S) + 2, & if | Y ∩ J | = 2 and e ∉ Y \end{matrix}

The proof follows from Lemmas 4.1 and 4.2.

Corollary 4.4.4. Let M = (S, r) be a binary matroid. Let r_{1}, r_{2}, r_{3} be the rank functions of the matroids M_{X}, M′_{X} and M_{X}^{e}, respectively. Then r_{3}(Y) = r_{2}(Y) = r_{1}(Y) for Y ⊆ S. Proof. It is known [3] that for a matroid M on S with T ⊆ S and X ⊆ S − T,

r_{M\T} (X) = r_{M}(X),  (∗)

A CHARACTERIZATION OF THE BASES 15

where r_{M} is a rank function of M. We have

M_{X}^{e} \ {γ} = M′_{X} and M′_{X} \ {a} = M_{X}.

Thus from (*), it follows that, r_{3}(Y) = r_{2}(Y) and r_{2}(Y) = r_{1}(Y) for Y ⊆ S. □

References

[1] Azanchiler H., Extension of line-splitting operation from graphs to binary matroids, Lobachevskii Journal of Mathematics, (24) (2006), 3-12.

[2] Fleischner H., Eulerian Graphs and Related Topics, Part 1, Vol. 1, North Holland, Amsterdam (1990).

[3] Oxley J. G., Matroid Theory, Oxford University Press, New York, (1992).

[4] Raghunathan T. T., Shikare M. M. and Waphare B. N., Splitting in a binary matroid, Discrete Mathematics, 184 (1997), 261-271.

[5] Shikare M. M., Azadi G., Determination of the bases of a splitting matroid, European Journal of Combinatorics, 24 (2003), 45-52.

[6] Shikare, M. M., Azadi G. and Waphare B. N., Generalized splitting operation and its applications to binary matroids (preprint).

[7] Shikare, M. M. and Azadi, G., Element splitting operation for binary matroids (preprint).

[8] Slater P. J., Soldering and point splitting, J. Combinatorial Theory, 24(3) (1978), 338-343.

Department of Mathematics, University of Urmia, Urmia - 57135 (Iran) E-mail address: azanchiler@yahoo.com

Received March 28, 2007