5
votes
1answer
171 views

How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?

Let $G \leq {\rm S}_n$ be a finite permutation group, and let $S = \{g_1, \dots, g_k\}$ be a generating set for $G$ which is closed under inversion and which does not contain the identity. The growth ...
2
votes
5answers
252 views

Equivalence relations not associated with a group

This is a vague question; so vague that I wonder if anyone will get it. Many, perhaps most, equivalence relations that are regularly used in mathematics correspond to the orbits of some group action ...
4
votes
0answers
172 views

Permutations with all cycles odd

I have recently needed to compute the number of permutations in $S_n$ with all cycles odd, and while this is easy using Flajolet-Sedgewick theory (the exponential generating function seems to be ...
1
vote
1answer
178 views

Group with 2 orbits on the nonnegative integers — description of the orbits

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 ...
11
votes
0answers
399 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 ...
8
votes
1answer
243 views

Permutations of prescribed cycle types that multiply to the identity

Suppose that $\lambda_1,\lambda_2,\lambda_3$ are partititions of $n$. When do there exist permutations $\sigma_1,\sigma_2,\sigma_3 \in S_n$ such that (1) $\sigma_1\sigma_2\sigma_3$ is the identity; ...
4
votes
3answers
352 views

automorphisms of graphs and finite permutation groups

I am interested in automorphisms of graphs and in using tools from permutation groups (especially such as in Wielandt's text on finite permutation groups, which I have been studying). What are some ...
19
votes
1answer
1k views

Order of products of elements in symmetric groups

Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying $1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$ whose product has order ...
2
votes
0answers
246 views

Does probability of a derangement go up under passing to subgroups? [closed]

This is prompted by my attempts to work on this question. Let $H \subset G \subseteq S_d$ be transitive permutation groups. Recall that an element of $S_d$ is called a derangement if it has no fixed ...
5
votes
1answer
300 views

Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices

Dear community, I have the following combinatorial question which I will explain in short first and then with some more detail. At the end you will find a very simple example. Short version Le $A ...