Information Technology Reference
In-Depth Information
For random variables
X
and
Y
, taking values in finite sets according to some joint
distribution, and
y
(
)
support
Y
,let
X
y
be the random variable taking values in
support
(
X
)
such that Pr
[
X
y
=
x
]=
Pr
[
X
=
x
|
Y
=
y
]
. Then, the conditional
entropy of
X
given
Y
is
H
[
X
|
Y
]=
Pr
[
Y
=
y
]
H
[
X
y
]
.
y
support
(
Y
)
We will use of the following standard facts about entropy [
CT91
].
H
[
X
]
log
2
|
support
(
X
)
|;
k
H
[
X
1
X
2
...
X
k
|
Y
]=
H
[
X
i
|
X
1
X
2
...
X
i
−
1
Y
]
.
i
=
1
10.3 Moore Bound for Irregular Graphs
In Sect.
10.3.1
, we recall the proof of theMoore bound; in Sect.
10.3.2
, we review and
reprove the theorem of Alon et al. [
AHL02
] assuming Lemma 3.4. In Sect.
10.3.3
,
we prove this lemma using an entropy- based argument.
10.3.1 Proof of the Moore Bound
The Moore bound provides a lower bound for the order of a graph in terms of its
minimum degree and girth.
Theorem 3.1
(The Moore bound [
Big93
, p. 180])
Let G be a simple undirected
graph with n vertices, minimum degree
δ
and girth
g
.
r
−
1
i
.
Odd girth
If
g
=
2
r
+
1
, then n
≥
1
+
δ
0
(δ
−
1
)
i
=
r
−
1
i
Even girth
If
g
=
2
r, then n
≥
2
0
(δ
−
1
)
.
i
=
The key observation in the proof of the Moore bound is the following. If the girth
is 2
r
+
1, then two distinct nonreturning walks of length at most
r
starting at a vertex
v
lead to distinct vertices. Similarly, if the girth is 2
r
, then nonreturning walks of
length at most
r
starting with (some directed version of) an edge
e
lead to distinct
vertices. We will need this observation again later, so we record it formally.
Let G be an undirected simple graph with n vertices and girth
g
.
Observation 3.2
