Beneš Conjecture

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

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

\begin{problem}[$\star$] Find a sufficient condition for a sequence of partitions ${\bf h}_1, \dots, {\bf h}_\ell$ of $E$ to be \emph{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$? \end{problem}

\begin{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}. $$ \end{conjecture}

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

A partition of a set is \emph{uniform} if all its blocks have the same size. Given a subset $P$ of a multiplicative group and a positive integer $m$, by $P^m$ we mean the set $PP\dots P$ ($m$ times). A set $T\subseteq\frak S(E)$ is \emph{transitive} if for every $x,y\in E$ there exists a permutation $\tau\in T$ such that $\tau(x)=y$. The \emph{infinum} of two partitions $\bf a$ and $\bf b$ of $E$ is the partition of $E$ defined by $$ {\bf a\wedge b} := \big\{\, a\cap b\ne\varnothing \ | \ a\in{\bf a} \ \&\ b\in{\bf b} \,\big\}. $$ The partition $\bf 0$ of $E$ is defined by ${\bf 0}:={\bf 0}_E:=\big\{\{x\} \ | \ x\in E \big\}$. So the condition ${\bf h}\wedge\delta({\bf h})={\bf 0}$ is equivalent to saying that for every pair of blocks $a,b\in{\bf h}$, the intersection $a\cap\delta(b)$ consists of at most one element.

Observe that the decomposition $\frak S(E) = \big(\delta S({\bf h})\big)^{\ell}$ is equivalent to universality of the sequence %of partitions ${\bf h},\delta({\bf h}),\dots,\delta^{\ell-1}({\bf h})$ due to the obvious identity $\delta S({\bf h}) \delta^{-1} = S(\delta{\bf h})$. Thus Problem ($\star$) is indeed underlying for Beneš conjecture.

Problem ($\star$) 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 $E,{\bf u},\varphi$), would provide a very useful and easy-to-check sufficient condition for universality of the sequences ${\bf u},\varphi({\bf u}),\dots,\varphi^{\ell-1}({\bf u})$ that are of particular interest.

Another important and interesting problem related to ($\star$) is to find an efficient polynomial-time (in $|E|$) factorization algorithm for identity (1). Given an identity $A = A_1A_2\dots A_\ell$, where all $A_i$ are subsets of a multiplicative group, a \emph{factorization algorithm} finds for every $a\in A$ an $\ell$-tuple $(a_1,\dots,a_\ell)\in A_1\times \dots \times A_\ell$ such that $a = a_1a_2\dots a_\ell$.

Beneš conjecture is mainly famous for its central case, \OPrefnum[Shuffle-Exchange (SE) conjecture]{37167}, stating essentially that $\frak S(X) = \big(\sigma S({\bf g})\big)^{2n-1}$, where $(X,{\bf g},\sigma)$ is an instance of $(E,{\bf u},\varphi)$ defined, given arbitrary integer parameters $k,n\ge2$, as follows:

\begin{itemize} \item $X$ is the set of all words of length $n$ over a $k$-letter alphabet. \item $\bf g$ is the partition of $X$ formed by the equivalence relation $\sim$ on $X$ defined by $x_1\dots x_{n} \sim y_1\dots y_{n} : \Leftrightarrow x_1\dots x_{n-1}=y_1\dots y_{n-1}$. \item $\sigma$ is the \emph{shuffle permutation} of $X$ defined by $\sigma(x_1 x_2 \dots x_{n}) := x_2 \dots x_{n} x_1$. \end{itemize}

Whereas \OPrefnum[SE conjecture]{37167}, especially its case $k=2$, has received enormous attention with relatively little progress, the general case of Beneš conjecture, despite importance of Problem ($\star$), has virtually generated no literature and had no progress. It remains open for all $n\ge3$.

While I strongly believe in the validity of \OPrefnum[SE conjecture]{37167}, I am not so sure about Beneš conjecture (without any additional assumptions on $E,{\bf u},\varphi$) and even do not rule out that it could be disproved by a low-scale counterexample.

It is easy to see that the case $n=2$ of Beneš conjecture coincides with that of SE conjecture, which (the case) is well known to be valid (it is discussed \OPrefnum[here]{37167}).

Unlike that of universality, the condition of transitivity is very easy to check. In particular, transitivity of the set $\big(\dd S({\bf h})\big)^{n}$ with $n\ge2$ is equivalent to the following assertion: $$ \forall\,h_1,h_n\in{\bf h} \ \exists\,h_2,\dots,h_{n-1}\in{\bf h} \ \forall\, i\in[n-1]: h_i\cap \delta(h_{i+1}) \ne \varnothing. $$

Beneš conjecture (as well as its underlying Problem ($\star$) and a broader problem of characterization of product of stabilizers on a finite set) admits a nice equivalent \OPrefnum[graph-theoretic form]{37210}.

\section{Counterexamples}

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

\textbf {1.} The condition ${\bf u}\wedge\varphi({\bf u})={\bf 0}$ is necessary for Beneš conjecture. This can be shown by the following simple counterexample: $$ E := [6], \ {\bf u} := \big\{\{1,2,3\}, \{4,5,6\}\big\}, \text{ and } \varphi:= (3,4). $$ Indeed, ${\bf u}\wedge\varphi({\bf u}) \ne {\bf 0}$ as $\{1,2,3\}\cap\varphi\{1,2,3\} = \{1,2\}$. Also, the set $\big(\varphi S({\bf u})\big)^{2}$ is obviously transitive. However, it can be easily seen that any permutation $\alpha$ of $E$ satisfying $\alpha \{1,2,3\} = \{4,5,6\}$ does not belong to $S({\bf u})\varphi S({\bf u})\varphi S({\bf u})$. Thus, $\frak S(E) \ne \big(\varphi S({\bf u})\big)^{3}$. %Therefore, In fact, the condition ${\bf u}\wedge\varphi({\bf u})={\bf 0}$ 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).

\textbf {2.} Beneš conjecture is not directly generalizable to products of stibilizers of the form $\varphi_0S({\bf u})\varphi_1 S({\bf u})\dots\varphi_{\ell-1} S({\bf u})$. For that I constructed a counterexample of a unform 6-block partition ${\bf u}$ of a 12-set $E$ and permutations $\varphi_1, \varphi_2$ of $E$ satisfying each ${\bf u}\wedge\varphi_i({\bf u})={\bf 0}$ such that the set $P:=S({\bf u})\varphi_1 S({\bf u})\varphi_2 S({\bf u})\varphi_1S({\bf u})$ is transitive but $\frak S(E) \ne P^2$.

\textbf {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 $n\ge2$ is the smallest integer such that $\big(\varphi S({\bf u})\big)^{n}$ is transitive, then $\frak S(E) \ne \big(\varphi S({\bf u})\big)^{2n-2}$. 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 ${\bf u}$ of an 8-set $E$ such that $\big(\varphi S({\bf u})\big)^{3}$ is non-transitive while $\frak S(E) = \big(\varphi S({\bf u})\big)^{6}$.

Bibliography

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

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.