# Beneš, Václav E.

## Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

\begin{problem}[$\dag$] Find a sufficient condition for a straight $\ell$-stage graph to be rearrangeable. In particular, what about a straight uniform graph? \end{problem}

\begin{conjecture}[$\diamond$] Let $L$ be a simple regular ordered $2$-stage graph. Suppose that the graph $L^m$ is externally connected, for some $m\ge1$. Then the graph $L^{2m}$ is rearrangeable. \end{conjecture}

Keywords:

## Beneš Conjecture ★★★

Author(s): Beneš

Given a partition $\bf h$ of a finite set $E$, \emph{stabilizer} of $\bf h$, denoted $S(\bf h)$, is the group formed by all permutations of $E$ preserving each block in $\mathbf h$.

\begin{problem}[$\star$] Find a sufficient condition for a sequence of partitions ${\bf h}_1, \dots, {\bf h}_\ell$ of $E$ to be \emph{universal}, i.e. to yield the following decomposition of the symmetric group $\frak S(E)$ on $E$: $$(1)\quad \frak S(E) = S({\bf h}_1) S({\bf h}_2) \dots S({\bf h}_\ell).$$ In particular, what about the sequence $\bf h,\delta(\bf h),\dots,\delta^{\ell-1}(\bf h)$, where $\delta$ is a permutation of $E$? \end{problem}

\begin{conjecture}[Beneš] Let $\bf u$ be a uniform partition of $E$ and $\varphi$ be a permutation of $E$ such that $\bf u\wedge\varphi(\bf u)=\bf 0$. Suppose that the set $\big(\varphi S({\bf u})\big)^{n}$ is transitive, for some integer $n\ge2$. Then $$\frak S(E) = \big(\varphi S({\bf u})\big)^{2n-1}.$$ \end{conjecture}

Keywords:

## Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers $k,n\ge2$, let $d(k,n)$ be the smallest integer $d\ge2$ such that the symmetric group $\frak S$ on the set of all words of length $n$ over a $k$-letter alphabet can be generated as $\frak S = (\sigma \frak G)^d$, where $\sigma\in \frak S$ is the \emph{shuffle permutation} defined by $\sigma(x_1 x_2 \dots x_{n}) = x_2 \dots x_{n} x_1$, and $\frak G$ is the \emph{exchange group} consisting of all permutations in $\frak S$ preserving the first $n-1$ letters in the words.

\begin{problem}[SE] Find $d(k,n)$. \end{problem}

\begin{conjecture}[SE] $d(k,n)=2n-1$. \end{conjecture}

Keywords:

## Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers $k,n \ge 2$, the \emph{2-stage Shuffle-Exchange graph/network}, denoted $\text{SE}(k,n)$, is the simple $k$-regular bipartite graph with the ordered pair $(U,V)$ of linearly labeled parts $U:=\{u_0,\dots,u_{t-1}\}$ and $V:=\{v_0,\dots,v_{t-1}\}$, where $t:=k^{n-1}$, such that vertices $u_i$ and $v_j$ are adjacent if and only if $(j - ki) \text{ mod } t < k$ (see Fig.1).

Given integers $k,n,r \ge 2$, the \emph{$r$-stage Shuffle-Exchange graph/network}, denoted $(\text{SE}(k,n))^{r-1}$, is the proper (i.e., respecting all the orders) concatenation of $r-1$ identical copies of $\text{SE}(k,n)$ (see Fig.1).

Let $r(k,n)$ be the smallest integer $r\ge 2$ such that the graph $(\text{SE}(k,n))^{r-1}$ is rearrangeable.

\begin{problem} Find $r(k,n)$. \end{problem}

\begin{conjecture} $r(k,n)=2n-1$. \end{conjecture}

Keywords: