Information Technology Reference
In-Depth Information
Let
g
=
+
v
Odd girth
2
r
1
. Then, for all vertices
,
n
≥
n
0
(v)
+
n
1
(v)
+···+
n
r
(v).
Even girth
Let
g
=
2
r. Let e be an edge of G and suppose
∃
e
1
and
∃
e
2
are its directed
versions in G. Then,
r
−
1
n
≥
0
[
n
i
(
∃
e
1
)
+
n
i
(
∃
e
2
)
]
.
i
=
Proof of Theorem 3.1
The claim follows immediately from Observation 3.2 by not-
ing that for such a graph
G
, for all vertices
E
,
v
V
and edges
∃
e
i
−
1
n
i
(v)
≥
δ(δ
−
1
)
(for
i
≥
1)
,
n
0
(v)
=
1
;
(10.1)
i
n
i
(
∃
e
)
≥
(δ
−
1
)
(for
i
≥
0)
.
(10.2)
∩
10.3.2 The Alon-Hoory-Linial Bound
Alon, Hoory, and Linial showed that the bound in Theorem 3.1 holds for any undi-
rected graph even when the minimum degree
δ
is replaced by the average degree
d
.
Theorem 3.3
(Alon et al. [
AHL02
])
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
.
If
g
=
+
≥
−
)
Odd girth
2
r
1
, then n
1
1
i
=
r
−
1
0
(
d
i
.
Even girth
If
g
=
2
r, then n
≥
2
−
1
)
i
=
We will first prove this theorem assuming the following lemma, which is the main
technical part of Alon et al. [
AHL02
]. This lemma shows that the bounds (
10.1
) and
(
10.2
) holds with
δ
replaced by
d
. In Sect.
10.3.3
, we will present an information
theoretic proof of this lemma.
Lemma 3.4
Let G be an undirected simple graph with n vertices, girth
g
, minimum
degree at least two and average degree d.
(a)
If
v
V
(
G
)
is chosen with distribution
π
, where
π(v)
=
d
v
/(
2
|
E
(
G
)
|
)
=
v
/(
dn
n
i
(v)
]≥
d
(
d
i
−
1
d
)
, then
E[
−
1
)
(
i
≥
1
)
.
e is a uniformly chosen random edge in E, then
)
]≥
(
d
i
(b)
If
∃
E[
n
i
(
∃
e
−
1
)
(
i
≥
0
)
.
