10
$\begingroup$

For every positive integer $m$, consider the symmetric group $S_m$. By a full cycle, I mean a permutation $\sigma\in S_m$ which is a single cycle of length $m$. I will say two permutations $\sigma$ and $\tau$ are orthogonal if $\sigma^{-1}\tau$ has no fixed points, or in other words, $\sigma(x)\neq\tau(x)$ for all $x\in\{1,2,\ldots,m\}$. I want to know, for each $m$, what the maximum number of pairwise orthogonal full cycles in $S_m$ is. That is, what is the maximum number $n$ for which there exist $\sigma_1,\sigma_2,\ldots,\sigma_n\in S_m$ such that each $\sigma_i$ is an $m$-cycle and for any distinct $i$ and $j$, $\sigma_i^{-1}\circ\sigma_j$ is fixed-point free?

It is easy to show that $n\leq m-1$ for $m\geq 2$. This is simply because for any $x\in\{1,2,\ldots,m\}$, the assumptions imply $\sigma_1(x),\sigma_2(x),\ldots,\sigma_n(x)$ are distinct and $\{\sigma_1(x),\sigma_2(x),\ldots,\sigma_n(x)\}\subseteq\{1,2,\ldots,m\}\setminus\{x\}$. We can also show that $n=m-1$ if $m$ is prime since then we can take $\sigma_i$ to be the function which adds $i$ modulo $m$, which are all $m$-cycles because $1,2,\ldots,m-1$ are all coprime to $m$ when $m$ is prime. I believe the converse is true too: If $m$ is a composite number, then $n\leq m-2$.

In all of the examples I have checked, $n=m-2$ when $m$ is composite. So I really just want to know if this is true for all composite numbers.

$\endgroup$
4
  • 3
    $\begingroup$ For a lower bound we may essentially use the Chinese remainder theorem. For any composite $m=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k}$ and any $\eta\in[1,k]$ we may partition $(1,\ldots,m)$ into $p_\eta^{\alpha_\eta}$ blocks and define a map $\psi_{\eta,i}$ which brings a block with index $a$ into a block with index $a+i\pmod{p_\eta^{\alpha_\eta}}$. If $i\neq 0$ this map has order $p_{\eta}^{\alpha_{\eta}}$, hence by composing different $\psi_{\eta,i}$ for $\eta$ ranging from $1$ to $k$ we get at least $\prod_{\eta=1}^{k}\left(p_\eta^{\alpha_1}-1\right)$ orthogonal cycles. $\endgroup$ Commented Aug 12 at 17:27
  • 1
    $\begingroup$ Maybe by combining shifts and blocks-shifts it is also possible to reach $m-2$: too look for a suitable "tensor trick" seems the way to go. $\endgroup$ Commented Aug 12 at 17:54
  • 2
    $\begingroup$ @JackD'Aurizio There is one minor error with your calculation. In order for $\psi_{\eta,i}$ to have order $p_{\eta}^{\alpha_{\eta}}$, you need $i$ to be coprime to $p$, not simply $i\neq 0$. Thus, you actually get $\prod_{\eta=1}^k(p_{\eta}^{\alpha_{\eta}}-p_{\eta}^{\alpha_{\eta}-1})$. Note however, that this is just $\phi(n)$ where $\phi$ is the Euler totient function. We could achieve this more simply by letting $\sigma_i$ be addition by $i$ modulo $m$ where $i$ is coprime to $m$. $\endgroup$ Commented Aug 12 at 18:14
  • 1
    $\begingroup$ you're right. Still we may consider a standard shift for any $(a,m)=1$ and maybe a suitable composition of block-shifts if $(a,m)>1$. $\endgroup$ Commented Aug 12 at 20:09

1 Answer 1

Reset to default
3
+50
$\begingroup$

We can naturally interpret your question as on a maximal number of pairwsie edge disjoint Hamiltonian cycles in a complete directed graph with $m$ vertices. As I understand this answer, this number is $m-1$ for each natural $m>1$, but $4$ and $6$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.