论文标题
较短的可及性网络
Short reachability networks
论文作者
论文摘要
我们研究置换网络的概括。我们说一个序列$ t =（t_1，\ dots，t_ \ ell）$ s_n $中的换位$，如果每一个选择$ t $ difters $ x_1，\ dots，x_t \ in \ in \ in \ {1，\ dots，n \} $ j $ t $ t $ t $ t $ t $ $ 1 \ leq j \ leq t $。当$ t = n $时，可以创建$ s_n $中的任何排列，而$ t $是一个排列网络。 Waksman [JACM，1968年]表明，最短的排列网络的长度约为$ n \ log_2n $。在本文中，我们研究了最短的$ t $ reachability网络。我们的主要结果解决了$ t = 2 $的情况：最短的$ 2 $ -Reachability网络具有长度$ \ lceil 3n/2 \ rceil-2 $。对于固定的$ t $，我们提供了一个简单的随机结构，该结构表明使用$（2+o_t（n））n $ transosions存在$ t $ reachability网络。我们还研究了所有换位均为$ $（1，\ cdot）$的情况，将2个可持续性与2-均匀性的相关概率变体分开。许多有趣的问题将打开。
We investigate a generalisation of permutation networks. We say a sequence $T=(T_1,\dots,T_\ell)$ of transpositions in $S_n$ forms a $t$-reachability network if for every choice of $t$ distinct points $x_1, \dots, x_t\in \{1,\dots,n\}$, there is a subsequence of $T$ whose composition maps $j$ to $x_j$ for every $1\leq j\leq t$. When $t=n$, 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 \log_2n$. 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 $\lceil 3n/2\rceil-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, \cdot)$, separating 2-reachability from the related probabilistic variant of 2-uniformity. Many interesting questions are left open.
