## 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

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

~~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.

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