Publication at Faculty of Mathematics and Physics |
2013
Abstract
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 >= k: F(n, k) is of the order 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)).