Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The 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 ...