# Beneš Conjecture

 Importance: High ✭✭✭
 Author(s): Beneš, Václav E.
 Subject: Combinatorics
 Keywords:
 Posted by: Vadim Lioubimov on: January 3rd, 2010

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

This conjecture was essentially proposed by Václav E. Beneš in [B75] and bears his name.

A partition of a set is uniform if all its blocks have the same size. Given a subset of a multiplicative group and a positive integer , by we mean the set ( times). A set is transitive if for every there exists a permutation such that . The infinum of two partitions and of is the partition of defined by The partition of is defined by . So the condition is equivalent to saying that for every pair of blocks , the intersection consists of at most one element.

Observe that the decomposition is equivalent to universality of the sequence due to the obvious identity . Thus Problem () is indeed underlying for Beneš conjecture.

Problem () is the central case of a broader fundamental problem of characterization of product of stabilizers on a finite set. The latter problem, which I believe is combinatorial by nature, is of great interest in switching network theory. However, despite many years of extensive research on its various cases in the context of switching networks, this fascinating problem remains unsolved in all but a very few interesting instances. Very little is understood about such products beyond what is obvious. In particular, it is unclear how to efficiently compute their cardinalities. Even for some rather simple sequences of partitions, the product of their stabilizers is surprisingly difficult to characterize. Beneš conjecture, if proven (even under some additional assumptions on ), would provide a very useful and easy-to-check sufficient condition for universality of the sequences that are of particular interest.

Another important and interesting problem related to () is to find an efficient polynomial-time (in ) factorization algorithm for identity (1). Given an identity , where all are subsets of a multiplicative group, a factorization algorithm finds for every an -tuple such that .

Beneš conjecture is mainly famous for its central case, Shuffle-Exchange (SE) conjecture, stating essentially that , where is an instance of defined, given arbitrary integer parameters , as follows:

\item is the set of all words of length over a -letter alphabet. \item is the partition of formed by the equivalence relation on defined by . \item is the shuffle permutation of defined by .

Whereas SE conjecture, especially its case , has received enormous attention with relatively little progress, the general case of Beneš conjecture, despite importance of Problem (), has virtually generated no literature and had no progress. It remains open for all .

While I strongly believe in the validity of SE conjecture, I am not so sure about Beneš conjecture (without any additional assumptions on ) and even do not rule out that it could be disproved by a low-scale counterexample.

It is easy to see that the case of Beneš conjecture coincides with that of SE conjecture, which (the case) is well known to be valid (it is discussed here).

Unlike that of universality, the condition of transitivity is very easy to check. In particular, transitivity of the set with is equivalent to the following assertion:

Beneš conjecture (as well as its underlying Problem () and a broader problem of characterization of product of stabilizers on a finite set) admits a nice equivalent graph-theoretic form.

## Counterexamples

In what follows we present 3 counterexamples showing that certain 3 extensions of Beneš conjecture are false.

1. The condition is necessary for Beneš conjecture. This can be shown by the following simple counterexample: Indeed, as . Also, the set is obviously transitive. However, it can be easily seen that any permutation of satisfying does not belong to . Thus, . In fact, the condition is missing in the original statement [B75] of Beneš conjecture (however, such condition is commonly (but not always) assumed in the context of switching networks).

2. Beneš conjecture is not directly generalizable to products of stibilizers of the form . For that I constructed a counterexample of a unform 6-block partition of a 12-set and permutations of satisfying each such that the set is transitive but .

3. In the same paper [B75], Beneš proposed a stronger version of his conjecture by adding to it the following converse claim (in the context of Beneš conjecture): if is the smallest integer such that is transitive, then . However, this claim turned out to be generally false as I found several (non-trivial) counterexamples to it. The simplest one is with a 4-block partition of an 8-set such that is non-transitive while .

## Bibliography

*[B75] V.E. Beneš, Proving the rearrangeability of connecting networks by group calculation, Bell Syst. Tech. J. 54 (1975), 421-434.

* indicates original appearance(s) of problem.