Maximum Size of Reverse-Free Sets of Permutations
Josef Cibulka · SIAM Journal on Discrete Mathematics · 2013
Two words have a reverse if they have the same pair of distinct letters on the same pair of positions, but in reversed order. A set of words no two of which have a reverse is said to be reverse-free. Let $F(n,k)$ be the maximum size of a reverse-free set of words from $[n]^k$, where no letter repeats within a word. We show the following lower and upper bounds in the case $n \ge k$: $F(n,k) \in n^k k^{-k/2 + O(k /\log k)}$. As a consequence of the lower bound, a set of $n$-permutations, each two having a reverse, has size at most $n^{n/2 + O (n/\log n)}$.