pith. sign in

arxiv: 1208.2847 · v3 · pith:ASXADSLWnew · submitted 2012-08-14 · 🧮 math.CO · cs.DM

Maximum size of reverse-free sets of permutations

classification 🧮 math.CO cs.DM
keywords reversereverse-freesizewordslowermaximumpairsame
0
0 comments X
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.