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š

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:

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:

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