# Γ-Extension of Binary Matroids

Authors: Habib Azanchiler
Journal: ISRN Discrete Mathematics
 (2011)

---

## Abstract

We extend the notion of a point-addition operation from graphs to binary matroids. This operation can be expressed in terms of element-addition operation and splitting operation. We consider a special case of this construction and study its properties. We call the resulting matroid of this special case a Γ-extension of the given matroid. We characterize circuits and bases of the resulting matroids and explore the effect of this operation on the connectivity of the matroids.


---

## Body

## 1. Introduction

Slater [1] defined few operations for graphs which preserve connectedness of graphs. One such operation is a point-addition (vertex-addition) operation. This operation is defined in the following way. Let G be a graph and V(G) be the set of vertices of G. Let H be the graph obtained from G by adding a new vertex v adjacent to vertices v1,v2,…,vn of G. The graph H is said to be obtained from G by point-addition operation. Letting X={v1,v2,…,vn}, for convenience, we denote the graph H by GX. Thus, V(GX)=V(G)∪{v} and E(GX)=E(G)∪{vv1,vv2,…,vvn}.Point-addition operation has several applications in graph theory. For example, Slater classifiedn-connected graphs using point-addition operation along with some other operations [2].If|V(G)|=n, then the new vertex v can be joined to at most n vertices of the graph. That means, we can add at most n edges in the original graph.Definition 1.1.
LetM=M[A] be a binary matroid of rank r on a set S. Let A′′ be the matrix obtained from A by the following way.(1)
Adjoink columns to A(k≤r) with labels say γ1,γ2,…,γk. Let the resulting matrix be denoted by A′.(2)
Adjoin a new row toA′ with entries zero except in the columns corresponding to γ1,γ2,…,γk, where it takes the value 1.LetM′′ be the vector matroid of the matrix A′′. We say that M′′ is obtained from M by the point-addition operation. We call the matroid M′′ point-addition matroid or Γ-extension of M. Let us denote by Γ, the set of columns γ1,γ2,…,γk which are adjoined to A in the first step. That is, Γ={γ1,γ2,…,γk}. Then, second step consists of splitting the matroid M[A′] with respect to the set Γ (see [3, 4]).In fact, the matroidM′′ is obtained by elements addition and generalized splitting operation [5]. As an immediate consequence of the definition, we have the following result.Letvi and vj be two vertices of G. Then, the addition of an edge vivj, results in the smallest supergraph of G containing edge vivj.Proposition 1.2.
LetM=M(G) be a cycle matroid of rank r. Let G′ be the graph obtained from G by adding adjacent edges γ1,γ2,…,γn(n≤r) to G. Let Γ={γ1,γ2,…,γn}. Then, the point-addition matroid M′′ is graphic and M′′=M(GΓ′).Proof.
LetA be representation matrix of M over GF(2). Let the matrix A′ be obtained from A by adding column vectors say, γ1,γ2,…,γn. Suppose that A′′ is obtained from A′ by adding a new row where entries are zero, except in the columns corresponding to γ1,γ2,…,γn, where it takes the value 1. Thus M′′=M[A′′] is a binary matroid with ground set E(G)∪Γ. Since γ1,γ2,…,γn are adjacent edges in G′, the splitting of M(G′) with respect to Γ is graphic (see [5]), and we have M(G′)Γ=M(GΓ′), where GΓ′ is the graph obtained from G by splitting operation with respect to Γ. It follows that M′′=[M(G)]′′=M(GΓ′).We assume that the reader is familiar with elementary notions in matroid theory, including minors, binary, and connectivity. For an excellent introduction to the subject, read Oxley [6].


## 2.Γ-Extension of a Binary Matroid

If a matroidM is obtained from a matroid N by adding a nonempty subset T of S(N), then N is called an extension of M. In particular, if |T|=1, then N is a single-element extension of M (see [6]). Another term, that is sometimes used instead of single-element extension, is addition (see [7]).Now we consider a special case of the operation that is introduced in the first section.Definition 2.1.
LetM=M[A] be a binary matroid of rank r on a set S, and let A=[Ir∣J] be the standard representation of M over GF(2). Let B be a base of M, and let X={ei1,ei2,…,eim} be a subset of B. We obtain the matrix AX by the following way.(1)
Obtain a matrixA1 from A by adjoining m(m≤r) columns say γi1,γi2,…,γim to A, parallel to ei1,ei2,…,eim, respectively.(2)
Split the matrixA1 with respect to the set Γ, where Γ={γi1,γi2,…,γim}. Denote the resulting matrix by AX.LetMX be the vector matroid of the matrix AX. We say that MX is Γ-extension of M. Note that MX is a binary matroid with ground set S∪Γ, where S∩Γ=ϕ, and |X|=|Γ|. The transition from M to MX is called Γ-extension operation on M. In particular, if |X|=ℓ, it is called ℓ-Γ-extension operation, and, for |X|=1, we call it single-Γ-extension operation.The next example illustrates this construction for the dual of Fano matroid.Example 2.2.
LetM=F7* be the dual of the Fano matroid F7, and let S={1,2,3,4,5,6,7} be the ground set of M. The matrix A that represents M over GF(2) is given by. 							(2.1)1234567A=[1000110010001100101010001111].Consider the setX={1,3,4} contained in the base of M. Then, the corresponding matrix AX is given by
(2.2)1234567γ1γ3γ4AX=[10001101000100011000001010101000011110010000000111].The vector matroid ofAX is the matroid (F7*)X.Corollary 2.3.
LetM=M[A] be a binary matroid on S. Let X be a subset of a base of M, and MX be the Γ-extension of M on the set S∩Γ. Then, MX∖Γ=M, that is, MX is an extension of M.Corollary 2.4.
Letr and r′ be the rank functions of the matroids M and MX, respectively. Then r′(MX)=r(M)+1.With the help of Lemma2.5, we characterize the circuits of the matroid MX.Lemma 2.5.
(1) Every circuit ofM is a circuit of MX.
(2) Every circuit ofMX contains at least one element of S.
(3) Every circuit ofMX contains even number of elements of Γ.The proof follows from the construction of the matrixAX.Remark 2.6.
LetMX be a single-Γ-extension of M (i.e., |X|=1). Then every circuit of MX is a circuit of M and vice versa. In fact, the added element γ is a coloop in the resulting matroid.Theorem 2.7.
LetM be a binary matroid on S with representation matrix A=[Ir∣E] over GF(2) and X be a subset of a base of M. Then, a subset Z of S∪Γ is a circuit of MX if and only if one of the following conditions hold:(1)
Z={ei,ej,γi,γj}, where i≠j,γi,γj∈Γ and ei,ej∈X for 1≤i,j≤r,(2)
Z=J∪D, where J⊆Γ, |J| is an even integer and ϕ≠D⊆S is such that D∪XJ is a circuit in M, where XJ={ei∈X∣γi∈J}.Proof.
IfZ={ei,ej,γi,γj}, then, by Definition 2.1 of AX, Z is a circuit of MX. Now, let Z=J∪D be as stated in (2). If |J|=0, then J=ϕ,XJ=ϕ, and Z=D is a circuit of M. Suppose that J⊆Γ,J≠ϕ, and XJ∪D is a circuit of M. Then clearly, Z=D∪J is a circuit of MX.
Conversely, letZ⊆S∪Γ be a circuit of MX, we have two cases:(I)
Z∩Γ=ϕ. Then J=ϕ,XJ=ϕ. Thus, Z=D is a circuit in M and the condition (2) in the result holds.(II)
LetZ∩Γ≠ϕ, and suppose that Z∩Γ=J. We have two subcases:
(i)
Z∩X≠ϕ. Then, Z∩X={ei,ej}=D=XJ and J={γi,γj}. Thus, Z={ei,ej,γi,γj} and condition (1) in the result holds.(ii)
Z∩X=ϕ. Take Z∩S=D. Then D∪XJ is a circuit of M and D∪J is a circuit of MX. Thus, Z=D∪J, and the condition (2) in the result holds.We characterize the independent sets ofMX in terms of independent sets of M. Firstly, we have the following lemma.Lemma 2.8.
(1) Every independent set ofM is independent in MX.
(2) Every subset ofΓ is independent in MX.The proof is straightforward.Remark 2.9.
LetMX be a single-Γ-extension of M. Then, every independent set in MX is also independent in M and vice versa.Theorem 2.10.
LetM be a binary matroid on S and MX be the Γ-extension matroid of M with respect to X. Let ℐ be a collection of independent sets of M. Then, a subset I of S∪Γ is an independent set of MX if and only if one of the following conditions hold:(1)
I=I1∪{γ}, where γ∈Γ and I1∈ℐ.(2)
I=I1∪J, where J⊆Γ, I1∈ℐ and I1∪XJ contains no circuit of M.Proof.
IfI1∈ℐ, then clearly I1∪{γ} for γ∈Γ is an independent set in MX. Now, suppose that I1∪XJ contains no circuit of M. On the contrary, suppose that I1∪J contains a circuit say C′ of MX. Then C′∖J⊆I1 and (C′∖J)∪XJ⊆I1∪XJ. But (C′∖J)∪XJ is a circuit of M and is contained in I1∪XJ, a contradiction.
Conversely, letI be an independent set in MX and I⊆S∪Γ. We have two cases.(I)
LetI∩Γ=ϕ. Then I⊆S and I is independent in M.(II)
LetI∩Γ≠ϕ, and let I∩Γ=J. Then J⊆Γ and J⊆I.
We prove thatI-J⊆S is an independent set in M. On the contrary, suppose that I-J contains a circuit of M, say C, then C⊆I-J and C⊆I gives a contradiction.
LettingI-J=I1, we have I=I1∪J. We claim that I1∪XJ does not contain any circuit of M. If I1∪XJ contains a circuit of M, say C′, then C∖XJ⊆I1. Further, (C∖XJ)∪J⊆I1∪J, and thus (C∖XJ)∪J⊆I leads to a contradiction as (C∖XJ)∪J is a circuit of MX. This completes the proof of the theorem.Corollary 2.11.
Letℐ and ℐX denote the collection of independent sets of M and MX, respectively. If |X|=1, then ℐX={I∪{γ}∣I∈ℐ,γ∈Γ}.Corollary 2.12.
A subsetI of S is independent in M if and only if I∪{γ} for γ∈Γ is independent in MX.Corollary 2.13.
Letr and r′ be the rank functions of M and MX, respectively. Then r′(Z∪{γ})=r(Z)+1 for Z⊆S.In the next theorem, we characterize the bases of the matroidMX in terms of the bases of M.Lemma 2.14.
LetZ⊆S, then Z is an independent set in MX if and only if Z is an independent set in M.The proof is straightforward.Corollary 2.15.
LetZ be a subset of S. Then r′(Z)=r(Z) where r′ and r are rank functions of MX and M, respectively.Theorem 2.16.
A subsetB′ of S∪Γ is a base for MX if and only if B′=(B∖D)∪J, where ϕ≠J⊆Γ,D⊂B,|D|=|J|-1 and (B∖D)∪XJ contains no circuit of M.Proof.
LetB be a base for M. Then B is an independent set in M, and so B∖D is independent in M. Let B∖D=I1. Then, by Theorem 2.10, I1∪J, where J⊆Γ,|D|=|J|-1 and (B∖D)∪XJ contains no circuit of M and hence is independent in MX. Moreover, r′((B∖D)∪J)=|(B∖D)∪J|=|B|-|D|+|J|=|B|+1=r′(MX).
We conclude thatB′=(B∖D)∪J is a base for MX.
Conversely, letB′⊆S∪Γ be a base for MX. Firstly, we show that B′∩Γ≠ϕ. On the contrary, suppose that B′∩Γ=ϕ. Then B′⊆S and is independent in MX. So by Lemma 2.14, B′ is independent in M. Also by Corollary 2.15,
(2.3)r′(B′)=r(B)=|B′|=r(M)+1.
This shows that B′⊆S and r(B′)>r(M); a contradiction.
Now, letB′∩Γ=J. Then B′-J⊆S is independent in MX as well as in M. It can be extended to form the base of M. Let D⊆S-(B′-J) be such that (B′-J)∪D=B is a base for M. Then B′=(B∖D)∪J. We claim that |D|=|J|-1. Now,
(2.4)|B|=|(B′-J)∪D|=|B′|-|J|+|D|=r(M)+1-|J|+|D|.
Since |B|=r(M), we conclude that 1-|J|+|D|=0, that is, |D|=|J|-1. Finally, we show that (B∖D)∪XJ contains no circuit of M. On the contrary, suppose that (B∖D)∪XJ contains a circuit, say C of M. Then C∖XJ⊆B∖D and (C∖XJ)∪J⊆(B∖D)∪J. Thus, (C∖XJ)∪J⊆B′ leads to a contradiction. This completes the proof of theorem.Corollary 2.17.
Every base ofMX contains at least one element of Γ.


