Questions tagged [permutation-groups]
The permutation-groups tag has no usage guidance.
7
votes
0answers
83 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$ ...
11
votes
1answer
165 views
Permutation groups having a regular cyclic subgroup and a conjectured algebra of characters
Let $G$ be a transitive permutation group of degree $d$ having a cyclic regular subgroup $K = \langle k \rangle \cong C_d$. Let $\pi(g) = |\mathrm{Fix}(g)|$ be the permutation character of $G$ and let
...
4
votes
1answer
209 views
Number of permutations that are products of disjoint cycles of distinct length
What is the number of permutations $\pi\in S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $...
1
vote
0answers
82 views
What is an upper limit of relative size of conjugacy class of the transitive finite group?
What is
$$ \limsup_{n\to\infty} \sup_{\deg(G)=n} \left( \frac{\max_{x\in G} \left|\operatorname{conj}(x)\right|}{\operatorname{ord}(G)}\right),$$
$G$ transitive permutation group?
And what are the ...
6
votes
1answer
118 views
Enlarging a subdegree-finite “almost transitive” permutation group to a transitive one? (follow-up)
Consider a permutation group $G$ acting on an infinite set $X$. Assume $G$ has finitely many orbits, and every point stabiliser $G_x$ has finite orbits.
Can we always find a permutation $\tau\in\...
3
votes
1answer
88 views
Enlarging a subdegree-finite “almost transitive” permutation group to a transitive one?
Consider a permutation group $G$ acting on an infinite set $X$. Assume $G$ has finitely many orbits, and every point stabiliser $G_x$ has finite orbits. Now consider a permutation $\tau\in\...
12
votes
0answers
271 views
Escaping from a centralizer
Let $G = Sym(n)$, $n$ even. Let $H<G$ be the stabilizer of the partition $\{\{1,2\},\{3,4\},\dotsc,\{n-1,n\}\}$, or, what is the same, the centralizer of $(1\;2) \dotsc (n-1\; n)$.
By Stirling's ...
1
vote
1answer
196 views
A permutation with reflection property
Consider permutations $\pi$ of the set $\{1,\dots,n\}$ having the symmetry property $\pi \pi^* \pi = \pi^*$, where $\pi^*$ is the "reflection" $k \mapsto n+1-k$. Are there references or other ...
8
votes
1answer
164 views
Is $\beta\mathbb N$ a unique compactification with the smallest possible permutation group?
For a compactification $c\mathbb N$ of $\mathbb N$ let $\mathcal H(c\mathbb N,\mathbb N)$ be the group of homeomorphisms $h:c\mathbb N\to c\mathbb N$ such that $h(x)=x$ for all $x\in c\mathbb N\...
7
votes
1answer
392 views
Linear permutations commuting with $x\rightarrow x^{-1}$
Let $F = \operatorname{GF}(2^n)$ be a finite field. Define a permutation $\phi:F \rightarrow F$ by the formula
$$
\phi(x) = x^{-1}, \ x\neq 0; \ \phi(0) =0.
$$
We say that a permutations $\psi$ of $F$ ...
8
votes
1answer
149 views
sum of character product over derangements
It is widely known that
$$ \frac{1}{n!}\sum_{\pi\in S_n}\chi_\lambda(\pi)\chi_\mu(\pi)=\delta_{\lambda,\mu},$$
where $S_n$ is the permutation group and $\chi$ are its irreducible characters.
In ...
0
votes
0answers
29 views
What is an example of a constructive encoding of binary strings modulo an arbitrary permutation group $G$?
Given a group $G \leq S_n$ we can construct by the axiom of choice a function $f : \{0, 1\}^n \rightarrow \{0, 1\}^{ceil(log_2 |\{0, 1\}^n/G|)}$ such that for any orbit $O$ of binary strings under $G$,...
3
votes
2answers
179 views
Length of composition series in a primitive group
Let $G$ be a primitive group acting on a set $\Omega$ with $n$ elements. By Cameron/Liebeck (essentially a consequence of the Classification + O'Nan-Scott), there are two possibilities:
(a) $G$ has a ...
0
votes
1answer
59 views
Sequence Generation with Combinations and Permutations
I am trying to generate a set of genetic sequences with conditions. The problem uses a base 4 numerical notation:
nucleotides = ['A','C','G','T']
From this, I'd ...
2
votes
0answers
73 views
First appearance of “structure tree”?
Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges ...
4
votes
1answer
154 views
Time Complexity of the Word Problem for Finite Permutation Groups
Given a finite permutation group, i.e. a subgroup of the symmetric group on $n$ symbols in terms of generators, what is the complexity of the word problem? That is, computing if two words in the ...
1
vote
1answer
72 views
Complexity to decide for permutation group if every element fixed at most $k$ points
I want to consider the following problem, which generalises the decision problem to decide if a given finite permutation group is a Frobenius group:
Given a finite permutation group in terms of its ...
1
vote
2answers
121 views
Complexity of decision problem to decide if permutation group is $k$-transitive
Given a finite permutation group $G$ (a subgroup of the symmetric group on a finite set) in terms of its generators, what is known about the decision problem of deciding if $G$ is $k$-transitive for a ...
19
votes
3answers
652 views
What did Frobenius prove about $M_{12}$?
I am interested in this paper which I can't read because it's in German:
Frobenius, G., Über die Charaktere der mehrfach transitiven Gruppen., Berl. Ber. 1904, 558-571 (1904). ZBL35.0154.02.
A free ...
2
votes
0answers
50 views
What are the transitive extensions of finite representations of cyclic groups?
This question is a generalisation of this one. Let $H$ be a finite, transitive permutation group of degree $n$. If the point stabiliser subgroup $H_n$ of degree $n-1$ is some faithful permutation ...
14
votes
1answer
409 views
The number of involutions in a permutation group
If $G$ is a group let $I(G)$ be the number of involutions (elements of order 2) in $G$. My question is then easily stated: does there exists a constant $C > 1$ such that for every $n \ge 1$ and ...
1
vote
0answers
103 views
A question about permutation matrices
This question is trying to abstract out in a self-contained way the point that is probably being made in page 6 of this paper, https://arxiv.org/pdf/1604.03544.pdf and why Theorem 4.1 there works.
...
10
votes
2answers
509 views
How do I know if an irreducible representation is a permutation representation?
I have a vague question, a less vague question and a lot of vaguer questions about permutation representations of a finite group $G$.
Vague question. Recall that if $G$ acts on a finite set $X$, we ...
1
vote
0answers
166 views
Counting elements having a given cycle structure in maximal subgroups of a generalized symmetric group
Let $G$ be the wreath product $C_7\wr S_{18}$, where $C_7$ is the cyclic group of order 7 and $S_{18}$ is the symmetric group on 18 symbols. Consider $G$ to be embedded in the group $S_{126}=S_{7\cdot ...
7
votes
0answers
128 views
Connection between Gauss's lemma and Zolotarev's lemma
So I was reflecting on the relationship between Gauss's Lemma and Zolotarev's Lemma in proofs of quadratic reciprocity:
GL: $(a/p) = -1^n$, where $n$ is the number of least positive residues of $ax$ ...
1
vote
0answers
80 views
graphs with semiregular automorphisms
I need some "well-known" non-regular finite graphs (at least two vertices have different valency) whose automorphism groups contain a non-trivial subgroup that acts on the vertices semi-regularly (i....
1
vote
1answer
174 views
Automorphism group of a graph
Suppose $\Gamma$ is a simple graph and $G=\mathrm{Aut}(\Gamma)$ is the automorphism group of $\Gamma$. If $G$ stabilizes a subgraph $\Gamma_1$,, and $G_0$ is the point-wise stabiliser of the set $V(\...
7
votes
2answers
335 views
Automorphism group of a special commuting graph
Suppose $S_6$ is the symmetric group on six letters and let $X$ denote the conjugacy class containing $(12)(34)$. Define a graph $\Gamma$ with vertex set $X$ and edges precisely the 2-element subsets ...
11
votes
1answer
349 views
Outer automorphism action on representations of $S_6$
Let $S_6$ be the symmetric group on 6 letters and let $\alpha \colon S_6 \to S_6$ be an outer automorphism (note that $S_6$ is the only permutation group that has an outer automorphism and that $\...
13
votes
1answer
395 views
Tensor power of the natural representation of Sn
The symmetric group $S_n$ acts over $V=\mathbb{R}^n$ by permuting the canonical basis.
So it acts over $V^{\otimes p}$ with a diagonal action (acts the same over each element of the tensor product).
...
2
votes
0answers
85 views
What is the meaning of a linked group action?
Some definitions and Notations
Group Action see this link.
$G$-invariant partition $B_i$ means $\forall \sigma \in G, B_i^{\sigma} = B_i$.
Minimal block system see page no - 30
Let $V$ be a $k$-...
0
votes
1answer
104 views
number of orbits of a proper subgroup
Let $G$ be a permutation group that acts on (say) $X=\{1,2,..,n\}$, and $H$ be a proper subgroup of $G$. Can one say anything precise about when the number of orbits of $H$ on $X$ will be equal to ...
5
votes
1answer
106 views
composition factors of primitive components
A finite transitive permutation group $G$ can always be ``decomposed'' into primitive permutation groups, called its primitive components, although the decomposition is not unique. See Chapter 1 of ...
7
votes
2answers
401 views
sum-sets in a finite field
Let $\mathbb{F}_p$ be a finite field, $A=\{a_1,\dots,a_k\}\subset\mathbb{F}_p^*$ a $k$-element set, for $k<p$. $\mathfrak{S}_k=$permutation gp.
Question. Is it true there is always a $\pi\in\...
2
votes
1answer
128 views
Endomorphism of the symmetric group of the set of positive integers via action on the prime numbers
For a positive integer $n$, let $p_n$ denote the $n$-th prime number.
Further let $f: {\rm Sym}(\mathbb{N}) \rightarrow {\rm Sym}(\mathbb{N})$
be the monomorphism which maps a permutation $\sigma$ to ...
8
votes
2answers
490 views
Regular elementary abelian subgroups of primitive permutation groups
A finite group $B$ is said to be a B-group if every primitive permutation group having a regular (transitive) subgroup isomorphic to B is $2$-transitive.
Schur proved that a cyclic group of ...
3
votes
1answer
154 views
Maximal subgroups of a generalized symmetric group
Let $G$ be the wreath product $C_m\wr S_n$, where $C_m$ is the cyclic group of order $m$ and $S_n$ is the symmetric group on $n$ letters. I would like to understand the maximal subgroups of $G$ up to ...
2
votes
1answer
151 views
Permutation groups: is there a term for an arbitrarily-permuted subset of points?
Let $G$ be a permutation group on a set $X$ of points. How do we call a subset $S\subseteq X$ such that, for each permutation $\pi \in \mathrm{Sym}(S)$ there exists $g \in G$ acting like $\pi$ if ...
10
votes
1answer
375 views
Eliminating constant in Rado graph
Let $R$ denote the Rado graph, and let $c$ be a fixed vertex.
Question 1. Is the structure obtained by extending $R$ by the constant $c$ interpretable in $R$ without parameters?
By interpretable I ...
1
vote
0answers
46 views
Set of vectors closed under restricted permutation operations
Let $V=\{v_1,\cdots v_k\}$ a set of non zero different norm one vectors in $R^d$, $k>2$. I am trying to demonstrate that if $Q=\{P_i\in R^{k\times k},i=1,\cdots,k\}$ is a set of permutations such ...
2
votes
1answer
267 views
Is there a formula for the number of elements in $S_n$ having length $k$ with respect to the generators taken to be the transpositions?
Define the length of a permutation as the minimum number of adjacent transpositions needed to describe it.
We know that there is only one element of length $0$ in $S_n$ and $n-1$ elements of length $1$...
6
votes
6answers
611 views
Transitive permutation groups which all of their proper subgroups are intransitive
Let $G$ be a transitive permutation group on a finite set $\Omega$. It is clear
that if $G$ is regular, then every proper subgroup of $G$ is intransitive. Is
there any other class of groups with this ...
2
votes
1answer
446 views
2-closure of a permutation group
Let $G$ be a group acting on a set $\Omega$ faithfully. Then 2-closure of $G$ denoted by
$G^{(2)}$ is the largest subgroup of the symmetric group of $\Omega$ with
the same orbits as $G$ on $\Omega\...
2
votes
1answer
123 views
Intransitive finite irreducible linear groups whose orbits are all large
I am interested in intransitive irreducible linear subgroups $G\subseteq\mathrm{GL}_n(\mathbb{F}_p)$ acting on $V-\{0\}=\mathbb{F}_p^n-\{0\}$ in the natural way, such that all of the orbits are very ...
4
votes
1answer
228 views
Hyperoctahedral group acting on a special permutation
Let $[n]=\{1,...,n\}$ and $[\hat n]=\{\hat 1,...,\hat n\}$. Realize the hyperoctahedral group $H_n$ as the centralizer of the permutation $(1\hat 1)\cdots (n \hat n)$. It has $2^n n!$ elements.
Let $...
6
votes
1answer
145 views
A sum over characters of $S_{2n}$ and zonal spherical functions of $(S_{2n},H_n)$
The hyperoctahedral group $H_n$ can be seen as the centralizer of the permutation $(12)(34)\cdots (2n-1\,2n)$ in $S_{2n}$. It has $2^nn!$ elements.
The quantities $$ \omega_\lambda(\pi)=\frac{1}{2^...
-1
votes
1answer
134 views
Can someone explain how Sims's algorithm works on a permutation group with a simple example? [closed]
Can someone explain how Sims's algorithm works on a permutation group with a simple example? The book "Permutation group algorithms" by Seress is a pretty hard read with a whole bunch of confusing ...
12
votes
1answer
406 views
A sum over characters of the symmetric group
Let $C_\mu$ be the size of the conjugacy class in $S_n$ of permutations whose cycletype is the partition $\mu\vdash n$. Let $\chi$ be the characters of the irreducible representations of $S_n$.
Let $\...
6
votes
1answer
479 views
number of maximal subgroups of the symmetric group
What is the asymptotics of the number of the maximal subgroups of $S_n$ (as a function of $n$)? This must be written down somewhere...
EDIT I am actually more interested in the number of conjugacy ...
15
votes
2answers
585 views
Minimal maximal subgroup of the symmetric group
The question is pretty much in the title: What is the maximal subgroup of $S_d$ of maximal index (so minimal size)? A slight variant (I am not sure if it leads to a different answer) is: what if we ...
