# Can $S_n$ be partitioned into subsets containing an involution and satisfying $∀σ≠τ, ∃j$ s.t. $σ(j)≠τ(j),σ^{−1}(j)=τ^{−1}(j)$?

## Background

Let $\sigma, \tau \in S_n$. We will say that $\sigma$ and $\tau$ are locally orthogonal and write $\sigma \perp \tau$ if there exists $j \in \{1, 2, \ldots, n\}$ such that $\sigma(j) \neq \tau(j)$ but $\sigma^{-1}(j) = \tau^{-1}(j)$. (I will explain this terminology in the Motivation section below.) We will call a subset $S \subset S_n$ exclusive if $\sigma \perp \tau$ for any $\sigma, \tau \in S$, $\sigma \neq \tau$. Observe that any exclusive subset of $S_n$ can contain at most one involution.

We say $\sigma, \tau \in S_n$ are Knuth equivalent if they have the same insertion tableau under the Robinson-Schensted correspondence. This is the same as $\sigma^{-1}$ and $\tau^{-1}$ being dual Knuth equivalent, i.e., having the same recording tableau. Involutions are precisely those permutations that have the same recording and insertion tableaux, so each Knuth equivalence class contains exactly one involution, as does each dual Knuth equivalence class.

## Questions

1. Does there exist a partition of $S_n$ into exclusive subsets such that each subset contains an involution?

2. Does either Knuth equivalence or dual Knuth equivalence imply local orthogonality? Either would imply a positive answer to Q1.

EDIT: A simple counterexample to Q2 is the pair of permutations $\sigma = (132)(4)$ and $\tau = (1)(234)$, which are Knuth equivalent but do not satsify $\sigma(j) = \tau(j)$ or $\sigma^{-1}(j) = \tau^{-1}(j)$ for any $j$. Q1 remains open.

1. Has this notion of local orthogonality for elements of $S_n$ been defined anywhere before (presumably under some other name)?

I have verified Q1 by brute force for $n \leq 11$.

## Motivation

The notion of local orthogonality appears in a more general context as part of a necessary condition for multipartite quantum correlations. A positive answer to Q1 would imply that in the variant of the 100 prisoners problem (sometimes called the locker puzzle) in which $n$ prisoners may only open 2 drawers, the classical best solution cannot be improved upon using shared quantum entanglement between the prisoners. (Note that this is different from the quantum version of the game considered by Avis and Broadbent in which the prisoners are allowed to open a superposition of drawers.)

• Slightly different way of thinking about local orthogonality: $\sigma$ and $\tau$ are locally orthogonal iff $\sigma$ and $\tau$ have non-identical cycles which share at least one edge. This makes it clear that $\sigma$ and $\tau$ are locally orthogonal iff $\sigma^{-1}$ and $\tau^{-1}$ are locally orthogonal, so your questions about Knuth equivalence and dual Knuth equivalence are equivalent. – Sean Eberhard Jul 7 '18 at 10:15
• Is it obvious that if $\sigma$ and $\tau$ are Knuth equivalent then $\tau^{-1}\sigma$ has a fixed point? – Sean Eberhard Jul 7 '18 at 10:15
• @SeanEberhard: No. Take $\sigma = \left[3, 1, 2, 4\right]$ and $\tau = \left[1, 3, 4, 2\right]$ (both in one-line notation). – darij grinberg Jul 8 '18 at 11:16
• @darijgrinberg Thanks. I posted my comment before Evan updated his question. Your example is the one he gave in his update. – Sean Eberhard Jul 8 '18 at 11:21

Yes. For each permutation $\sigma\in S_n$, choose (arbitrarily) from each nontrivial cycle of $\sigma$ a point $x$ such that $x < \sigma(x)$, and let $f(\sigma)$ be the set of pairs $(x,\sigma(x))$ so obtained. Then $f$ is a map from $S_n$ to the set of sets of disjoint ordered pairs $(i, j)$ with $i,j\in\{1,\dots,n\}$, $i<j$, so $f$ partitions $S_n$. Moreover, for each such set $E = \{(i_1, j_1), \dots, (i_k,j_k)\}$ of disjoint ordered pairs we have an involution $\sigma = (i_1j_1) \cdots (i_kj_k)$ such that $f(\sigma)=E$, so there is an involution in each class. It remains to show that each class $f^{-1}(E)$ is exclusive.
Suppose $f(\sigma) = f(\tau) = E$. Then for each $(i,j) \in E$ we have $\sigma(i) = \tau(i) = j$. If there is a largest positive integer $k$ such that $(i,\sigma(i), \dots, \sigma^k(i)) = (i, \tau(i), \dots, \tau^k(i))$ then we must have $\sigma\perp\tau$, because if $x = \sigma^k(i)$ then $$\sigma^{-1}(x) = \sigma^{k-1}(i) = \tau^{k-1}(i) = \tau^{-1}(x)$$ while $$\sigma(x) = \sigma^{k+1}(i) \neq \tau^{k+1}(i) = \tau(x).$$ If there is no largest such $k$ then it must be that the cycles of $\sigma$ and $\tau$ containing $i$ are identical, and if this is true for every $(i,j)\in E$ then we must have $\sigma=\tau$.