### PPTX

```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   .
= =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
```