Information Technology Reference
In-Depth Information
The graph consisting of paths from inputs in
I
t
to the outputs of
SC
1
(
k
)
constitutes a
2
k
-superconcentrator. Prior to time
t
a
there are at most
c
2
2
k
+
1
pebbles on the graph and
during the interval
[
t
1
,
t
2
]
there are at least
c
2
2
k
(but at most
c
2
2
k
+
1
) pebbles on the graph.
Thus, there is a latest time
t
0
before
t
1
when there are at most
c
2
2
k
+
1
pebbles on the graph.
Since
c
3
2
k
c
2
2
k
+
1
+
1outputsof
SC
1
(
k
)
are pebbled in the interval
[
t
1
,
t
2
]
(and in
the interval
[
t
0
,
t
2
]
), by Problem
10.27
at time
t
0
there are at least 2
k
≥
c
3
2
k
inputs in
I
t
(and in
I
b
) that are connected by pebble-free paths to the pebbled outputs of
SC
1
(
k
)
. Thus, at least
c
3
2
k
+
1
inputs in
I
t
and
I
b
are connected via pebble-free paths to the
pebbled outputs of
SC
1
(
k
)
.In
[
t
0
,
t
1
−
c
2
2
k
+
1
−
≥
1
]
there are at least
c
2
2
k
+
1
pebbles continuously
on the graph, whereas there are at least
c
2
2
k
pebbles during
[
t
1
,
t
2
]
.Since
c
2
2
k
c
4
2
k
+
1
,
the number continuously on the graph in
[
t
1
,
t
2
]
is at least
c
4
2
k
+
1
and we have the desired
conclusion for
H
(
k
+
1
)
.
In the third case, there is an interval
[
t
1
,
t
2
]
≥
[
t
a
,
t
b
]
during which at least
c
1
2
k
outputs
of the full graph
H
(
k
+
1
)
are pebbled and at least
c
2
2
k
pebbles are always on the graph. This
implies that during
[
t
1
,
t
2
]
either
c
1
2
k
/
2outputsin
O
t
or in
O
b
are pebbled, which in turn
implies that at least
c
1
2
k
/
2outputsof
SC
2
(
k
)
are pebbled. Since
c
1
2
k
/
2
⊆
c
2
2
k
+
1
+
1
(at most
c
2
2
k
+
1
pebbles are on
H
(
k
+
1
)
), it follows from Problem
10.27
that at least
2
k
≥
c
3
2
k
inputs in
I
t
(or
I
b
) are connected via pebble-free paths to the pebbled
outputs of
SC
2
(
k
)
. The total number of such inputs is
c
3
2
k
+
1
.Since
c
2
2
k
c
2
2
k
+
1
−
≥
c
4
2
k
+
1
,there
are at least
c
4
2
k
+
1
pebbles on the graph continuously during
[
t
1
,
t
2
]
and we have the desired
conclusion.
Inthefourthcasenoneofthepreviouscaseshold.Since
c
1
2
k
+
1
outputs of
H
(
k
+
1
)
are pebbled during
[
t
a
,
t
b
]
, there is an earliest time
t
1
≥
∈
[
t
a
,
t
b
]
such that
c
1
2
k
outputs of
H
(
k
+
1
)
are pebbled in the interval
[
t
a
,
t
1
−
1
]
. Since the third case does not hold, there
is a time
t
2
≤
t
1
such that fewer than
c
2
2
k
pebbles are on the graph at
t
2
−
1 and at least
c
1
2
k
outputs of
H
(
k
+
1
)
are pebbled in the interval
[
t
2
,
t
b
]
. It follows that at least
c
1
2
k
/
2
outputs of
SC
2
(
k
)
are pebbled during this interval. Since
c
1
2
k
/
2
c
2
2
k
+
1, it follows
≥
from Problem
10.27
that at least 2
k
c
3
2
k
inputs to
SC
2
(
k
)
(which are outputs to
H
2
(
k
)
) are connected via pebble-free paths to the pebbled outputs of
SC
2
(
k
)
and must be
pebbled during
[
t
2
,
t
b
]
.Since
c
3
2
k
c
2
2
k
−
≥
c
1
2
k
, by the inductive hypothesis there is an interval
≥
[
t
2
,
t
b
]
during which at least
c
3
2
k
inputs of
H
2
(
k
)
(which are outputs of
H
1
(
k
)
)
are pebbled and
c
4
2
k
pebbles reside continuously on
H
2
(
k
)
.
Since the second case does not hold, by an argument paralleling that given in the pre-
ceding paragraph there must be a time
t
3
[
t
d
,
t
e
]
⊆
[
t
d
,
t
e
]
such that at most
c
3
2
k
/
2outputsof
∈
H
1
(
k
)
are pebbled during
[
t
d
,
t
3
−
1
]
and fewer than
c
2
2
k
pebbles reside on
H
(
k
+
1
)
at
t
c
−
c
1
2
k
outputs of
H
1
(
k
)
are pebbled from
an initial configuration of fewer than
c
2
2
k
pebbles. By the inductive hypothesis there is an
interval
[
t
f
,
t
g
]
1. Thus, during
[
t
3
,
t
e
]
at least
c
3
2
k
/
2
≥
[
t
3
,
t
e
]
during which at least
c
3
2
k
inputs of
H
1
(
k
)
(which are outputs of
SC
1
(
k
)
) are pebbled and
c
4
2
k
pebbles reside on
H
1
(
k
)
continuously.
Since the first case does not hold, again paralleling an earlier argument there must be a
time
t
4
⊆
[
t
f
,
t
g
]
such that at most
c
3
2
k
/
2outputsof
SC
1
(
k
)
are pebbled during
[
t
f
,
t
4
∈
−
1
]
and fewer than
c
2
2
k
pebbles reside on
H
(
k
+
1
)
at
t
4
−
1. Thus, during
[
t
4
,
t
g
]
at least
c
3
2
k
/
2
c
2
2
k
+
1outputsof
SC
1
(
k
)
are pebbled from an initial configuration of fewer
than
c
2
2
k
pebbles. By Problem
10.27
at least 2
k
≥
c
3
2
k
inputs of
SC
1
(
k
)
are
connected via pebble-free paths to the pebbled outputs. Thus at least
c
3
2
k
corresponding
inputs in both
I
t
and
I
b
must be pebbled for a total of at least
c
3
2
k
+
1
inputs.
c
2
2
k
−
≥
Search WWH ::
Custom Search