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](https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_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.
> 
> 
> 


3. 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](https://arxiv.org/abs/1210.3018). A positive answer to Q1 would imply that in the variant of the [100 prisoners problem](https://en.wikipedia.org/wiki/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](https://arxiv.org/abs/0812.2242) in which the prisoners are allowed to open a superposition of drawers.)



Can $S_n$ be partitioned into subsets containing an involution and satisfying $∀σ≠τ, ∃j$ s.t. $σ(j)≠τ(j),σ^{−1}(j)=τ^{−1}(j)$?
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$.


