Skip to main content

All Questions

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12 votes
0 answers
558 views

Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers

Definition / Question Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$. Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition $...
Stefan Kohl's user avatar
  • 19.6k
10 votes
0 answers
194 views

Permutation groups with diameter $O(n \log n)$

I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture: Suppose that 1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...
Dmytro Taranovsky's user avatar
4 votes
0 answers
115 views

Complexity to find "short" (e.g. polynomial in diameter) decomposition of the permutation into the product of generators?

Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ ...
Alexander Chervov's user avatar