Maximum size of reverse-free sets of permutations
From MaRDI portal
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)}.
Recommendations
Cited in
(13)- New bounds on even cycle creating Hamiltonian paths using expander graphs
- Ramsey numbers of interval 2-chromatic ordered graphs
- Reverse-free codes and permutations
- On reverse-free codes and permutations
- scientific article; zbMATH DE number 3857113 (Why is no real title available?)
- The maximal length of a k-separator permutation
- Maximal entropy permutations of even size
- Interlocked Permutations
- On \(k\)-neighbor separated permutations
- Path separation by short cycles
- scientific article; zbMATH DE number 7053339 (Why is no real title available?)
- Ramsey numbers of ordered graphs
- Large families of permutations of Zn whose pairwise sums are permutations
This page was built for publication: Maximum size of reverse-free sets of permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300491)
