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:

Beneš Conjecture ★★★

Author(s): Beneš

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

Problem  ($ \star $)   Find a sufficient condition for a sequence of partitions $ {\bf h}_1, \dots, {\bf h}_\ell $ of $ E $ to be 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 $?
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:

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 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)   Find $ d(k,n) $.
Conjecture  (SE)   $ d(k,n)=2n-1 $.

Keywords:

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).

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

Problem   Find $ r(k,n) $.
Conjecture   $ r(k,n)=2n-1 $.

Keywords:

Syndicate content