Maximum size of reverse-free sets of permutations
classification
🧮 math.CO
cs.DM
keywords
reversereverse-freesizewordslowermaximumpairsame
read the original 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) \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)}.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.