# Beneš, Václav E.

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

Author(s): Beneš

Problem  ()   Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ()   Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.

Keywords:

## Beneš Conjecture ★★★

Author(s): Beneš

Given a partition of a finite set , stabilizer of , denoted , is the group formed by all permutations of preserving each block in .

Problem  ()   Find a sufficient condition for a sequence of partitions of to be universal, i.e. to yield the following decomposition of the symmetric group on : In particular, what about the sequence , where is a permutation of ?
Conjecture  (Beneš)   Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then

Keywords:

## Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as ( times), where is the shuffle permutation defined by , and is the exchange group consisting of all permutations in preserving the first letters in the words.

Problem  (SE)   Evaluate .
Conjecture  (SE)   , for all .

Keywords:

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

Author(s): Beneš; Folklore; Stone

Given integers , the 2-stage Shuffle-Exchange graph/network, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).

Given integers , the -stage Shuffle-Exchange graph/network, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).

Let be the smallest integer such that the graph is rearrangeable.

Problem   Find .
Conjecture   .

Keywords: