Beneš Conjecture

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

Let be a non-empty finite set. Given a partition of , the stabilizer of , denoted , is the group formed by all permutations of preserving each block of .

Problem  ()   Find a sufficient condition for a sequence of partitions of to be complete, i.e. such that the product of their stabilizers is equal to the whole symmetric group on . In particular, what about completeness of the sequence , given a partition of and 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 1975 [B75] and bears his name. It remains open for all .

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 product ( 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 completeness of the sequence due to the obvious identity . Thus Problem () is indeed underlying for Beneš conjecture.

Problem () is a special case of a broader fundamental problem of description 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 study. 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 describe. Beneš conjecture, if proven (even under some additional assumptions on ), would provide a very useful and easy-to-check sufficient condition for completeness 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 the identity . 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:

is the set of all words of length over a -letter alphabet .

is the -partition of formed by the equivalence relation on defined by

.

is the shuffle permutation of defined by .

Whereas SE conjecture, especially its case , has received enormous attention in the study of switching networks with relatively little progress, the general case of Beneš conjecture, despite importance of Problem () in that area, has virtually generated no literature and had no progress. While I strongly believe in the validity of SE conjecture, I am not so sure about the general case of Beneš conjecture and even do not rule out that it could be disproved by a low-scale counterexample. On the other hand, I cannot rule out that Beneš conjecture (possibly under some mild additional assumptions on ) may be reduced to SE conjecture.

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

Unlike completeness of a sequence of partitions of , the condition of transitivity of the product of their stabilizers 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 description 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 stronger versions of Beneš conjecture are false.

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

Counterexample 2. Beneš conjecture is not directly generalizable to the products of stibilizers of the form . More precisely, transitivity of does not always imply , where is a uniform partition of and all are permutations of such that (while Beneš conjecture states that this implication is always true as long as ). For that I constructed the following counterexample:

Indeed, it is obvious that both permutations are satisfying and the set is transitive. However, as, in particular, it can be easily seen that any permutation of satisfying does not belong to .

Counterexample 3. In the same paper [B75], Beneš also proposed the following

Conjecture  ()   Let be a uniform partition of and be a permutation of such that . Suppose that is the smallest integer such that the set is transitive. Then .

In other words, this conjecture together with Beneš one, asserts that if is the smallest integer such that is transitive, then is the the smallest integer such that . However, Conjecture () turned out to be generally false as I found the following counterexample for it:

Indeed, it is easy to verify that and the set is transitive while is not as, in particular, . However, a brute force verification confirmed that .

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.