EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 2, 2024, 772-789 ISSN 1307-5543 – ejpam.com Published by New York Business Global Eigenvalue Interlacing of Bipartite Graphs and Construction of Expander Code using Vertex-split of a Bipartite Graph Machasri Manickam1, Kalyani Desikan1,∗ 1 Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Chennai, Tamilnadu, India. Abstract. The second largest eigenvalue of a graph is an important algebraic parameter which is related with the expansion, connectivity and randomness properties of a graph. Expanders are highly connected sparse graphs. In coding theory, Expander codes are Error Correcting codes made up of bipartite expander graphs. In this paper, first we prove the interlacing of the eigenvalues of the adjacency matrix of the bipartite graph with the eigenvalues of the bipartite quotient matrices of the corresponding graph matrices. Then we obtain bounds for the second largest and second smallest eigenvalues. Since the graph is bipartite, the results for Laplacian will also hold for Signless Laplacian matrix. We then introduce a new method called vertex-split of a bipartite graph to construct asymptotically good expander codes with expansion factor D 2 < α < D and ϵ < 1 2 and prove a condition for the vertex-split of a bipartite graph to be k−connected with respect to λ2. Further, we prove that the vertex-split of G is a bipartite expander. Finally, we construct an asymptotically good expander code whose factor graph is a graph obtained by the vertex-split of a bipartite graph. 2020 Mathematics Subject Classifications: 05C40, 05C48, 05C50 Key Words and Phrases: Expander code, vertex-split, second largest eigenvalue, bipartite graph, quotient matrix 1. Introduction Let G be a finite graph. The adjacency matrix A(G) of G is an n×n matrix A = [aij ], where aij = 1 if vi and vj are adjacent, otherwise it is 0. Let λ1 ≥ λ2 ≥ · · · ≥ λn be the eigenvalues of A known as the spectrum of G. The Laplacian matrix of G is L(G) = D(G) − A(G) where D(G) is the diagonal degree matrix. Let µ1 ≥ µ2 ≥ µ3 ≥ · · · ≥ µn−1 ≥ µn be the eigenvalues of the Laplacian matrix. The signless Laplacian matrix of G is Q(G) = D(G) + A(G). For a bipartite graph, Laplacian and signless Laplacian ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i2.5102 Email addresses: machasri.m2019@vitstudent.ac.in (M.Machasri), kalyanidesikan@vit.ac.in (D.Kalyani) https://www.ejpam.com 772 © 2024 EJPAM All rights reserved. M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 773 eigenvalues are the same. Expanders are graphs which are sparse but highly connected. The word sparse means that the number of edges of G is much less than the possible number of edges of G. Expander has wide application in various areas of computer science including pseudoran- domness, complexity theory, coding theory, algorithm design, cryptography, etc. Depending on the use, the term expander has many meanings. An (n,m, d, γ, α)− expander is a bipartite graph H = (X,Y,E) where |X| = n, |Y | = m, d(x) = d for all x ∈ X and for every S ⊆ X, |S| ≤ γn, we have the set of vertices N(S) ⊆ Y such that |N(S)| ≥ α|S|, where γ and α are positive constants. To obtain good expansion, α should be high. An expander is said to be a lossless expander when α is closer to d. Expander code has rate at least 1−m n . Therefore, smaller m implies codes with higher rate. An Error-Correcting Code (ECC) is a type of encoding used in the theory of coding to transfer messages as binary numbers in a way that allows the message to be decoded even if some bits are reversed. The error-correcting codes known as expander codes are constructed from bipartite expander graphs. A collection of strings known as codewords form an error correcting code denoted by C. Block length of an ECC is the number of elements in the code word and it is denoted by n. The codewords consist of n symbols from σ which is the alphabet set. A code is referred to as (n, k)q code where |σ| = q and |C| = qk. k indicates how many informa- tional symbols are contained in each codeword and R(C) = k n is the rate of the code. The smallest Hamming distance between two different codewords of C is the distance D(C) of the code. The parity-check and generator matrix views of the code give reasons for seeing linear codes as graphs and building them using graph-theoretic methods. To express the properties of the code from the characteristics of the graph, we can interpret the parity check matrix for a [n, n −m]2 code as representing an n ×m bipartite graph. Low Den- sity Parity Check (LDPC) codes are an interesting family of codes since they appear as sparse graphs in the graph view because there are few 1′s in each row and column of the parity-check matrix. In Section 4 we obtain the upper bound for the second largest adjacency eigenvalue, lower bound for the second smallest adjacency eigenvalue and upper bound for the second largest Laplacian eigenvalue of a connected bipartite graph G. To obtain sharper bounds, we discuss some possible cases with respect to the bipartitions of G in a minimally con- nected bipartite graph and derive bounds for the second largest adjacency eigenvalue and second smallest adjacency eigenvalue in terms of n, the number of vertices. In Section 5, we introduce a new concept called vertex-split of bipartite graph and we prove a condition for the vertex-split of a bipartite graph to be k−connected with respect to λ2. We prove theorems related to connectivity and prove the expansion of vertex-split M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 774 of a bipartite graph. Finally, in Section 6 we show that the vertex-split of a biregular bipartite graph forms an expander code. 2. Related work Eigenvalues are often difficult to compute. Therefore, obtaining bounds for eigenvalues is useful. In literature, bounds have been found for the second largest eigenvalue of some family of graphs. Chang An [2] obtained upper and lower bounds for the second largest eigenvalue of a tree. The lower bounds on the second largest eigenvalue of a regular graph with given girth were obtained by Patrik Solv [14]. Mehatari and Kannan [11] derived bounds for the second largest and second smallest eigenvalues of adjacency matrices, nor- malized adjacency matrices and Laplacian matrices of regular graphs. In 1988, Powers [12] gave some upper bounds of second largest eigenvalue for general graphs and bipartite graphs. In 2012, Mingqing Zhaim et al. [18] presented upper bounds for the second largest eigenvalue of connected graphs and particularly, for bipartite graphs. Expander codes which are constructed from unbalanced bipartite expander graphs with expansion factor (1 − ϵ)D for ϵ < 1 2 are said to be asymptotically good codes. Initially, constructions with α ≈ D 2 were known explicitly. So the requirement is to give explicit construction of codes with expansion higher than D 2 . In 2002, Capalbo et al. [4] presented an explicit construction with expansion (1 − ϵ)D where D is the degree of the left side partition of G for any desired ϵ > 0, and imbalance ratio m n . Using the edge vertex matrix is one method of building an unbalanced expander, which Tanner [16] introduced and Sipser and Spielman [13]-[15] employed. Also, it is observed by Zemor [17] that if the edge vertex incidence graph’s underlying graph is a bipartite graph, the decoding technique is straightforward. In this work, we use vertex-split of a bipartite graph to construct expanders codes with expansion factor D 2 < α < D and ϵ < 1 2 . 3. Preliminaries Definition 1. [9](Quotient matrix) Let M = M11 · · · M1t ... . . . ... Mt1 · · · Mtt  be a real matrix of order n and Mij be the blocks of M, where i,j = 1, 2, . . . , t. Then B(M)=(bij) is called the Quotient Matrix of M where bij is the sum of all entries in Mij divided by the number of rows of Mij. Definition 2. [3](Interlacing) Consider two sequences of real numbers: ξ1, ξ2, . . . , ξn and η1, η2, . . . , ηm with m ≤ n. The second sequence is said to interlace the first one whenever ξi ≤ ηi ≤ ξn−m+i for i = 1, 2, . . . ,m. The interlacing is called tight if M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 775 there exists an integer k ∈ [0,m] such that ξi = ηi for 1 ≤ i ≤ k and ξn−m+i = ηi for k + 1 ≤ i ≤ m. Definition 3. A graph is said to be minimally connected if removal of any one edge disconnects the graph. Lemma 1. ([6]-[10]) Let AQ be the quotient matrix of a symmetric matrix A whose rows and columns are partitioned according to a partitioning (X1, X2, . . . , Xm). Then (i) The eigenvalues of AQ interlace the eigenvalues of A. (ii) If the interlacing is tight then the partition is equitable. Definition 4. [8] (Vertex expander) A graph G with n vertices is said to be a vertex expander if |N(S)| ≥ A|S| for all S ⊆ V : |S| ≤ n 2 , where A is a constant and N(S) is the neighbourhood of S in G not in S. Definition 5. [8] (Spectral expansion) The spectral expansion of graph G is defined by λ = max{|λ2|, |λn|}. Definition 6. [1] Let G = (V,E) be a graph. For a subset S of V let N(S) = {v ∈ V : vs ∈ E for some s ∈ S}. An (n, d, c)−expander is a bipartite graph on the sets of vertices X and Y , where |X| = |Y | = n , the maximal degree of a vertex is d, and for every set S ⊆ X of cardinality |S| = α ≤ n 2 , |N(S)| ≥ (1 + c(1− α n ))α. Definition 7. [4] A D−left regular bipartite graph G = (X ∪ Y,E) where |X| = n and |Y | = m such that for all S ⊆ X with |S| ≤ γn, |N(S)| ≥ α|S|, where γ and α are positive constants is known as an (n,m,D, γ,D(1− ϵ)) expander. Note : Let λ1 ≥ λ2 ≥ · · · ≥ λn be the adjacency eigenvalues of G and let λ′ 1 ≥ λ′ 2 ≥ · · · ≥ λ′ n be the adjacency eigenvalues of G′. Assume that γi = λ′ i d be the normalized eigenvalues of G′. Let λ′ be the spectral expansion of G′. Then γ = λ′ d is the spectral expansion of G′ with respect to the normalized adjacency eigenvalues. Lemma 2. [8] (vertex expansion to spectral expansion). Let G be a d−regular graph. For every ϵ > 0 and d > 0, there exists γ > 0 such that if G is a d−regular (1 + ϵ)−expander then G has spectral expansion (1− γ). Specifically, we can take γ = Ω(ϵ2/d). Lemma 3. [5] Let G be an (n,m,D, γ,D(1 − ϵ)) expander. Then the distance of the code corresponding to the graph G is ∆(C(G)) ≥ 2γ(1− ϵ)n where C(G) denotes the code corresponding to an expander graph G. M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 776 4. Eigenvalue Interlacing of Bipartite Quotient Matrix and Spectral Bounds In this section we derive the upper bounds for the second largest eigenvalues of both the adjacency matrix and Laplacian matrix of a connected bipartite graph. Also, we derive the lower bounds for the second smallest eigenvalue of the adjacency matrix of a connected bipartite graph. To arrive at these bounds, we define the Bipartite quotient matrix as follows : Definition 8. (Bipartite quotient matrix) Let G be a bipartite graph. The Bipartite quo- tient matrix of the Adjacency matrix A (Laplacian matrix L) of G is the Quotient matrix of A/L whose rows and columns are partitioned according to the bipartition of G. 4.1. Bounds for the second largest eigenvalue and second smallest eigen- value of adjacency matrix In this section we derive the upper bounds for the second largest eigenvalue and lower bounds for the second smallest eigenvalue of the adjacency matrix of a connected bipartite graph G. Theorem 1. Consider a Bipartite graph G with bipartition V = (X,Y ) where |X| = n1, |Y | = n2 and |V | = n1 + n2 = n. Let λ1 ≥ λ2 ≥ · · · ≥ λn−1 ≥ λn be the eigenvalues of the adjacency matrix A of G, AQ be the bipartite quotient matrix of A and η1 and η2 the eigenvalues of AQ. Then (i) λ1 ≥ η1 ≥ λ2 (ii) λn−1 ≥ η2 ≥ λn (iii) λ2 ≤ m√ n1n2 (iv) λn−1 ≥ −m√ n1n2 Proof. Let A be the adjacency matrix of G represented in the following block matrix form with respect to the bipartition V = (X,Y ). A = [ A11 A12 A21 A22 ] . Let AQ be the bipartite quotient matrix of A. Then AQ = [ 0 m n1 m n2 0 ] . The characteristic equation of AQ is λ2 − m2 n1n2 = 0 and the corresponding eigenvalues of AQ are η1 = m√ n1n2 and η2 = −m√ n1n2 . To get the generalized interlacing, we need n M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 777 eigenvalues. To obtain this, consider the following. The characteristic matrix of G is given by S̃ = [ Jn1×1 0n1×1 0n2×1 Jn2×1. ] n×2 where J is the all-ones matrix. Let S = S̃K −1 2 where K = diag(|X|, |Y |). i.e., K =[ n1 0 0 n2 ] . Then S = [ Pn1×1 0n1×1 0n2×1 Rn2×1 ] n×2 . where Pn1×1 and Rn2×1 are column matrices with entries (pi1) = 1√ n1 for all vi ∈ X and (ri1) = 1√ n2 for all vi ∈ Y , respectively. From the proof of Lemma 1 [7] we have, AQ = STAS. (1) Left and right multiplying equation (1) by S and ST respectively, we get, SAQS T = A. Now consider SAQS T and denote it by C.Then C = (cij) =  m n1 √ n1 vi ∈ X and vj ∈ Y m n2 √ n2 vi ∈ Y and vj ∈ X 0 otherwise. The above matrix can be represented as a block matrix as follows: C = [ 0 M N 0 ] n×n . Denote the eigenvalues of C by γi, i = 1, 2, . . . , n. The eigenvalues of C are the square roots of the non-zero eigenvalues of MN . That is γ1 = m√ n1n2 , γn = −m√ n1n2 and γi = 0 for i = 2, 3, . . . , n− 1. Then by interlacing we get, λ1 ≥ γ1 ≥ λ2 ≥ · · · ≥ λn−1 ≥ γn−1 ≥ λn ≥ γn. By comparing the eigenvalues of AQ and C we get, γ1 = m√ n1n2 = η1 and γn = −m√ n1n2 = η2. Now let us first consider λ1 ≥ γ1 ≥ λ2. Since γ1 = η1 we have λ1 ≥ η1 ≥ λ2. This proves (i). Since G is bipartite, its eigenvalues are symmetric about the origin. Now from (i) and since G is bipartite, we get λn ≤ η2 ≤ λn−1. This proves (ii). To prove (iii), using (i) we have, λ2 ≤ η1 = m √ n1n2 . M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 778 To prove (iv), using (ii), we have, λn−1 ≥ η2 = −m √ n1n2 . This completes the proof. Corollary 1. If G is a regular bipartite graph then λ2 ≤ m n1 Proof. For a regular bipartite graph G, n1 = n2. Substituting this in (iii) of Theorem 1, we get the result. Corollary 2. If G is a regular bipartite graph then λn−1 ≥ −m n1 Proof. For a regular bipartite graph G, n1 = n2. Substituting this in (iv) of Theorem 1, we get the result. In the following theorems, we present simpler bounds, involving a single parameter n, when compared to the bounds obtained in Theorem 1. To achieve this we require m to be minimum. m would be minimum only if G is minimally connected, that is m = n− 1. We consider three types of bipartitions such as balanced, unbalanced and average bipar- titions to arrive at our result. For a balanced bipartition we have (n1, n2) = (n−1 2 , n+1 2 ) n is odd (n2 , n 2 ) n is even . Unbalanced bipartition is given by, (n1, n2) = (1, n− 1). Average bipartition is given by (n1, n2) =  (3n−4 4 , n+4 4 ) if n is even (3n−3 4 , n+3 4 ) if n = 4k + 3 where k = 0, 1, 2, . . . . (3n−5 4 , n+5 4 ) if n = 4k + 1 where k = 0, 1, 2, . . . . Let η11, η12 and η13 represent the largest eigenvalues of the bipartite quotient matrices corresponding to the three different bipartitions. Let η1 = min{η11, η12, η13}. Let η21, η22 and η23 represent the smallest eigenvalues of the bipartite quotient matrices corresponding to the three different bipartitions. Let η2 = max{η21, η22, η23}. M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 779 Theorem 2. Let G be a connected bipartite graph of order n. Then λ2 ≤  2(n−1)√ n2−1 n is odd 2(n−1) n n is even. Proof. From Theorem 1 we have, λ2 ≤ m √ n1n2 . (2) Consider the following cases. Case 1: Let G be minimally connected with balanced bipartition. Substituting for m,n1 and n2 for a balanced bipartition in equation (2), we have η11 =  2(n−1)√ n2−1 n is odd 2(n−1) n n is even. Case 2: Let G be minimally connected with unbalanced bipartition. Substituting for m,n1 and n2 for an unbalanced bipartition in equation (2), we have η12 = n− 1√ n− 1 = √ n− 1. Case 3: Let G be minimally connected with the average bipartition. Substituting for m,n1 and n2 for an average bipartition in equation (2), we have when n is even, η13 =  4(n−1)√ 3n2+8n−16 if n is even 4(n−1)√ 3n2+6n−9 if n = 4k + 3 where k = 0, 1, 2, . . . . 4(n−1)√ 3n2+10n−25 if n = 4k + 1 where k = 0, 1, 2, . . . . When n is even, comparing all the three cases, since the numerator contains (n− 1) as a common term, we have √ n− 1 ≤ √ 3n2 + 8n− 16 4 ≤ n 2 . which implies that 2(n− 1) n ≤ 4(n− 1)√ 3n2 + 8n− 16 ≤ √ n− 1. When n is odd and n = 4k + 3 where k = 0, 1, 2, . . . , comparing all the three cases, since the numerator contains (n− 1) as a common term, we have √ n− 1 ≤ √ 3n2 + 6n− 9 4 ≤ √ n2 − 1 2 . M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 780 which implies that 2(n− 1)√ n2 − 1 ≤ 4(n− 1)√ 3n2 + 6n− 9 ≤ √ n− 1. When n is odd and n = 4k + 1 where k = 0, 1, 2, . . . , comparing all the three cases, since the numerator contains (n− 1) as a common term, we have √ n− 1 ≤ √ 3n2 + 10n− 25 4 ≤ √ n2 − 1 2 . which implies that 2(n− 1)√ n2 − 1 ≤ 4(n− 1)√ 3n2 + 10n− 25 ≤ √ n− 1. Comparing all the three cases, we get η11 ≤ η13 ≤ η12. From this we have, η1 = η11. Applying this in equation (2), we get a tight upper bound in terms of n as λ2 ≤  2(n−1)√ n2−1 n is odd 2(n−1) n n is even. Theorem 3. Let G be a connected bipartite graph of order n. Then λn−1 ≥  −(2(n−1))√ n2−1 n is odd −(2(n−1)) n n is even. Proof. In Theorem 1, we have proved that λn−1 ≥ −m √ n1n2 . (3) Consider the following cases. Case 1: G is minimally connected with balanced bipartition. Substituting for m,n1 and n2 for a balanced bipartition in equation (3), we have η21 =  −(4(n−1))√ 3n2+8n−16 if n is even −(4(n−1))√ 3n2+6n−9 if n = 4k + 3 where k = 0, 1, 2, . . . . −(4(n−1))√ 3n2+10n−25 if n = 4k + 1 where k = 0, 1, 2, . . . . Case 2: G is minimally connected with unbalanced bipartition. Substituting for m,n1 and n2 for an unbalanced bipartition in equation (3), we have η22 = −(n− 1)√ n− 1 = − √ n− 1. M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 781 Case 3: G is minimally connected with average bipartition. Substituting for m,n1 and n2 for an average bipartition in equation (3), we have η23 =  −(2(n−1)) n n is even −(2(n−1))√ n2−1 n is odd. When n is even, comparing all the three cases, since the numerator contains (n− 1) as a common term, we have √ n− 1 ≤ √ 3n2 + 8n− 16 4 ≤ n 2 . which implies that −(2(n− 1)) n ≥ −(4(n− 1))√ 3n2 + 8n− 16 ≥ − √ n− 1. When n = 4k+3 where k = 0, 1, 2, . . . , comparing all the three cases, since the numerator contains (n− 1) as a common term, we have √ n− 1 ≤ √ 3n2 + 6n− 9 4 ≤ √ n2 − 1 2 . which implies that 2(n− 1)√ n2 − 1 ≤ 4(n− 1)√ 3n2 + 6n− 9 ≤ √ n− 1. When n = 4k+1 where k = 0, 1, 2, . . . , comparing all the three cases, since the numerator contains (n− 1) as a common term, we have √ n− 1 ≤ √ 3n2 + 10n− 25 4 ≤ √ n2 − 1 2 . which implies that 2(n− 1)√ n2 − 1 ≤ 4(n− 1)√ 3n2 + 10n− 25 ≤ √ n− 1. Comparing all the three cases, we get η21 ≥ η23 ≥ η22. From this we have, η2 = η21. Applying this in equation (3), we get a tight lower bound in terms of n as λn−1 ≥  −(2(n−1))√ n2−1 n is odd −(2(n−1)) n n is even. M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 782 4.2. Bounds for the Second largest Laplacian eigenvalue In this section we derive the upper bound for the second largest Laplacian eigenvalue of a connected bipartite graph G. Theorem 4. Consider a Bipartite graph G with bipartition V = (X,Y ). Let µ1 ≥ µ2 ≥ · · · ≥ µn−1 ≥ µn be the eigenvalues of the Laplacian matrix L of G, LQ be the bipartite quotient matrix of L and θ1 and θ2 the eigenvalues of LQ. Then (i) µ1 ≥ θ1 ≥ µ2 (ii) µ2 ≤ mn n1n2 Proof. The proof is similar to that of Theorem 1. Let L be the Laplacian matrix of G represented in the following block matrix form with respect to the bipartition V = (X,Y ) L = [ L11 L12 L21 L22 ] . Let LQ be the Bipartite quotient matrix of the Laplacian matrix L of G. Then LQ = [ m n1 −m n1−m n2 m n2 ] . The characteristic equation of LQ is µ2 − mn n1n2 µ = 0 Then the eigenvalues of LQ are θ1 = mn n1n2 and θ2 = 0. To get the generalized interlacing consider the following. The characteristic matrix of G is given by S̃ = [ Jn1×1 0n1×1 0n2×1 Jn2×1 ] n×2 Let S = S̃K −1 2 , where K = diag(|X|, |Y |) i.e., K = [ n1 0 0 n2 ] . Then S = [ Pn1×1 0n1×1 0n2×1 Rn2×1 ] n×2 . where Pn1×1 and Rn2×1 are column matrices with entries (pi1) = 1√ n1 where i = 1, 2, . . . , n1 and (rj1) = 1√ n2 where j = 1, 2, . . . , n2. From the proof of Lemma 1 [7] we have, LQ = STLS. (4) Left and right multiplying equation (4) by S and ST we have SLQS T = L. Now consider SLQS T and denote it by U . Let U = (uij) =  m n2 1 vi, vj ∈ X m n2 2 vi, vj ∈ Y −m n1 √ n1n2 vi ∈ X and vj ∈ Y −m n2 √ n1n2 vi ∈ Y and vj ∈ X M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 783 Then the block matrix representation of U is given by U = [ E F G H ] n×n . Let the eigenvalues of U be β1 ≥ β2 ≥ · · · ≥ βn. The eigenvalues of U are the trace of U and 0, that is β1 = mn n1n2 and βi = 0 for i = 2, 3, . . . , n. Then the interlacing becomes, µ1 ≥ β1 ≥ µ2 ≥ · · · ≥ µn−1 ≥ βm ≥ µn which implies that µ1 ≥ β1 ≥ µ2. By comparing the eigenvalues of LQ and U we have, β1 = θ1. Let us consider µ1 ≥ β1 ≥ µ2. Since β1 = θ1, we have µ1 ≥ θ1 ≥ µ2. This proves (i). To prove (ii), using (i) we have, µ2 ≤ θ1 = mn n1n2 . Corollary 3. If G is a regular bipartite graph then µ2 ≤ 2m n1 . Proof. For a regular bipartite graph G, n1 = n2. Substituting this in Theorem 4, we get the result. Note: For a complete bipartite graph G, the size of G is equal to the product of the orders of the bipartitions of G, that is m = n1n2. Hence µ2 ≤ n. 5. Vertex-split of a bipartite graph In this section, we define vertex split of a bipartite graph. Next, we prove theorems related to the connectivity and expansion of vertex split of a bipartite graph. Definition 9. (Vertex-split of a bipartite graph) Let G = (X ∪ Y,E) be a connected bipartite graph with δ ≥ 4 where |X| = n1 ≥ 4, |Y | = n2 ≥ 3 with n1 > n2. A graph G′ = (X ′ ∪ Y ′, E′) is said to be a vertex-split of G if (i) |X ′| = |X| and |Y ′| = |Ya| + |Yb| = 2|Y | where Ya = {y1a, y2a, . . . , yn1a}, Yb = {y1b, y2b, . . . , yn2b}. (ii) Let deg(y) = dy = da + db ∀y ∈ Y such that da = deg(ya) ∀ya ∈ Ya and db = deg(yb) ∀yb ∈ Yb with the condition that |da − db| = { 1 if dy is odd 0 if dy is even. (iii) N(Ya) ∩N(Yb) ̸= ∅ Example: Vertex-split of a complete graph K8,4 is shown in figure 1 where |X| = |X ′| = 8, |Y | = 4, |Y ′| = 8 M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 784 Figure 1: Vertex-split of K8,4 5.1. Connectivity of Vertex-split of a bipartite graph Let G′ be a vertex-split of a bipartite graph G with minimum degree δ′ and edge connectivity κ′(G′). The adjacency eigenvalues of G′ are denoted as λ′ 1 ≥ λ′ 2 ≥ · · · ≥ λ′ n. Theorem 5. Let δ′ ≥ k ≥ 2 be a constant and let G(X ∪ Y,E) be a d−regular bipartite graph and G′ the vertex-split of G. If λ′ 2 ≥ 2k − 1√ 2 then κ′(G′) ≥ k. Proof. Our proof is by contradiction. We prove that if G′ is a connected bipartite graph of order n′ and minimum degree δ′ such that κ′(G′) ≤ 2k′ − 1, then λ′ 2 ≤ 2k − 1√ 2 . (5) Let n′ = n′ 1 + n′ 2 where n′ 1 = n1 and n′ 2 = 2n2 and δ′ = δ 2 . Let δ ′ ≥ k ≥ 2. From this we have δ 2 ≥ k ≥ 2. Consider δ 2 ≥ k. By (iii) of Theorem 1 we have, λ2 ≤ m √ n1n2 . (6) For a regular bipartite graph n1 = n2 = n 2 and m = nd 2 . Suppose δ ≤ 2k − 1. Substituting this in equation (6) we get, λ′ 2 ≤ d√ 2 = δ√ 2 λ′ 2 ≤ 2k − 1√ 2 This completes the proof. Example for connectivity of vertex-split of a regular graph: Consider a com- plete bipartite graph K5,5. The vertex-split of K5,5 is a graph with minimum degree δ′ = 2 and the second largest eigenvalue λ′ 2 = 2.34. Since it is regular graph, from theorem 1 we have, for k = 2, 2k−1√ 2 = 2.121 M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 785 Figure 2: vertex-split of K5,5 Theorem 6. Let G be a biregular bipartite graph with V = (X,Y ) where |X| = n1, |Y | = n2 and G′ the vertex-split of G. If λ′ 2 ≥ n2(2k − 1)√ 2n1n2 then κ′(G′) ≥ k. Proof. The proof is by contradiction. We prove that if G′ is a connected bipartite graph of order n′ and minimum degree δ′ such that κ′(G′) ≤ 2k − 1, then λ′ 2 ≥ n2(2k − 1)√ 2n1n2 . Let n′ = n′ 1 + n′ 2 where n′ 1 = n1 and n′ 2 = 2n2 and δ′ = δ 2 . Let δ ′ ≥ k ≥ 2. Therefore we have, δ 2 ≥ k ≥ 2. Consider δ 2 ≥ k. Suppose δ ≤ 2k − 1. For a biregular bipartite graph n1d1 = n2d2 = m, where d1 and d2 are the degrees of the bipartition with d1 > d2. Similarly n′ 1d ′ 1 = n′ 2d ′ 1 = m′ = m. Substituting this in (iii) of Theorem 1 we have, λ′ 2 ≤ n2d2√ 2n1n2 = n2δ√ 2n1n2 λ′ 2 ≤ n2(2k − 1)√ 2n1n2 This completes the proof. M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 786 5.2. Expansion of Vertex-split of a bipartite graph In this section, we prove that the vertex split of a complete bipartite graph is a bipartite expander. Theorem 7. The vertex-split of a complete bipartite graph Km,n is a bipartite expander if (i) n is even (ii) n ≤ m ≤ 2n Proof. Let G′ = (X ′ ∪ Y ′, E′) be the vertex-split of the complete bipartite graph G. Here |X ′| = |X| = m, |Y ′| = 2|Y | = 2n. Assume that S ⊆ X ′ with |S| = n 2 . To prove this theorem, consider the following cases. Case 1: m = n. In this case, when |S| = m 2 the cardinality of the neighbourhood of S is |N(S)| = m+2 2 which implies that |N(S)| ≥ α|S| where α = (1 + 2 n). Case 2: m = 2n. In this case, when |S| = n 2 the cardinality of the neighbourhood of S is |N(S)| = n which implies that |N(S)| ≥ α|S| where α = 1. Case 3: n < m < 2n. In this case, when |S| = n 2 the cardinality of the neighbourhood of S is |N(S)| = n+(i− n 2 ), i = 2, 3, . . . , n2 which implies that |N(S)| ≥ α|S| where α = 1+ (i−n 2 ) n , where i = 2, 3, . . . , n2 . By definition (4), in all the cases we conclude that the vertex-split of Km,n is a bipar- tite expander. Note: From the above theorem we say that, vertex-split G′ of G is a α− vertex expander. Corollary 4. The vertex-split G′ of a complete bipartite graph G = Km,n where n = m 2 is a (1− γ)−spectral expander. Proof. From the above theorem we know that G′ is a α− vertex expander where α = 1 + ϵ where ϵ = 1 n . From lemma 2, we can conclude that G′ is (1 − γ)−spectral expander where γ = 1 n2d′ , where d′ is the degree of G′. 6. Construction of Error correcting code Consider a biregular graphG with bipartitions (X,Y ) and the corresponding degrees d1 and d2. Let d1 = |X| 2 . In this section, we prove that the vertex-split of a biregular bipartite graph is a bipartite expander and then we show that the vertex-split of a biregular bipartite graph forms an expander code. Let C(G) be the error correcting code of block length n obtained from a bipartite graph G and let ∆(C(G)) be the distance of the code C. M.Machasri, D.Kalyani / Eur. J. Pure Appl. Math, 17 (2) (2024), 772-789 787 Lemma 4. Let G = (X ∪Y,E) be a biregular bipartite graph with |X| = n1 and |Y | = n2. Let d1, d2 be the degrees of the corresponding bipartitions X,Y where d1 = ⌊ |X| 2 ⌋. Then vertex-split G′ of G is a bipartite expander. Proof. Let G′ = (X ′ ∪ Y ′, E′) be the vertex-split of a biregular bipartite graph G with |X ′| = n1 and |Y ′| = 2n2. The degrees of the bipartitions X ′, Y ′ are denoted by d′1 and d′2 respectively. Let S be a subset of X ′ with |S| = n1 d′1 . Since d′1 = |X′| 2 , we have |S| = 2. For any subset S of X ′ the neighbourhood of S is |N(S)| ≥ n1 2 + 1, which implies that |N(S)| |S| ≥ α where α = (n1+2 4 ) is the vertex expansion constant. That is |N(S)| ≥ α|S|. This proves the result. Theorem 8. The vertex-split of a biregular bipartite graph G = (X∪Y,E) where |X| = n1, |Y | = n2 with degree d1 = |X| 2 is an expander code. Proof. We proved that the vertex-split of a biregular bipartite graph G is a bipartite expander in Lemma 4. For constructing an efficient error correcting code, let us fix |Y | as |Y | = n2 = max{x : x|n 2 1 2 and n1+2 4 < x < n1 2 }. Usually α is close to D 2 where D is the degree of the larger side partition. Here D = d1 = n1 2 . Then D 2 = n1 4 . Clearly D 2 < α < D, where α = (n1+2 4 ). Putting α = D(1− ϵ), we get ϵ = n1−2 2n1 < 1 2 . Corollary 5. Let the vertex-split G′ of G be a (n1, n2, d1, γ,D(1− ϵ)) expander. Then the distance of the ECC corresponding to graph G′ is ∆(C(G′)) ≥ n1(n1+2) 2d21 . Proof. We proved in Lemma 4 that the vertex-split G′ of G is a (n1, n2, d1, γ,D(1− ϵ)) expander, where γ = 1 d1 , α = n1+2 4 and ϵ = n1−2 2n1 . Substituting all these in Lemma 3, we get the result. 7. Conclusion In the first part of this paper, we defined bipartite quotient matrix of matrices associ- ated with bipartite graphs and proved that the two eigenvalues of the bipartite quotient matrix interlace at the two ends of the spectrum of the adjacency matrix of a bipartite graph. From this interlacing, we obtained the upper bound for the second largest eigen- value and the lower bound for the second smallest eigenvalue of a bipartite graph. To achieve a more sharper bound we considered the minimally connected graph for three different bipartitions and obtained two new bounds which depend only on the order of the graph. Also, we proved the eigenvalue interlacing for the Laplacian matrix and obtained an upper bound for the second largest Laplacian eigenvalue. In the second part of this paper, we defined vertex-split of a bipartite graph and proved its connectivity with respect to the second largest eigenvalue. Finally, we proved that the vertex-splits of complete bipartite graph Km,n and biregular bipartite graph G(X,Y ) are bipartite expanders and constructed an efficient ECC with expansion factor α > D 2 . REFERENCES 788 Acknowledgements We are highly thankful to the anonymous referees for their comments and suggestions to enhance our paper. References [1] Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. [2] Chang An. Bounds on the second largest eigenvalue of a tree with perfect matchings. Linear algebra and its applications, 283(1-3):247–255, 1998. [3] Andries E Brouwer and Willem H Haemers. Spectra of graphs. Springer Science & Business Media, 2011. [4] Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 659–668, 2002. [5] Venkatesan Guruswami. Expander codes and their decoding. https://www.cs.cmu.edu/ venkatg/teaching/codingtheory/notes/notes8.pdf, 2010. [6] W Haemers. Eigenvalue techniques in design and graph theory (thesis), tract 121, math. Centrum Amsterdam, 1980. [7] Willem H Haemers. Interlacing eigenvalues and graphs. Linear Algebra and its ap- plications, 226:593–616, 1995. [8] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their appli- cations. Bulletin of the American Mathematical Society, 43(4):439–561, 2006. [9] Chia-an Liu and Chih-wen Weng. Spectral radius of bipartite graphs. Linear Algebra and its Applications, 474:30–43, 2015. [10] Huiqing Liu, Mei Lu, and Feng Tian. Edge-connectivity and (signless) laplacian eigenvalue of graphs. Linear Algebra and Its Applications, 439(12):3777–3784, 2013. [11] Ranjit Mehatari and M Rajesh Kannan. Eigenvalue bounds for some classes of ma- trices associated with graphs. Czechoslovak Mathematical Journal, 71:231–251, 2021. [12] David L Powers. Graph partitioning by eigenvectors. Linear Algebra and its Appli- cations, 101:121–133, 1988. [13] Michael Sipser and Daniel A Spielman. Expander codes. IEEE transactions on Information Theory, 42(6):1710–1722, 1996. [14] Patrick Solé. The second eigenvalue of regular graphs of given girth. Journal of Combinatorial Theory, Series B, 56(2):239–249, 1992. REFERENCES 789 [15] Daniel A Spielman. Linear-time encodable and decodable error-correcting codes. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 388–397, 1995. [16] R Tanner. A recursive approach to low complexity codes. IEEE Transactions on information theory, 27(5):533–547, 1981. [17] Gillés Zémor. On expander codes. IEEE Transactions on Information Theory, 47(2):835–837, 2001. [18] Mingqing Zhai, Huiqiu Lin, and BingWang. Sharp upper bounds on the second largest eigenvalues of connected graphs. Linear algebra and its applications, 437(1):236–241, 2012.