Beneš, Václav E.

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

Author(s): Beneš

Problem ( $\dag$ ) Find a sufficient condition for a straight $\ell$ -stage graph to be rearrangeable. In particular, what about a straight uniform graph?

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.

Keywords:

Posted by Vadim Lioubimov
updated April 17th, 2010

add new comment | 3 attachments

Combinatorics

Beneš Conjecture ★★★

Author(s): Beneš

Let $E$ be a non-empty finite set. Given a partition $\bf h$ of $E$ , the stabilizer of $\bf h$ , denoted $S(\bf h)$ , is the group formed by all permutations of $E$ preserving each block of $\mathbf h$ .

Problem ( $\star$ ) Find a sufficient condition for a sequence of partitions ${\bf h}_1, \dots, {\bf h}_\ell$ of $E$ to be complete, i.e. such that the product of their stabilizers $S({\bf h}_1) S({\bf h}_2) \dots S({\bf h}_\ell)$ is equal to the whole symmetric group $\frak S(E)$ on $E$ . In particular, what about completeness of the sequence $\bf h,\delta(\bf h),\dots,\delta^{\ell-1}(\bf h)$ , given a partition $\bf h$ of $E$ and a permutation $\delta$ of $E$ ?

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}.$

Keywords:

Posted by Vadim Lioubimov
updated January 3rd, 2010

add new comment

Combinatorics

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:=\sigma\frak G \sigma\frak G \dots \sigma\frak G$ ( $d$ times), where $\sigma\in \frak S$ is the shuffle permutation defined by $\sigma(x_1 x_2 \dots x_{n}) = x_2 \dots x_{n} x_1$ , and $\frak G$ is the exchange group consisting of all permutations in $\frak S$ preserving the first $n-1$ letters in the words.

Problem (SE) Evaluate $d(k,n)$ .

Conjecture (SE) $d(k,n)=2n-1$ , for all $k,n\ge2$ .

Keywords:

Posted by Vadim Lioubimov
updated November 27th, 2009

add new comment

Graph Theory

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

Author(s): Beneš; Folklore; Stone

Given integers $k,n \ge 2$ , the 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 $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).