ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.784992 J. Algebra Comb. Discrete Appl. 7(3) • 247–258 Received: 14 April 2020 Accepted: 1 May 2020 Journal of Algebra Combinatorics Discrete Structures and Applications Generalization of pinching operation to binary matroids Research Article Vahid Ghorbani, Ghodratollah Azadi, Habib Azanchiler Abstract: In this paper, we generalize the pinching operation on two edges of graphs to binary matroids and investigate some of its basic properties. For n ≥ 2, the matroid that is obtained from an n-connected matroid by this operation is a k-connected matroid with k ∈ {2,3,4} or is a disconnected matroid. We find conditions to guarantee this k. Moreover, we show that Eulerian binary matroids are char- acterized by this operation and we also provide some interesting applications of this operation. 2010 MSC: 05B35 Keywords: Binary matroid, Connectivity, Pinching, Splitting, Splitting off, Element splitting 1. Introduction The matroid and graph notations and terminology used here will follow [4] and [7]. Let G be a graph and S be a subset of the edge set E(G). We denote by GpS the graph that is obtained from G by adding a new vertex w and replacing any edge uv ∈ S with two edges uw and wv. The transition from G to GpS is called the k-pinching operation [2] where k = |S|. If S is the empty set, then 0-pinching means adding a new single vertex w. If |S| = 1, then applying the pinching operation is equivalent to the subdivision of uv where S = {uv}. If S = E(G), then we have the parallel classes on the new vertex w on GpS such that the sequence of the cardinality of them is equal to the degree sequence of the vertices of G. Applying the pinching operation on graphs is a useful method for solving 2k-edge-connectivity prob- lems for graphs [2]. For example, suppose that G is a 2k-edge-connected graph. Then the graph G′ obtained from G by pinching together any k edges of G is also 2k-edge-connected. Raghunathan, Shikare, and Wapare [5] extended the splitting operation and Azadi [1] extended the splitting off and the element splitting operations from graphs to binary matroids. These operations are defined as follows. Definition 1.1. Let M be a binary matroid on a set E and A be a matrix that represents M over GF(2). Consider two elements x and y of E(M). Let Ax,y be the matrix that is obtained by adjoining an extra Vahid Ghorbani (Corresponding Author), Ghodratollah Azadi, Habib Azanchiler; Department of Mathematics, Urmia University, Iran (email: v.ghorbani@urmia.ac.ir, gh.azadi@urmia.ac.ir, h.azanchiler@urmia.ac.ir) 247 http://orcid.org/0000-0002-7301-6973 http://orcid.org/0000-0002-1807-4732 http://orcid.org/0000-0002-2949-3836 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 row to A whose entries are zero everywhere except in the columns corresponding to x and y where it takes value 1. Let Mx,y be the matroid that represents by the matrix Ax,y. Then the transition from M to Mx,y is called the splitting operation. Definition 1.2. Let M be a binary matroid on a set E and A be a matrix that represents M over GF(2). Consider two elements x and y of E(M). Let A′x,y be the matrix that is obtained by adjoining an extra row to A whose entries are zero everywhere except in the columns corresponding to x and y where it takes value 1 and then adjoining an extra column to the resulting matrix with this column being zero everywhere except in the last row. Let M′x,y be the matroid that represents by the matrix A ′ x,y. Then the transition from M to M′x,y is called the element splitting operation. Definition 1.3. Let M be a binary matroid on a set E and A be a matrix that represents M over GF(2). Consider two elements x and y of E(M). Let Axy be the matrix that is obtained by adjoining an extra column to A which is the sum of the columns corresponding to x and y, and then deleting the two columns corresponding to x and y. Let Mxy be the matroid that represents by the matrix Axy. Then the transition from M to Mxy is called the splitting off operation. Splitting off operation on graphs is defined as follows. Definition 1.4. Let G be a graph. Consider two adjacent non-loop edges x = uw and y = vw. The splitting off a pair (x,y) of edges from a vertex w means that we replace the edges x and y by a new edge α = uv. If u = v then the resulting loop is deleted from the graph. 2. 2-pinching operation in 2-connected graphs Let G be a 2-connected graph with the edge set E(G) and S ⊆ E(G) where S = {x = u1v1,y = u2v2}. To apply the 2-pinching operation, we first delete x and y and add new vertex w. Then we add new edges x′ = u1w, x′′ = wv1, y′ = u2w and y′′ = wv2. When x and y are adjacent, we take v1 = v2 = v. Therefore, x′ = u1w, x′′ = wv, y′ = u2w and y′′ = wv (Figure 1). We denote by Gpxy the graph that is obtained by applying the 2-pinching operation on edges x and y. Note that we can retrieve the graph G from Gpxy by splitting off the pair (x ′,x′′) and then splitting off the pair (y′,y′′). Figure 1. 2-pinching operation on {x,z} and {x,y}. Now let G be a 2-connected graph and x,y ∈ E(G). Then G has a cycle Cn of length n containing both x and y. Assume that the cycle Cn has the minimum cardinality among all such cycles. After applying the 2-pinching operation on x and y, the cycle Cn transforms into two cycles C′k+2 and C ′ n−k where k is the length of shortest path Q among endpoints of x and y such that x′′,y′′ ∈ C′k+2 and x ′,y′ ∈ C′n−k. In other words, C ′ k+2 = E(Q)∪{x ′′,y′′} 1 and C′n−k = ( Cn−(E(Q)∪{x,y}) ) ∪{x′,y′}. Note that if k = 0, then x and y are adjacent and Cn transforms to C′2 = {x′′,y′′} and C′n = ( Cn−{x,y} ) ∪{x′,y′}. 1 In this section, for cycle Cn of length n from a graph G, we consider just its edge set 248 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 Theorem 2.1. Let G be a graph and x,y ∈ E(G). Suppose that G has a cycle Cn with a minimum length containing both x and y. Let x′,x′′,y′,y′′,C′k+2 and C ′ n−k be the notations as mentioned above. Moreover, let δ = {C′k+2,C ′ n−k} and C be a subset of edges of G p xy. Then C forms a cycle of G p xy if and only if C ∈ δ or C satisfies one of the following conditions. (i) C is a cycle of G which contains neither x nor y; (ii) C = ( C′−{x} ) ∪{x′,x′′} where C′ is a cycle of G containing x but not y, or C = ( C′′−{y} ) ∪{y′,y′′} where C′′ is a cycle of G containing y but not x; and (iii) C = C1∆C2 where C1 ∈ δ, and C2 is a cycle of type (i) or (ii) such that C1 ∩C2 6= ∅. Proof. It is clear that if C ∈ δ or if C is a cycle of G containing neither x nor y, then C is a cycle of Gpxy. Now suppose that C = ( C′ −{x} ) ∪{x′,x′′} = ( C′ −{u1v1} ) ∪{u1w,v1w} where C′ is a cycle of G containing x but not y and has length k′ + 1, so C′ = v1xu1e1z1...e ′ k′−1zk′−1ek′v1. After applying the pinching operation on x we delete x and add x′ = u1w and x′′ = v1w. Thus (C′ −{x}) ∪{x′,x′′} = u1e1z1...ek′−1zk′−1ek′v1x′′wx′u1. Therefore C is a cycle of Gpxy. Similarly, if C = ( C′′−{y} ) ∪{y′,y′′} = ( C′−{u2v2} ) ∪{u2w,v2w} where C′′ is a cycle of G containing y but not x, then C is a cycle of Gpxy. Now suppose that C1 is a cycle of type (i) or (ii) and C2 ∈ δ such that C1 ∩C2 6= ∅. To show that C1∆C2 is a cycle of Gpxy, we consider the following two possible cases. Figure 2. Internally disjoint paths. Case(1) Let C1 be a cycle of type (i). Assume that C1 has a non-empty intersection with both C′k+2 and C′n−k. Let Q1 and Q2 be the paths such that C1∩C ′ n−k = E(Q1) and C1∩C ′ k+2 = E(Q2). Moreover, let Q3 , Q4 be internally disjoint paths which have the same end vertices as of Q1 and Q2 such that C1 = E(Q1)∪E(Q2)∪E(Q3)∪E(Q4) (See figure 2). Suppose that C′n−k = E(Q1)∪E(Q5)∪E(Q7) and C′k+2 = E(Q2)∪E(Q6)∪E(Q8) where Qi and Qj for i,j ∈{1, 2, 5, 6, 7, 8} are internally disjoint paths. Then clearly C1∆C′n−k and C1∆C ′ k+2 are cycles of G p xy. Similarly, if C1 has a non-empty intersection with exactly one of C′k+2 or C ′ n−k, then C1∆C ′ n−k or C1∆C ′ k+2 is a cycle of G p xy. Case(2) Let C2 = E(Q3)∪E(Q5)∪E(Q6) and C3 = E(Q4)∪E(Q7)∪E(Q8). Clearly, C2 and C3 are cycles of type (ii). It is easy to see that C2∆C′n−k, C2∆C ′ k+2, C3∆C ′ n−k and C3∆C ′ k+2 are cycles of G p xy. Now suppose that x and y are adjacent. Then v1 = v2 = v and C′k+2 = vy ′′wx′′v. An argument similar to one as given above shows that C1∆C′2 and C1∆C ′ n are cycles of G p xy where C1 is a cycle of type (i) or (ii) such that C1 ∩C′n 6= ∅. 249 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 Conversely, let C be a cycle of Gpxy. By the definition of G p xy one can see that x,y /∈ E(Gpxy) and x′,x′′,y′,y′′ /∈ E(G). Let N = {x′,x′′,y′,y′′}. We know that the induced subgraph of N is either the graph (a) or the graph (b) of the following figure. Figure 3. Two possible induced subgraphs of N. It is straightforward to check that if C is a cycle of Gpxy, then C contains a subset N ′ of N with |N′| ∈ {0, 2}. Therefore, every cycle of Gpxy is a cycle of type (i), (ii) or (iii). 3. 2-pinching operation for binary matroids Now, by using Theorem 2.1 we extend the notion of the 2-pinching operation from 2-connected graphs to binary matroids. Let M be a binary matroid and x,y ∈ E(M). We denote by Cp the collection of all the circuits of M which contain both x and y. Choose a member of Cp and denote it by Cxy. Partition Cxy −{x,y} into sets X1 and X2 where X1 or X2 may be empty. We denote such a partition by P = (X1,X2). Clearly, when Cp is empty or |Cxy| = 2, there is no such partition and we say that P is empty. Definition 3.1. Let A be a matrix that represents the matroid M over GF(2). For x,y ∈ E(M), let Cp 6= ∅ and P = (X1,X2) constructed as above. Let APxy be the matrix obtained from A by the following way. (1) Adjoin four extra columns to A with the labels α1,α2,α3 and α4 such that: – The corresponding entries of α1 and x are equal; – α2 is a zero column; – α3, α4 are columns whose entries are 1 or 0 such that sum of the corresponding entries of the corresponding columns of X1 ∪{α1,α3} and X2 ∪{α2,α4} are zero. (2) Delete the two columns corresponding to x and y (3) Adjoin an extra row with this row being zero everywhere except in the columns corresponding to the new elements αk where it takes value 1, for 1 ≤ k ≤ 4. We call a vector matroid obtained in this way a pinching on x and y with respect to P or 2-pinching with respect to P and denoted it by MPxy. Definition 3.2. Let all hypotheses of Definition 3.1 be established except that Cp 2 is an empty set. To build A∅xy from A, carry out all the steps of Definition 3.1 with the following changes. • The corresponding entries of α1 and x are equal; • The corresponding entries of α3 and y are equal; 2 This means x or y or both are cocircuits of M 250 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 • α2 and α4 are zero columns; Remark 3.3. Let x and y be two elements of a matroid M. Note that, when |Cxy| = 2, we can build A∅xy with both Definition 3.1 and Definition 3.2. So throughout this paper, we may assume that Cp 6= ∅ unless in special cases of some proofs. Figure 4. {x=6,y=7} and P=({1},{4}). Example 3.4. Consider the cycle matroid of the graph in Figure 4 with the following matrix A over GF(2) that represents it. A =   1 2 3 4 5 6 7 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1  . Let x = 6 and y = 7. Then Cp = {{2, 6, 7},{1, 4, 6, 7}}. Let Cxy = {1, 4, 6, 7}. Partition Cxy−{x,y} to two sets X1 = {1} and X2 = {4}. So by definition 3.1, after applying the pinching operation on x and y with respect to P1 = ({1},{4}), the matrix A transforms into the following matrix. A P1 xy =   1 2 3 4 5 α1 α2 α3 α4 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1  . One can easily check that the vector matroid of AP1xy is isomorphic to M ∗(K3,3). Hence the 2-pinching operation on a graphic matroid may not yield a graphic matroid. Moreover, M∗(K3,3) is a 3-connected matroid while the original matroid is not. Clearly, if Cxy = {2, 6, 7}, then P2 = ({2},∅) and MP2xy is a graphic matroid. Theorem 3.5. Let M = (E,C) be a binary matroid on the set E together with the collection C of circuits. Let x,y ∈ E(M), and for a given circuit Cxy, let P = (X1, X2) be a partition of Cxy −{x,y}. Suppose that Γ = {α1,α2,α3,α4} such that αi /∈ E(M) for 1 ≤ i ≤ 4. Then MPxy = ( (E −{x,y}) ∪ Γ,CPxy ) with CPxy = C0 ∪C1 ∪ δ ∪C2 ∪C3 is a binary matroid where (i) C0 = { C ∈C : C contains neither x nor y } ; (ii) C1 = {( C−{x} ) ∪{α1,α2} : C ∈C, and C contains x but not y }⋃{( C−{y} ) ∪{α3,α4} : C ∈C, and C contains y but not x } ; (iii) δ = { X1 ∪{α1,α3},X2 ∪{α2,α4} } ; (iv) C2 = { C1∆C2 : C1 ∈C0 ∪C1 and C2 ∈ δ, and if C1 ∈C0, then C1 ∩C2 6= ∅; and there is no circuit C of C0 and C1 such that C ⊆ C1∆C2 } ; and 251 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 (v) C3 = The set of minimal members of { (C −{x,y}) ∪ Γ : x,y ∈ C and C 6= Cxy } . Proof. It is easy to see that every member of CPxy is a circuit in Mpxy. To show that Cpxy is the collection of circuits of a binary matroid on ( E −{x,y}∪ Γ ) , we must show that if X,Y ∈ CPxy, then X * Y and Y*X, and X∆Y contains at least one member of CPxy. So there are fifteen cases to check and checking them is straightforward. Let A be a matrix that represents M over GF(2). Let C ⊆ E(M). Then C is a circuit of M if and only if C is minimal and the mod-2 sum of the columns of A corresponding to C is a zero columns [4]. By using this fact, a consequence of the last theorem is the following partial result. Corollary 3.6. Under the hypotheses of Theorem 3.5, Let A be a matrix that represents M over GF(2), then the collection of minimal dependent sets of vector matroid of the matrix APxy is CPxy. Proof. Depending on how to construct the matrix APxy, the proof is straightforward. Corollary 3.7. Under the hypotheses of Theorem 3.5, Let r(M) and r(MPxy) be the ranks of M and M P xy, respectively. Then r(MPxy) = r(M) + 1. Proof. Suppose that B is a basis of M such that Cxy is a fundamental circuit with respect to B. Then exactly one of the following holds. (i) ( Cxy −{x} ) ⊆ B. Let B1 = (B −{y}) ∪{α3,α4}. Then |B1| = |B| + 1. By Theorem 3.5(iii), C′1 = X1 ∪{α1,α3} and C′2 = X2 ∪{α2,α4} are circuits of MPxy. Clearly, B1 does not contain either C′1 or C′2, nor any member of C0 ∪C1 ∪C2 ∪C3. So B1 is an independent set. Since B1 ∪α1 contains C′1 and B1 ∪α2 contains C′2, the set B1 is a maximal independent set and so B1 is a basis of M P xy. (ii) ( Cxy −{y} ) ⊆ B. Similar to (i) we can see that if B2 = (B −{x}) ∪{α1,α2}, then B2 is a maximal independent set and |B2| = |B| + 1. (iii) Cxy −{z}⊆ B where z /∈{x,y}. Suppose that z ∈ X1 and B3 = ( B−{x,y} ) ∪{α1,α2,α3,α4}. Consider two sets ( X1−{z} ) ∪{α1,α3} and X2 ∪{α2,α4}. Clearly, ( X1 −{z} ) ∪{α1,α3} is an independent set and X2 ∪{α2,α4} is a circuit of MPxy. Hence B3 cannot be a basis of M P xy, but B4 = B3 −{z′} where z′ ∈ ( X2 ∪{α2,α4} ) is a basis of MPxy and |B4| = |B| + 1. By (i),(ii) and (iii), we conclude that r(MPxy) = r(M) + 1. 4. Connectivity of MPxy In this section, by studying the cardinality of some circuits and cocircuits of MPxy, we explore the relationship between connectivity of a given connected binary matroid M and MPxy. Theorem 4.1. Let MPxy be the pinching of a connected binary matroid M. If C1 ∪C3 = ∅, then MPxy is a disconnected matroid. Otherwise, MPxy is a connected matroid. 252 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 Proof. Since M is a connected matroid, for every pair (x,y) of two elements of E(M), there exists a circuit of C(M) containing both x and y. Now assume C1 ∪C3 = ∅. By Theorem 3.5, we conclude that there is no circuit of M which contains x but not y, also there is no circuit of M which contains y but not x. Let P = (X1,X2). Then δ = { C′1 = X1 ∪{α1,α3},C′2 = X2 ∪{α2,α4} } and C2 = { C′1∆C : C ∈ C0, and C ∩ C′1 6= ∅}∪{C′2∆C : C ∈ C0, and C ∩ C′2 6= ∅ } . Hence every member of C2 contains either {α1,α3} or {α2,α4}. Since Cpxy = C0 ∪ δ ∪C2, there is no member of CPxy containing {α1,α2}, {α3,α4}, {α1,α4} and {α2,α3}. Therefore MPxy is a disconnected matroid. Similarly, it can be shown that if C1∪C3 is non-empty, then MPxy is a connected matroid. Definition 4.2. We say that two elements x and y from given matroid M are equivalent and denoted by x ∼ y, if at least one of x and y is a coloop of M or {x,y} is a cocircuit of M. If a matroid M has at least one pair of equivalent elements, then M is a connected or is a disconnected matroid. Our important task of this section is to rely connectivity of obtained matroid by applying the 2- pinching operation on a given n-connected matroid. So we investigate the cocircuits of matroid obtained by this operation. It is well known that all circuits and all cocircuits of an n-connected matroid with at least 2(n− 1) elements have at least n elements [4]. For a given binary matroid M with matrix representation A and two elements x,y ∈ E(M), we denote by R(C∗) and R(C∗p) the cocircuit spaces of A and APxy, respectively. In the following lemmas, we use the fact that the intersection of a circuit and a cocircuit of a binary matroid M has even cardinality [4]. Lemma 4.3. Let MPxy be a pinching of a binary matroid M. Then Γ = E(M P xy) −E(M) is a cocircuit of Mpxy if and only if x is not equivalent to y. Proof. Suppose that MPxy is such a pinching with P = (X1,X2) and Γ = {α1,α2, α3,α4}. Let A be the matrix that represent M over GF(2). Build APxy for MPxy according to Definition 3.1. Since there is a row in the row space of APxy which this row is zero everywhere except in the corresponding entries of Γ, we get Γ ∈R(C∗p). Assume, without loss of generality, that x ∼ y. Then exactly one of the following holds. (i) {x,y} is a cocircuit of M. Then, there is a row in the row space of A such that has the following form [ E(M)−{x,y} x y 0 0 ... 0 ∣∣∣ 1 1 ]. Let δXi be the sum of the corresponding entries of Xi in this row, for i ∈ {1, 2}. Clearly, δX1 = δX2 = 0. Thus, after applying the pinching operation on M, we have the following row in the row space of APxy [ E(M)−{x,y} α1 α2 α3 α4 0 0 ... 0 ∣∣∣ 1 0 1 0 ]. We conclude that {α1,α3} and {α2,α4} are in R(C∗p). By Theorem 3.5, C1 = X1 ∪{α1,α3} and C2 = X2 ∪{α2,α4} are circuits of MPxy and since |Cj ∩{αi}| = 1 for some j ∈ {1, 2} and some i ∈{1, 2, 3, 4}. Hence {α1,α3} and {α2,α4} are minimal and so Γ is not a cocircuit of MPxy. (ii) {x} is a cocircuit of M. Then M is a disconnected matroid and so {α2,α4} is a circuit of M∅xy. We see that in the row space of A∅xy the corresponding entries of α1 and α3 are 1 and 0, respectively and δX1 = δX2 = 0. Therefore {α1} is a cocircuit of MPxy and so Γ is not. 253 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 To complete the proof, we must show that Γ is minimal when x is not equivalent to y. On the contrary, let Z be a proper subset of Γ which is minimal. Clearly, if |Z| = 1 or 3, then there is a circuit in MPxy such that its intersection with Z or Z∆Γ is a singleton set and if |Z| = 2, we get x ∼ y; a contradiction. Hence Γ is a cocircuit of MPxy. For a given matroid M, The girth g(M) is the minimum circuit size of M unless M has no circuits, in which case, g(M) = ∞. The cogirth is the girth of the dual of M. By Lemma 4.3, we conclude that if M is an n-connected matroid with n ≥ 4, then the cogirth of MPxy is 4. Now suppose that the girth of such a matroid M is k and |Cxy| = k. Then clearly, k ≥ n and by Theorem 3.5, there is a matroid MPxy which will decrease the girth of M to w where 2 ≤ w ≤ [ k 2 ] + 1. Note that if g(M) = ∞, for a given matroid M, then g(M∅xy) = 2. Lemma 4.4. Let M be an n-connected binary matroid with n ≥ 4 and |E(M)| ≥ 2(n − 1). Let x,y ∈ E(M) and P = (X1,X2) be a partition of Cxy −{x,y} with Xi 6= ∅ for i ∈{1, 2}. Then (Γ,E(MPxy)−Γ) is a 4-separation of MPxy where Γ = E(M P xy) −E(M). Proof. Suppose that M is an n-connected binary matroid with n ≥ 4 and |E(M)| ≥ 2(n−1). Let MPxy be a pinching of M with respect to partition P with non-empty parts. Then |E(MPxy)| ≥ 2n. Consider the partition (X,Y ) of E(MPxy) with X = Γ and Y = E(M p xy) − Γ where Γ = E(M) −E(MPxy). Clearly, min{|X|, |Y |} = 4. Suppose that r and r′ be the rank functions of M and MPxy, respectively. The set Γ is an independent set and Y ⊂ E(M). By using Theorem 3.7 r′(X) + r′(Y ) −r′(Mpxy) ≤ 4 + r(M) −r′(Mpxy) ≤ 3. Hence, for n ≥ 4, the partition (X,Y ) is a 4-separation of MPxy. The last result says that for every n-connected matroid with n ≥ 4, the maroid MPxy is a k-connected matroid for some k in {2, 3, 4}. Lemma 4.5. Let x and y be two elements of an n-connected binary matroid M, for n ≥ 3, and let MPxy be a pinching of M. Let Z be a cocircuit of MPxy such that Z 6= Γ where Γ = E(MPxy) − E(M). Then |Z| ≥ n. Proof. Assume, without loss of generality, that Z′ is an n-element cocircut of M and P = (X1,X2) is a partition of Cxy−{x,y}. Let A be a matrix that represents M and APxy constructed from A by Definition 3.1. Suppose that δXi, for i ∈ {1, 2} is the sum of the corresponding entries of Xi in the corresponding row of Z′ in row space of A. So δXi ∈{0, 1}. Then exactly one of the following holds. (i) x,y /∈ Z′ and |Z′∩X1| and |Z′∩X2| are even. Then δX1 = δX2 = 0 and therefore all corresponding entries of Γ in the corresponding row in row space of APxy are 0. We conclude that Z ′ is a cocircuit of MPxy. (ii) x,y /∈ Z′ and |Z′∩X1| and |Z′∩X2| are odd. Then δX1 = δX2 = 1 and therefore the corresponding entries of α1 and α2 in APxy are 0 and α3 and α4 are 1. So Z ′ ∪{α3,α4} is a cocircuit of MPxy. Note that there is no cocircuit Z′ of M not containing x and y such that |Z′ ∩ X1| is odd and |Z′ ∩X2| is even or vice versa. Since in this case |Z′ ∩Cxy| is odd; a contradiction (iii) x is in Z′ but y not, then |Z′∩X1| is odd and |Z′∩X2| is even or vice versa. Then (Z′−{x})∪{α1} or (Z′ −{x}) ∪{α1,α3,α4} is a cocircuit of MPxy. (iv) y is in Z′ but x not, then |Z′∩X1| is odd and |Z′∩X2| is even or vice versa. Then (Z′−{y})∪{α3} or (Z′ −{y}) ∪{α4} is a cocircuit of MPxy. 254 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 (v) x,y ∈ Z′ and |Z′∩X1| and |Z′∩X2| are even. Then δX1 = δX2 = 0 and therefore the corresponding entries of α2 and α4 in APxy are 0 and α1 and α3 are 1. So (Z ′−{x,y}) ∪{α1,α3} is a cocircuit of MPxy. (vi) x,y ∈ Z′ and |Z′∩X1| and |Z′∩X2| are odd. Then δX1 = δX2 = 1 and therefore the corresponding entries of α2 and α3 in APxy are 0 and α1 and α4 are 1. So (Z ′−{x,y}) ∪{α1,α4} is a cocircuit of MPxy. Clearly, every cocircuit Z in (i)-(vi) has at least n elements and x is not equivalent to y. By Lemma 4.3 Γ is a cocircuit of MPxy, and if Z ′′∆Γ is a cocircuit of MPxy, then |Z′′| ≥ n. Consider the following proposition [4], which is straightforward consequence of the fact that all circuits and all cocircuits of an n-connected matroid have at least n elements where the ground set of such matroid has at least 2(n− 1) elements. Proposition 4.6. Let (X,Y) be an n-separation of an n-connected matroid and suppose that |X| = n. Then X is either a coindependent circuit or an independent cocircuit. By using this Proposition and the last three lemmas, for a given n-connected matroid with n ≥ 4, we have the following result to determine connectivity of pinching matroid with respect to P . Theorem 4.7. Let M be an n-connected binary matroid with n ≥ 4 and |E(M)| ≥ 2(n−1). Then MPx,y with respect to P = (X1,X2) is a k-connected matroid for k ∈{2, 3, 4}, if min{|X1|, |X2|}≥ k − 2. Proof. Let M be an n-connected binary matroid and let Cxy be an n′-element circuit of M where n′ ≥ n. Assume that P = (X1,X2) with |X1| = n′ −k and |X2| = k − 2. Let X = (X2 ∪{α2,α4}) and Y = E(MPxy)−X and let r and r′ be the rank functions of M and MPxy, respectively. Since X is a circuit of MPxy, so r ′(X) = k − 1. Clearly, r′(Y ) ≤ r′(E(MPxy). Now by these facts, we have r′(X) + r′(Y ) −r′(MPxy) ≤ k − 1. Since min{|X|, |Y |} = k, the partition (X,Y ) is a k-separation of MPxy. To complete the proof, we shall show that, MPxy has no j-separation for j < k. On the contrary, let (X ′,Y ′) be a j-separation of MPxy with |X′| = j. Then, by Proposition 4.6, the set X′ must be a coindependent circuit or independent cocircuit in MPxy, But such circuit or cocircuit by Theorem 3.5 and Lemma 4.5 does not exist; a contradiction. Definition 4.8. Let M be an n-connected binary matroid and x,y ∈ E(M) such that x is not equivalent to y. We say that a collection of some subsets of E(MPxy) is a Pinched set if all its members have at least (n + 1) elements. Note that if we consider C∗(MPxy)−Γ where Γ = E(MPxy)−E(M), then the cardinality of its members can be characterized by Lemma 4.5. Theorem 4.9. Let M be an n-connected binary matroid for n ∈ {2, 3} and x,y ∈ E(M) such that x is not equivalent to y and Cp has at least one member with k-elements where k ≥ 2n and every n- element circuit of M contains exactly one of x and y. Let C∗(MPxy)−Γis a Pinched set. Then MPxy is an (n + 1)-connected matroid. Proof. Suppose that M is an n-connected binary matroid and x,y ∈ E(M). Choose Cxy from Cp with |Cxy| ≥ 2n. Partition Cxy −{x,y} to two sets X1 and X2 with |X1| = n − 1 and |X2| ≥ k − n − 1. Let X = X1 ∪{α1,α2} and Y = E(Mpxy) −X. Then, min{|X|, |Y |} = n + 1. Therefore, By the similar argument in Theorem 4.7, one can easily show that (X,Y ) is a minimal (n + 1)-separation for MPxy. 255 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 5. Applications In this section, we study the relations between the pinching operation and other binary operations such as splitting, the splitting off operation and element splitting. Using these relations, we will extend the notions of subdivision on to edges and special case of vertex identification on two vertices from graphs to binary matroids. Moreover, we shall show that Eulerian binary matroids are characterized in terms of the 2-pinching, splitting and splitting off operations. The next theorem shows the relationship between M and Mpxy by combining the notions of minors, the splitting off and element splitting operation. Theorem 5.1. Let M be a connected binary matroid. Let x,y ∈ E(M) and Γ = {u,v,u′,v′} such that Γ /∈ E(M). Consider the matroid MPxy with δ = { X1 ∪{u,u′},X2 ∪{v,v′} } . Then (i) MPxy \ Γ = M \{x,y}. (ii) ( (MPxy)uv ) u′v′ ∼= ( (MPxy)u′v′ ) uv ∼= M. (iii) If X1 = ∅, then MPxy/{u,u′} = MPxy/{u}\{u′} = MPxy/{u′}\{u} = M where {u,u′} is a 2-circuit of MPxy. Moreover, M P xy is a single parallel extension of M ′ x,y, or M P xy\u = M′x,y and MPxy\u′ = M′x,y. Proof. The proofs are straightforward. A binary matroid M with ground set E is Eulerian if there exist disjoint circuits C1,C2, ...,CP such that E = C1 ∪C2 ∪ ...∪CP and M is called bipartite matroid if every circuit has even cardinality. For a given connected graph G, the matroid M(G) is Eulerian if and only if G is an Eulerian [6]. A matroid M is Eulerian if and only if Mxy is Eulerian [3]. The next theorem, says that this property is preserved under 2-pinching operation. To prove this theorem, we consider the following lemma and we use the fact that M is a binary matroid if and only if the symmetric difference of any set of circuits is a disjoint union of circuits [4]. Lemma 5.2. Let MPxy be a pinching of a Eulerian binary matroid M. Then E(M) can be partitioned into a collection of disjoint circuits of M such that this partition contains Cxy. Proof. For some k, Let π = (C1,C2, ...,Ck) be a partition of E(M) such that Cxy /∈ π. Choose all circuits of this partition that have a non-empty intersection with Cxy. Let V be the union of these circuits and let V ′ be the union of other circuits of this partition which are not in V . Then, there is a circuit C that is not in π and contains x, y or both such that C ∩V ′ = ∅ and V ∆C is a disjoint union of circuits and contains Cxy. Now E(M) = V ′ ∪ (V ∆C). Clearly, this union is a disjoint union of circuits. Theorem 5.3. Let M be a binary matroid on a set E and x,y ∈ E. Then M is Eulerian if and only if MPxy is Eulerian. Proof. Suppose that M is a binary Eulerian matroid and x,y ∈ E(M). Then, for some k, there are disjoint circuits C1,C2, ...,Ck of M such that E(M) = ⋃k i=1 Ci. Let M P xy be a pinching of M. If x ∈ Ci and y ∈ Cj where i,j ∈{1, 2, ...,k} and i 6= j, then C′ = (Ci−{x})∪{α1,α2} and C′′ = (Cj−{y})∪{α3,α4} are disjoint circuits of MPxy. Clearly, E(M P xy) = C1∪...∪Ci−1∪C′∪Ci+1∪...∪Cj−1∪C′′∪Cj+1∪...∪Ck and these circuits are pairwise disjoint. If x,y ∈ Ci′, for i′ ∈ {1, 2, ...,k}, then we have two following cases. (i) If Cxy = Ci′ and P = (X1,X2), then E(MPxy) = C1∪...∪Ci′−1∪(X1∪{α1,α3})∪(X2∪{α2,α4})∪ Ci′+1 ∪ ...∪Ck. Clearly, any two members of this union are disjoint. 256 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 (ii) If Cxy 6= Ci′, then we have two following cases: -If ( (Ci′ − {x,y}) ∪ {α1,α2,α3,α4} ) ∈ C3, then E(MPxy) = C1 ∪ ... ∪ Ci′−1 ∪ (Ci′ − {x,y}) ∪ {α1,α2,α3,α4}) ∪Ci′+1 ∪ ...∪Ck. Clearly, any two members of this union are disjoint. -If ( (Ci′ −{x,y}) ∪{α1,α2,α3,α4} ) /∈C3, then by Lemma 5.2, there is another partition of E(M) containing Cxy and by part (i) of this proof we can see that MPxy is an Eulerian matroid. We conclude that MPxy is an Eulerian matroid. To prove the converse, by Theorem 5.1, M = ((MPxy)α1α2 )α3α4. Therefore when M P xy is an Eulerian matroid, M is Eulerian. Corollary 5.4. Every uniform matroid Un,n+1 can be constructed from U1,2 by a sequence of the 2- pinching, splitting and splitting off operations. Proof. Let M = U1,2 and so there is no partition P. Then M∅xy ∼= U1,2 ⊕ U1,2. Now let {x′,y′} be {α1,α2} or {α3,α4}. Then (M∅xy)x′,y′ ∼= U3,4 and ((U3,4)x′,y′ )x′y′ ∼= U2,3. By repeating this process (first applying the 2-pinching operation with respect to partition P with one empty part, then applying splitting and splitting off operations, respectively), we eventually obtain Un,n+1 and then Un−1,n , respectively. On combining Theorem 5.3 with Corollary 5, we immediately obtain the following result. Theorem 5.5. A binary matroid is Eulerian if, by repeated applications of splitting and 2-pinching operations, it can be transformed to a direct sum of copies of U1,2 and U2,3. Now we extend the notions of subdivision of edge and vertex identification from graphs to binary matroids by the pinching operation in the following way. Let G be a 2-connected graph and x,y ∈ E(G). After applying the pinching operation on x and y, let {x′,y′} and {x′′,y′′} be the disjoint subsets of members of δ. Clearly, if we apply the splitting operation using {x′,x′′} or {y′,y′′}, then the obtained graph is isomorphic to the graph resulting by subdivision of G on x and y. Let G be a 2-connected graph and u,v,w,z ∈ E(G), such that t1 and t2 are the common vertices of {u,v} and {w,z}, respectively, and there are no other edges on t1 and t2. Suppose that α and α′ are the new elements of the obtained graph after applying the splitting off operation on {u,v} and then {w,z}, respectively. Now if we implement the pinching operation on {α,α′}, then the obtained graph is isomorphic to the graph obtained by vertex identification of t1 and t2. Definition 5.6. Let M be a connected binary matroid and x,y ∈ E(M). Consider the matroid MPxy with δ = { X1 ∪{u,u′},X2 ∪{v,v′} } . We call N1 as the subdivision of M on x and y if N1 ∼= (MPxy)u,v ∼= (MPxy)u′,v′. Definition 5.7. Let M be a connected binary matroid and Γ ⊆ E(M) such that Γ = {u,v,u′,v′}. Suppose that {u,v} and {u′,v′} are cocircuits of M and E(Muv) −E(M) = {α} and E(Mu′v′ ) −E(M) = {α′}. We call N2 is the identification {u,v} with {u′,v′} in M, if N2 ∼= ((Muv)u′v′ )Pαα′ ∼= ((Mu′v′ )uv) P αα′. Corollary 5.8. The matroids N1 and N2, defined as in definitions 5.6 and 5.7, are extensions of the notions of subdivision and vertex identification from graphs to connected binary matroids. References [1] G. Azadi, Generalized splitting operation for binary matroids and related results, Ph.D. Thesis, Uni- versity of Pune, 2001. 257 V. Ghorbani et al. / J. Algebra Comb. Discrete Appl. 7(3) (2019) 247–258 [2] A. Frank, Edge–connection of graphs, digraphs, and hypergraphs, More Sets, Graphs and Numbers 15 (2006) 93–141. [3] M. M. Shikare, K. V. Dalvi, S. B. Dhotre, Splitting off operation for binary matroids and its applica- tions, Graph and Combinatorics 27 (2011) 871–882. [4] J. Oxley, Matroid Theory, Oxford University Press, 2nd ed. 2011. [5] T. T. Raghunathan, M. M. Shikare, B. N. Waphare, Splitting in a binary matroid, Discrete Math. 184 (1998) 267–271. [6] D. J. A. Welsh, Euler and bipartite matroids, Journal of Combinatorial Theory 6(4) (1969) 375–377. [7] D. West, Introduction to graph theory, Prentice–Hall, 2nd ed. 2001. 258 https://doi.org/10.1007/978-3-540-32439-3_6 https://doi.org/10.1007/978-3-540-32439-3_6 https://doi.org/10.1007/s00373-010-1005-y https://doi.org/10.1007/s00373-010-1005-y https://doi.org/10.1016/S0012-365X(97)00202-1 https://doi.org/10.1016/S0012-365X(97)00202-1 https://doi.org/10.1016/S0021-9800(69)80033-5 Introduction 2-pinching operation in 2-connected graphs 2-pinching operation for binary matroids Connectivity of MPxy Applications References