## 3. Connectivity ofMX

LetM be a binary matroid on a set S and A be the representation matrix of M over GF(2). If M is bridgeless, then Γ-extension of M with respect to a singleton subset X of B yields a disconnected matroid.Lemma 3.1.
Letei∈S be a coloop in a matroid M and ei∉X. Then ei is a coloop in MX.The proof is straightforward.Corollary 3.2.
Suppose that no element ofS-X is a coloop of M. Then MX has no coloops.Theorem 3.3.
Let|X|≥2. If M is connected matroid, then, so is MX.Proof.
Assume thatM is connected. We show that for every pair of elements u,v∈S∪Γ there is a circuit of MX containing u and v. We have three cases.(1)
Letu,v∈S. By hypothesis, M is connected. So there is a circuit of M say C, containing u and v. Since C is a circuit in MX, we are through.(2)
Letu,v∈Γ and let u=γi and v=γj. Then the 4-circuit {ei,ej,γi,γj} in MX contains u and v.(3)
Letu∈S and v∈Γ. By assumption |X|≥2. So there is an element say w∈Γ. Let C1 be a circuit of MX containing v and w. By Lemma 2.5, C1 contains at least one element of S, say e. Now u,e∈S, and M is connected, so there is a circuit of M, say C2 which contains u and e. Thus C1∩C2≠ϕ and u∈C1,v∈C2. Then there is a circuit in MX, say C3, such that C3⊆C1∪C2 and u,v∈C3. This completes the proof of the theorem.Remark 3.4.
Converse of the above theorem is not true.Theorem 3.5.
LetMX be a 3-Γ-extension matroid of M and Γ={γi,γj,γk}. If M is a 3-connected matroid on S, then MX is 3-connected.Proof.
On the contrary, suppose thatMX is not 3-connected, then MX has a 1-separated or 2-separated partition. Let (A,B) be a 2-separated partition of S∪Γ. That means, min{|A|,|B|}≥2 and
(*)r′(A)+r′(B)-r′(MX)≤1.
We consider three cases.(i)
LetA=Γ and B=S. By Lemma 2.8, A is independent in MX, so
(3.1)r′(A)=|A|=|Γ|=3.
Also, by Lemma 2.14,
(3.2)r′(B)=r′(S)=r(S)=r(M).
Thus,
(3.3)r′(A)+r′(B)-r′(MX)=3+r(M)-r(M)-1=2.
This is a contradiction to (*).(ii)
LetA={γi,γj} and B=S∪{γk}.By Lemma2.14, r′(B)=r(M)+1. So
(3.4)r′(A)+r′(B)-r′(MX)=2+r(M)+1-r(M)-1=2gives a contradiction to (*).(iii)
LetA=S1∪{γi} and B=S2∪{γj,γk}, where S1,S2⊆S, and S1≠ϕ,S2≠ϕ. Then min{|S1|,|S2|}≥1 and r(S1)+r(S2)-r(M)≤r′(A)-1+r′(B)-1-r′(MX)+1≤0. Moreover,
(3.5)r(S1)+r(S2)≥r(M).
Thus, r(S1)+r(S2)-r(M)=0, and we conclude that (S1,S2) is a 1-separated partition for M.This is a contradiction to the fact thatM is 3-connected. By the same argument, we can show that MX does not have 1-separated partition.In the last theorem, the condition that|X|=3 is necessary. Consider the following example.Example 3.6.
M(K4) is a 3-connected matroid. Let a representation matrix of M(K4) be
(3.6)123456A=[100110010101001011].
Let X⊆B and X={1,2},Γ={γi,γ2}. Then
(3.7)123456γ1γ2AX=[10011010010101010010110000000011].
By row operations on AX, we can show that
(3.8)AX=[I4|1101101101100001].
By [], MX=M[AX] is not 3-connected.If|X|=1, then MX has a coloop, and it is not 3-connected.In general, we state the following result whose proof is immediate.Corollary 3.7.
LetM be a n-connected binary matroid and |X|<n. Then MX is not n-connected.



---

*Source: 629707-2011-11-03.xml*