Information Technology Reference
In-Depth Information
Chapter 10
An Entropy-Based Proof for the Moore
Bound for Irregular Graphs
S. Ajesh Babu and Jaikumar Radhakrishnan
Abstract
We provide proofs of the following theorems by considering the entropy
of random walks.
Theorem 1
(Alon, Hoory and Linial)
Let G be an undirected simple graph with n
vertices, girth
g
,
minimum degree at least
2
and average degree d
.
r
−
1
+
d
0
(
d
i
.
Odd girth
If
g
=
2
r
+
1,
then n
≥
1
−
1
)
i
=
r
−
1
0
(
d
i
.
Even girth
If
g
=
2
r
,
then n
≥
2
−
1
)
i
=
Theorem 2
(Hoory)
Let G
=
(
V
L
,
V
R
,
E
)
be a bipartite graph of girth
g
=
2
r
,
with
n
L
=|
V
L
|
and n
R
=|
V
R
|
,
minimum degree at least
2
and the left and right average
degrees d
L
and d
R
.
Then
,
r
−
1
i
2
ↆ
i
2
∈
)
∗
)
≤
n
L
≥
0
(
d
R
−
(
d
L
−
,
1
1
i
=
r
−
1
i
2
ↆ
(
i
2
∈
.
)
∗
)
≤
n
R
≥
0
(
d
L
−
1
d
R
−
1
i
=
This work was done while S. Ajesh Babu was at School of Technology and Computer Science,
Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India.
