Short reachability networks

Abstract: We investigate a generalisation of permutation networks. We say a sequence

T = (T_{1}, d o t s, T_{e} l l)

of transpositions in

S_{n}

forms a

t

-reachability network if for every choice of

t

distinct points

x_{1}, d o t s, x_{t} i n 1, d o t s, n

, there is a subsequence of

T

whose composition maps

j

to

x_{j}

for every

1 l e q j l e q t

. When

t = n

, then any permutation in

S_{n}

can be created, and

T

is a permutation network. Waksman [JACM, 1968] showed that the shortest permutation networks have length about

n l o g_{2} n

. In this paper, we investigate the shortest

t

-reachability networks. Our main result settles the case of

t = 2

: the shortest

2

-reachability network has length

l c e i l 3 n / 2 c e i l - 2

. For fixed

t

, we give a simple randomised construction which shows there exist

t

-reachability networks using

(2 + o_{t} (n)) n

transpositions. We also study the case where all transpositions are of the form

(1, c d o t)

, separating 2-reachability from the related probabilistic variant of 2-uniformity. Many interesting questions are left open.

This page was built for publication: Short reachability networks