The permutation-groups tag has no usage guidance.
1
vote
1answer
157 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
160 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
362 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
148 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
177 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
72 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
142 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
119 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
620 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
393 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
99 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.
...
9
votes
2answers
439 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
163 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 ...
6
votes
0answers
119 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
74 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
166 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
317 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
319 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
380 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
99 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
105 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
392 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
123 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
470 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
143 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
372 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
45 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
261 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
594 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
414 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
223 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 $...
5
votes
1answer
140 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
388 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
448 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
561 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 ...
0
votes
1answer
185 views
Reference Request: Irreducibles of the regular representation of the permutation group is absolutely irreducible
I am writing a paper(physics) where I am using the fact that the irreducible's of the regular representations of the permutation group are absolutely irreducible in the following sense.
If $V$ is an ...
5
votes
2answers
236 views
Group acting on two different sets, can isomorphisms be computed efficiently?
For the permutation group isomorphism problem, a permutational isomorphism between two permutation groups is sought. A closely related but seemingly easier problem arises, if an isomorphism between ...
5
votes
1answer
127 views
What is the criterion for a matrix containing vectors and their permutations being invertible?
Consider the matrix $A\in\mathbb{R}^{m\times 2m}$. Let any arbitrary choice of $m$ columns of $A$ be linearly independent. Together with a permutation $P\in\mathcal{P_{2m}}$, one can build the matrix $...
6
votes
2answers
506 views
Can every permutation group be realized as the automorphism group of a graph (acting on a subset of the vertices)?
By Frucht's theorem, every finite group can be realized as the automorphism group of a finite undirected graph. Because a permutation group is a finite group, it is clear that every permutation group ...
3
votes
1answer
1k views
variance of the number of fixed points for a permutation group
It is reasonably well-known that the variance of the number of fixed points for $S_n$ equals $1.$ Now, what about other transitive permutation groups on $\{1, \dotsc, n\}?$ Presumably much is known. I ...
4
votes
0answers
159 views
Application of finding shortest paths on Cayley graphs
For a fixed integer number $m$, Consider Cayley graph defined by all m-cycles in Symmetric group $Sym(n)$.
I know that for $m=2$,
there are some applications of finding shortest paths (or distance ...
1
vote
0answers
389 views
What is the definition of plethysm in the representation theory of permutation groups
Let $s_\lambda \circ s_\mu$ be a plethysm. Here let $\lambda, \mu$ be $m,n$ box Young diagrams.
I have seen the definition of plethysms in symmetric functions. I would like to understand the ...
