Information Technology Reference
In-Depth Information
10.4.1 The Hoory Bound
Theorem 4.1
(Hoory [
Hoo02
])
Let G
=
(
V
L
,
V
R
,
E
)
be a bipartite graph of girth
g
=
, minimum degree at least
2
and the left and
right average degrees d
L
and d
R
. Then,
2
r, with n
L
=|
V
L
|
and n
R
=|
V
R
|
r
−
1
2
ↆ
(
2
∈
,
)
∗
)
≤
n
L
≥
0
(
d
R
−
1
d
L
−
1
i
=
r
−
1
2
ↆ
(
2
∈
.
)
∗
)
≤
n
R
≥
0
(
d
L
−
1
d
R
−
1
i
=
For bipartite graphs the girth is always even. We then have the following variant
of Observation 3.2.
Observation 4.2
Let G
=
(
V
L
,
V
R
,
E
)
be an undirected bipartite graph with
|
V
L
|=
n
L
and
|
V
R
|=
n
R
and girth
g
=
2
r. Let e be an edge of G and suppose
∃
e
1
and
∃
e
2
be
its directed versions in G, such that
e
1
E
LR
and
e
2
E
RL
. Then,
∃
∃
r
2
∈−
r
2
ↆ−
≤
1
∗
1
n
L
≥
n
2
i
+
1
(
∃
e
1
)
+
n
2
i
(
∃
e
2
).
i
=
0
i
=
0
We will prove the Theorem 4.1, assuming the following lemma, which is the main
technical part of Hoory [
Hoo02
]. In Sect.
10.4.2
, we will present the proof of this
lemma using the language of entropy.
Lemma 4.3
be an undirected simple bipartite graph with n
L
vertices on the left and n
R
vertices on the right, girth
g
, minimum degree at least two
and average left and right degrees, respectively d
L
and d
R
.
Let G
=
(
V
L
,
V
R
,
E
)
E
LR
,
(a)
If
∃
e
is
a
uniformly
chosen
random
edge
in
then
E[
n
2
i
+
1
(
∃
e
)
]≥
i
+
1
i
(
d
R
−
1
)
(
d
L
−
1
)
(
i
≥
1
)
.
E
RL
,
(b)
If
∃
e
is
a
uniformly
chosen
random
edge
in
then
E[
n
2
i
(
∃
e
)
]≥
i
i
(
d
R
−
1
)
(
d
L
−
1
)
(
i
≥
1
)
.
Proof of Theorem 4.1
We will prove the bound for
n
L
. The proof for
n
R
case is
similar. Let
e
1
be chosen uniformly at random from
E
LR
and let
∃
∃
e
2
be its companion
edge (going in the opposite direction). Note that
e
2
is also uniformly distributed in
E
RL
. Then, from Observation 4.3, Lemma 4.3 and linearity of expectation we obtain
∃
⊡
⊤
r
2
∈−
r
2
ↆ−
≤
1
∗
1
r
−
1
2
ↆ
(
2
∈
.
⊣
⊦
≥
)
∗
)
≤
n
L
≥ E
n
2
i
+
1
(
∃
e
1
)
+
n
2
i
(
∃
e
2
)
0
(
d
R
−
1
d
L
−
1
∩
i
=
0
i
=
0
i
=
