Report

A Cheeger inequality of a distance regular graph using the Green’s function Gil Chun Kim Department of Mathematics Dong-A University, Busan, Korea 1. Some definitions and facts 2. Green’s function 3. A Cheeger inequality of a distance regular graph 4. Explicit expression of the krawtchouk polynomial be a subset of set of vertices in a graph Γ = (, ), where is a set of vertices of Γ and is a set of edges of Γ. . Let () The edge boundary of , denoted by is defined as follows: = , ∈ Γ ∈ ∈ − }, where (Γ) is a edge set of Γ. () If ≠ ∅, then the volume of , denoted by () is defined as follows: = ∈ where is a valency of in Γ. The volume of Γ is denoted by Γ = () The ℎ of , denoted by ℎ is defined as || ℎ = min{ , Γ − } () The ℎ of Γ, denoted by ℎΓ is defined as ℎΓ = min ℎ ⊂ In graph theory, the Cheeger constant is an important geometric meaning. The Cheeger constant give to us answer of the problem of separating the graph into two large components by making a small edge-cut. The Cheeger constant of a connected graph is strictly positive. If the Cheeger constant is “small” but postive, then there are two large sets of vertices with “few” edges between them. On the other hand if the Cheeger constant is “large”, then there are two sets of vertices with “many” edges between those two subsets. We are interested in finding bounds on the Cheeger constants of graphs. The Hamming graph is the graph that describes the distance – 1 relation in the Hamming scheme (, ) The Hamming graph is a special class of graphs used in several branches of Mathematics and Computer Science. The Hamming graphs are interesting in connection with error-correcting codes and association schemes. The Cheeger constant of the Hamming graphs Γ(, ) +1 2 ℎΓ = ( − 1) Hamming graph Γ(3,2) = 000, 100, 010, 110 = 4, = 12 4 1 ℎΓ = = 12 3 The Johnson graph is also an interesting class of graphs. A vertex set of , consists of all binary vectors of length with Hamming weight , such that = . The Johnson graph is the graph that describes the distance – 1 relation in the Johnson scheme (, ). Two vertices are adjacent if they differ in two coordinates. The Cheeger constant of the Johnson graphs Γ(, ) ℎΓ ≤ ℎΓ ≤ (−+1)2 2 2(−) 2 + 4 2 2 2 , if is even and is odd. , if is even and is even. ℎΓ ≤ ℎΓ ≤ (+1)2 +(−1) 4 2 2 2 (+1)2 +(−−1) 4(−) 2 , if is odd and is odd. 2 2 , if is odd and is even. . Let Γ be a connected graph. For a vertex ∈ , define Γ to be the set of vertices which are at distance precisely from (0 ≤ ≤ ), where = max , , ∈ }. A connected graph Γ with diameter is called if there are integers , +1 0 ≤ ≤ − 1 such that for any two vertices , with , = , there are precisely neighbors of in Γ−1 and neighbors of in Γ+1 . . Let be a nonempty finite set and = {0 , 1 , ⋯ , } be a family of relations defined on . Let be the order of . Then adjacency matrix of ( = 0,1, ⋯ , ) is the × matrix defined by 1 , if (, ) ∈ ( ), = { 0 , otherwise. We say that the pair = (, ) is a symmetric association scheme with classes if it satisfies the following conditions. 1 is symmetric, (2) =0 = (the all 1’s matrix), (3) 0 = , (4) = =0 , (, = 0,1,2, ⋯ , ). Let be the algebra spanned by the adjacency matrices 0 , 1 , ⋯ , . Then is called the Bose Mesner algebra of and has two distinguished bases and , where the latter consist of primitive idempotent matrices. For and , we express one in terms of the other: 1 = =0 () , = =0 () for = 0,1, ⋯ , . || The ( + 1) × + 1 matrix = ( ) (respectively, Q= ( ) ) is called the first eigenmatrix (respectively, the second eigenmatrix) of the association scheme. Then = ( ) and Q= ( ) satisfy = , where = ( ), is the valency of ,and is the complex conjugate of . The adjacency matrices satisfy = =0 , for all , , where for (, ) ∈ , , is the number of ∈ such that (, ) ∈ and , ∈ . The non-negative integers , are called the intersection numbers of . Let be a matrix with (, )-entries , ,and let ℬ be a algebra spanned by 0 , 1 , ⋯ , . Then is called the -th intersection matrix of and ℬ is called the intersection algebra of . In fact, the Bose-Mesner algebra of is isomorphic to ℬ by the map → . Let = , ( = 0,1, ⋯ , ) be a symmetric association scheme, and let Γ be the graph whose set and edge set are and 1 respectively. Then, it is known that the following are equivalent. () Γ is distance regular graph. () is a –polynomial scheme with respect to 0 , 1 , ⋯ , , that is 1 ( = 0,1, ⋯ , ) for some polynomial of degree . () The first eigenmatrix = ( ) satisfies = ( ) for some polynomials of degree , where = 1 (, = 0,1, ⋯ , ). () The first intersection matrix 1 is a tridiagonal matrix with non-zero off diagonal entries, = Let Γ be a graph of order , and let λ1 be the smallest positive eigenvalue of the Laplacian of Γ. Then there are Cheeger inequalities as follows: () [1] ℎΓ 2 2 ≤ 1 ≤ 2ℎΓ ⟹ ℎΓ ≤ 21 ; [1] J. Dodziuk, W.S. Kendall, Combinatorial Laplacians and isoperimetric inequality, in: K.D. Elworthy (Ed.), From Local Times to Global Geometry, control and Physics, Research Notes in Mathematics Series, Vol. 150, Pitman, London, 1986, pp.68-74. 2 For ≥ 4, ℎΓ ≤ 1 2 − 1 . [2] J.Tan, On cheeger inequalities of a graph, Discrete Math. 269(2003) 315-323. Our Cheeger inequality provides an upper bound of the cheeger constant, which yields an improvement of the bound (), (). . [1] Let Γ be a distance regular graph. Then its edge-connectivity equals its valency , and the only disconnecting sets of edges are the sets of edges incident with a single vertex. [1] A.Brouwer, W.Haemers, Eigenvalues and perfect matchings, Linear Algebra and its Applications. 395 (2005). 155-162. . [2] Let Γ be a non-complete distance regular graph of valency > 2. Then the vertex-connectivity Γ equals , and the only disconnecting sets of vertices of size not more than are the point neighbourhoods. [2] A. Brouwer, J. Koolen, the vertex-connectivity of a distance regular graph, European Journal of Combinatorics. Vol. 30. No. 3. (2009). 668-673. . [3] Let Γ = (, ) be a simple graph with the vertex-connectivity Γ and the edge-connectivity (Γ). Then 2 Γ || ≤ 2(Γ) || || || || . 2 ≤ where is a subset of with || ≤ ≤ Γ ≤ (Γ), [3] G. Oshikiri, Cheeger constant and connectivity of graphs, Interdisciplinary Information Sciences, 8 (2) (2002), 147-150. From Propositions 1,2 and 3 we see that, for a distance regular graph, there are close connections between the Cheeger constant and vertex and edge connectivity. Also, we obtain an inequality 2 ≤ ℎΓ ≤ 1. || We are thus interested in finding optimal bounds of ℎΓ for distance regular graph. For our Cheeger inequality, we use the Green's function, which is defined as the inverse of the -Laplacian. Green’s function Define a transition probability matrix over by = 1 , where 1 1 1 is the valency of 1 . For a function ∶ → ℝ, we define a ∆ by ∆() = Then, we have ∆= − = − 1 1 − . ~ 1 1 1 and ∆ is a matrix representation of the Laplacian ℒ. For = 0,1, ⋯ , and orthogonal eigenfunction ∗ , we have ℒ= where is an eigenvalue of ℒ. =0 ∗ , Let ℒ be the –normalized Laplacian by + ℒ. For > 0, let a Green’s function denote the symmetric matrix satisfying ℒ = . Then we have = 1 =0 + ∗ , For > 0 we have ( + − ) = . Thus, this implies that ℒ =( + 1) − = =0( +1− 1 1 1 ) . Hence, a Green’s function can be expressed by 1 =0( +1 − 1 1 = Since = 1 || ) . , is a linear combination of adjacency matrices as follows: = 0 where () = 1 1 () ( + 1 0 + 1 1 +1 () 1 + ⋯ + + ⋯ + () 1 ) + , ( = 0,1, ⋯ , ) Let be a ( − 1) × || matrix obtained by the removal of the first row of 1 ℒ =( + 1) − 1 . 1 Since the Bose-Mesner algebra is isomorphic to the intersection algebra of 1 1 then that isomorphism of algebra takes ( + 1) − 1 to ( + 1) − 1 . Let ′ = −1 ( + 1 − matrix. Let () 1 − 1 + 1 , which is a + 1 × + 1 be a matrix obtained by the removal of the first row of ′ . Then, we obtain 1 )= 1 1 1 1 () as follows: () where = − 1 ( + 1) for = 1,2, ⋯ , and , , are the same entries as in 1 . . For > 0, let be a Green’s function for a –polynomial scheme. Then we have the following: () A Green’s function can be expressed as = 0 () 0 + 1 for some nonzero ∈ ℝ, where (0 basis () () () 1 + ⋯ + , 1 () , ⋯ , () () of the nullspace (() ) of() with =1 1. () For > 0, 0 0 + 1 1 + ⋯ + = , where is the valency of for = 0, 1, ⋯ , . () 0 () > 1 () () As → 0+ , 0 > ⋯ > () ≈ 1 () > 0. ≈ ⋯ ≈ . () ) is the unique For > 0, let be a Green’s function of the distance regular graph of order We denote a subset of 0,1,2, ⋯ , by ≔{ | 1 − > 0}. It is clear that is a non-empty set. When is sufficiently close to 0+ , we consider a set ′ = Since + 1 < 1 + = 1 + 1 lim+ →0 Thus, we have 1 ⇒ + 1 < 1 }. + ⋯ + () 1 < 1 ( − + ) , = 1. − > 0. That is, ′ is a subset of . and . For > 0, let Γ be a distance regular graph of order and let () () = 0 0 + 1 for ∈ ′ , we have (a) 2 1− 1 + ⋯ + be a Green’s function of Γ. Then, is decreasing in ∈ ′ ′ () For ∈ , lim+ 2 →0 1− = , where = Moreover, for some ∈ ′ , < 1 . () 2 1− is decreasing in > 0. 1 −1 1 − 1 ⋯ − 1 . - A Cheeger inequality of a distance regular graph . Let Γ be a distance regular graph of diameter and let 1 be the smallest positive eigenvalue of the Laplacian. Then 1 ℎΓ < < −1 < ⋯ < 1 . . Let be a subset of vertices of Γ with () ≤ (Γ)/2. Let 1− = 1 . Then we have lim+ →0 number such that < () 1− 1− = 0+ . Let be a positive . Then 1 − < () ⇒ 1− ′ + Let = . Since lim+ = 0 , we have ′ < →0 () ⇒ () < 1 ()( ′ ) ′ ′ 1− ′ < ⇒ ′ 2 ′ 1− ′ () ′ ′ ⇒ < 2 ′ 1− ′ < ′ ′ 2 ′ 1− ′ 1− 1 ′ ′ ′ . Since 1 < () and < 1 . Therefore 2 ′ Since > 2 ′ 1− ′ ′ 1− ′ ′ ′ ′ > () 1− 1 = = , we can choose = 1 () ≥ ℎΓ 1 . and < −1 < ⋯ < 1 , we have 1 ℎΓ < < −1 < ⋯ < 1 . ∎ . Let Γ be a distance regular graph and let ℎΓ be a Cheeger constant of Γ . Then we have ℎΓ < ≤ 1 2 − 1 ≤ 21 , 1 where 1 is a smallest positive eigenvalue of the Laplacian. Let Γ be the Hamming graph (, ). Then Γ is a distance regular graph with vertices, valency ( − 1) and diameter. We consider two cases: = 3, = 2 and = 5, = 2. Then 2 3 3,2 ∶ = 8, 1 = 3, 1 = , = ℎΓ < 1 ≈ 0.545455 < 4 11 1 2 − 1 = 0.942809 < 2 5 5,2 ∶ = 32, 1 = 5, 1 = , = ℎΓ < 1 ≈ 0.437956 < . 24 137 1 2 − 1 = 0.8 < 21 = 1.1547. . 21 = 0.894427. graph with Let Γ be the Johnson graph (, ). Then Γ is a distance regular vertices, valency ( − ) and diameter. We consider two cases: = 10, = 4 and = 11, = 5. Then 10,4 ∶ = 210, 1 = 24, 1 = ℎΓ < 1 ≈ 0.429302 < 1 ≈ 0.382344 < = 11088 79091 1 2 − 1 = 0.773879 < 11,5 ∶ = 462, 1 = 30, 1 = ℎΓ < 11 , 30 10 , 24 = 105 587 1 2 − 1 = 0.812233 < . 21 = 0.856349. . 21 = 0.912871. In fact, is 1 −1 1 − 1 ⋯ − 1 , where 1 , ⋯ , are the -numbers of a -polynomial scheme. However, in general, the -numbers are not easy to compute. We thus find an approximated value of with some error > 0 in the following theorem. If is sufficiently close to 0 then we obtain the estimate which is close to and easier to compute. 1 () . Let Γ be a distance regular graph of order , and let = 0 1 + ⋯ + () be a Green’s function of Γ for > 0. Then we have − 1 − < . 0 + () For > 0, let 0 () be the × matrix obtained by the removal of the first () column of . Let () be the ( − ) × − matrix obtained by the removal from the first row(respectively, column) to the –th row(respectively, column) of 0 () In the following proposition 5, we find an expression for in terms of a basis (0 () , 1 () , ⋯ , () ) of ( We also find an explicit expression for () of () . () () ) and the valencies ’s. And by a determinant of a submatrix . () Let Γ be a distance regular graph of order . For > 0, let () () () (0 , 1 , ⋯ , ) be a basis of ( ) with be a Green’s function of Γ. Then we have the following: = lim+ , () →0 () where =0 = (−1)− () = 1, and let − det( ) +1 +2 ⋯ , = 0,1, ⋯ , − 1, are submatrices of () and det = 1. We consider a Johnson scheme (8,4) . Let Γ be a distance regular graph with respect to 1 . Then Γ is a distance regular graph with 70 vertices and valency 16 . Also, the valencies of (8,4) are 1, 16, 36, 16, 1 and () Since = 1 −1 1 − 1 ⋯ − 1 , 8 14 18 20 , , ), 16 16 16 16 (1 4 , ⋯ ,4 4 ) = (−7,20, −28,14) and 1 , ⋯ , 4 = ( , have = Let = (0 315 1522 1 . 1000 () , 1 we ≈ 0.206965. By proposition 5, a basis for ( () ,2 () , 3 () , 4 () )= () ) is 263196691 15762389 94021 1001 , , , ,1 244140625 15625000 93750 1000 . Thus, we have (70) 1 0 () + 16 1 () + 36 2 1 1000 () + 16 3 () + 1 4 () − 70 ≈ 0.206609. Also, by Theorem 4, we have − < 0.001 and < ≈ 0.206609 + 0.001 = 0.207609. Let be the set of × matrices over ( ) ( ≤ ). Define the –th relation on by , ∈ ⇔ − = . Then = , (0 ≤ ≤ ) is a -polynomial scheme with respect to the ordering 0 , 1 , ⋯ , . Let = 2, = 1, = 4, = 5. Then, () is as follows: Also, we have = = 1048576, 0 = 1, 1 = 465, 2 = 32550, 3 = 390600 ⋯ and 4 = 624960 by using = 1 1 2 −1 = 2,3, ⋯ , . 2 3 ⋯ 1 Let = . Then by Proposition 5, we obtain the unique basis of( 100 as follows: (0 () , 1 () ,2 () , 3 () , 4 () )= 3921317781669 486743013 661683 831 , , , ,1 358400000 17920000 448000 800 . () ) Thus, we have (1048576) 1 0 () + 465 1 () + 32550 2 () 1 100 + 390600 3 () + 624960 4 () − 1048576 ≈ 0.195023. Also, by Theorem 4, we have < ≈ 0.195023 + 0.01 = 0.205023. Let Γ be a distance regular graph with respect to 1 . Since an eigenvalue 1 of the Laplacian is ℎΓ < 256 , 465 we obtain ℎΓ < ≈ 0.372405 < 1 1 < 1 ≈ 0.372405. Moreover, 1 2 − 1 = 0.893299 < 21 = 1.04932. - Explicit expression of the krawtchouk polynomial For > 0, let be a Green’s function for a –polynomial scheme. Then we have A Green’s function can be expressed as = 0 () 0 + 1 () 1 + ⋯ + for some nonzero ∈ ℝ, where is the (0 the nullspace ( () ) of () () with , 1 () () , ⋯ , () ) unique basis of = 1. () where = − 1 ( + 1) for = 1,2, ⋯ , and , , are the same entries as in 1 . A Green's function is defined only for > 0, and is expressed as a linear combination of adjacency matrices . But, for ≤ 0, may be a singular matrix, so there is no Green's function notion for this case. We however still have ( (0 () , 1 () , ⋯ , () () ) = for ∈ ℝ, so we can obtain a unique basis ) of ( () ) with () = 1. We extend a notion of a Green's function associated with any real number as follows. The following definition plays an important role for computation of the number and the -number. with () . For ∈ ℝ , let (0 () , 1 () = 1 and let () () , ⋯ , () )∈ ( () ) , = 0 0 + 1 1 + ⋯ + , where is some nonzero ∈ ℝ if > 0 and = 1 if ≤ 0. Then , is called The normalized Green’s function. Let (5,3) be a Hamming scheme . Choosing = − obtain a 5 × 6 matrix () as follows: 40 () 1 , 10 26 1 1 4 Also, a basis of ( ) is (− , − , − , , , 1). 3 15 15 2 5 Thus we obtain a normalized Green’s function , as follows: , = − 40 3 0 − 26 15 1 − 1 15 2 1 2 4 5 + 3 + 4 + 5 , where ( = 0,1,2, ⋯ , 5) are the adjacency matrices of 5,3 . then we For some ∈ ℝ, let (0 () , 1 () , ⋯ , () ) be a basis of ( ) Let = , ( = 0,1, ⋯ , ) be a -polynomial scheme, and let = ( ) (respectively, Q= ( ) ) be the first eigenmatrix (respectively, the second eigenmatrix) of . In the following proposition 6, we show that the -th column vector of the second eigenmatrix Q belongs to ( ( ) 1 1 () ) for = − 1 (j = 0,1,2, ⋯ , ) . That is, we show the relationship between and component of the second eigenmatrix Q= ( ) over the - polynomial scheme. Let = , = 1 1 ( = 0,1, ⋯ , ) be a -polynomial scheme. For − 1 j = 0,1,2, ⋯ , , let , = 0 a normalized Green’s function with () 0 + 1 () 1 + ⋯ + = 1. Then satisfy = be 0 () () ( = 0,1, ⋯ , ). That is, the -th column of the second eigenmatrix Q= ( ) is equal to 0 () (0 () , 1 () , ⋯ , Moreover, we have = () ) , where is the -th multiplicity of . () . By Proposition 5 (b), () = (−1)− where det( ) +1 +2 ⋯ , = 0,1, ⋯ , − 1, are submatrices of ( ) and det = 1. Let (, ) be a Hamming scheme. Since the Hamming scheme is a self-dual scheme, = ( ) is equal to Q= ( ) . The -number of a Hamming scheme (, ) is defined by the Krawtchouk polynomial. Thus, we have 1 = − 1 − . And, 1 = − 1 . Thus = 1 1 −1= −1 −− −1 −1 =− (−1) . For = − , (−1) we have a matrix ( ) as follows: where = − 2 − ( − 1)( + 1) for = 1,2, ⋯ , , and = ( − )( − 1) for = 1,2, ⋯ , − 1. . Let , a Hamming scheme. Let submatrix of ( ) for = − −1 = () be an ( − ) × ( − ) (j = 0,1,2, ⋯ , ). Then we have = !det( (−1)+− ! ) . . Let (5,3) be a Hamming scheme. Then, the first eigenmatrix = ( ) is as follows: Let = 1, then we obtain the -number 1 as the entries of the second column of the first eigenmatrix . Let (1 ) be a 5 × 6 matrix for 1 = − 3 1 5 3−1 =− 3 10 as follows: Then, the matrices 0 Also, det 0 − 4, det 4 1 1 1 , 1 1 , 2 = 240 , det 1 1 1 , 3 1 and 4 1 = −168, det 2 are 1 = −2. Therefore, 1 ( = 0,1,2,3,4) are = 48, det 3 1 = respectively. Thus, (10,7,4,1, −2, −5) is the first column vector of the first eigenmatrix . Thank you