Questions tagged [permutation-groups]

For groups represented as permutations. Group transitivity, rank 3 groups, orbits and suborbits, stablizers, permutation characters, primitivity are all on-topic.

Filter by
Sorted by
Tagged with
-1
votes
1answer
209 views

Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]

Suppose you are given two indexed permutations, (7 followed by 4, for instance) What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer ...
2
votes
0answers
81 views

Permutation group with a nice lattice of block systems

Let $X$ be a finite set and $G$ be a transitive subgroup of the symmetric group on $X.$ Recall that a (complete) block system for this action is a partition of $X = B_1 \cup \cdots \cup B_k$ into ...
0
votes
0answers
97 views

classification for some groups

Let $G$ be a finite group. Suppose that $G$ acts on a set, say $X$, transitively such that for every $x\in X$, $G_x^g=G_x$ or $G_x^g\cap G_x=\{1\}$. Could you please tell me if there is a ...
6
votes
1answer
220 views

Is there a known classification of regular multiplicity-free permutation groups?

The question is in the title, but let me clarify the terminology. I consider a permutation group $\Sigma\subseteq\mathrm{Sym}(\Omega)$ on a finite set $\Omega$. $\Sigma$ is regular if it acts ...
4
votes
1answer
160 views

Number of permutations with combinatorial geometric constraints

We are given a $d$-dimensional hypercube $H$, where each vertex is labeled with an integer $\ell\in\{1, 2, \ldots, 2^d\}$. Let $L$ be this labelling. Question: How many labelling permutations $L'$ of ...
2
votes
1answer
83 views

Source for: a permutation group is multiplicity-free if and only if its 2-orbits define an association scheme

I have recently proven the following (at least, so I believe): Theorem. Given a permutation group $\Sigma\subseteq\mathrm{Sym}(\Omega)$ on the set $\Omega:=\{1,...,n\}$, the following are equivalent: ...
0
votes
0answers
101 views

Request for a modern Reference for Frobenius' paper “Über die Charaktere der mehrfach transitiven Gruppen”

I'm interested in the paper of Jan Saxl "The Complex Characters of the Symmetric Groups that Remain Irreducible in Subgroups". I have only (not yet enough!) standard background on the ...
2
votes
1answer
181 views

Does the Hawaiian Earring Group embed into the permutation group of $\mathbb N$?

Recall that the Hawaiian earring group, $\mathbb G$, is the fundamental group of the Hawaiian Earing using the point at the origin. It can be understood more combinatorially as a subgroup of the ...
6
votes
1answer
99 views

Automorphism group of a putative strongly regular graph

The smallest feasible parameters for which no strongly regular graph is known to exist are $(69,48,32,36)$, as per Brouwer's table. What is known on the automorphism group of such a graph?
7
votes
1answer
254 views

For which $n$ can $S_n$ act transitively on $n+k$ elements?

It is known that the symmetric group $S_n$ can act transitively on $n+1$ elements if and only if $n=5$. Are there similar classifications for $S_n$ acting transitively on $n+k$ elements, where $k$ is ...
6
votes
1answer
269 views

Group action with unique word

This must be known or easy for some of you, but here goes: Suppose $f_0,f_1:[n]\to [n]$ are invertible functions, where $[n]=\{0,\dots,n-1\}$ is a set of $n$ elements. For a word $w=w_1\dots w_m\in\{...
7
votes
0answers
80 views

Extensions of oligomorphic groups

Recall that a permutation group $G\le\mathfrak{S}(\mathbb N)$ is oligomorphic if, for any positive integer $k$, the induced $G$-action on $k$-tuples of distinct elements of $\mathbb N$ has only ...
9
votes
2answers
251 views

Can $1\ne H\cap H^g\lhd H$ happen if $G$ is a primitive permutation group with stabiliser $H$?

Assume everything is finite. Let $G$ be a primitive permutation group with point stabiliser $G_\alpha$ for some $\alpha$. For $\beta\ne\alpha$, by an arc stabiliser we mean $G_{\alpha\beta}=G_\alpha\...
0
votes
0answers
40 views

How to construct such a series of “partial” symmetric polynomials?

As we know, a symmetric polynomial is a polynomial P(X1, X2, …, Xn) in n variables, such that if any of the variables are interchanged, one obtains the same polynomial. Formally, P is a symmetric ...
0
votes
0answers
29 views

arc-transitive graphs of valency 3p, p a prime

I am looking for a characterization of arc-transitive graphs of valency $3p$, $p$ a prime. Is there any classification?
1
vote
2answers
162 views

Is there a 2 transitive finite group with transitive normal subgroup having a cyclic quotient other than $A_n$ and $S_n$?

Let $G \leq S_n$ be $2$-transitive other than $A_n$ and $S_n$. Is it possible that there exists $N\lhd G$ with $N\neq G$, $N$ transitive and $G/N$ cyclic? I am interested mostly in the answer when $...
12
votes
0answers
271 views

How many steps on $S_n$ are required to span $V\wedge V$, $V = K^n$?

Let $A$ be a set of generators of $G=S_n$; assume $e\in A$, $A=A^{-1}$. Let $V = K^n$, $K$ a field. Consider the natural action of $G$ on $V$ (namely, $g(e_i) = e_{g(i)}$) and on $W = V\wedge V$ (...
11
votes
1answer
236 views

How many steps are required for double transitivity?

Let $A$ be a set of generators of $S_n$, or of a doubly transitive subgroup of $S_n$. Assume $e\in A$, $A=A^{-1}$. What is the least $k$ such that $A^k$ is doubly transitive as a set? That is, what is ...
7
votes
1answer
157 views

Permutation groups generated by finitely many point stabilisers

Assume that $G\leq\operatorname{Sym}(X)$ is a permutation group generated by all its point stabilisers, i.e. $G=\langle G_x \mid x\in X\rangle$. There is no cardinality restriction on $X$. Furthermore,...
7
votes
1answer
347 views

Wreath product $S_k\wr S_n$ inside $S_{kn}$

I want to understand wreath products a little better. Currently, my intuition about them is as follows. Take $nk$ disks, pile them in order forming $n$ piles of $k$ disks (one pile contains disks {1,...
2
votes
1answer
127 views

Non-commutative projective lines

There have been many approaches to the notion of projective line: combinatorial approaches (e.g. as certain permutation groups, such as $\mathrm{PGL}_2(k)$ in its natural action on $\mathbb{P}^1(k)$, ...
20
votes
1answer
544 views

If $S_\mathbb N$ is partitioned into finitely many pieces, must one piece contain a “skew copy” of every countable group?

Suppose $G$ and $H$ are groups. $C \subseteq H$ is called a skew copy of $G$ in $H$ if $C = hK$ for some $h \in H$ and some subgroup $K$ of $H$ with $K \cong G$. Question 1: Suppose the infinite ...
6
votes
2answers
220 views

Irreducible factors of primitive permutation group representation

Consider a primitive permutation group $\Gamma\subseteq\mathrm{Sym}(N)$ on the $n$-element set $N=\{1,...,n\}$, that is, $\Gamma$ does not preserve any non-trivial partition of $N$. Consider the ...
6
votes
1answer
2k views

Are there infinitely many insipid numbers?

A number $n$ is called insipid if the groups having a core-free maximal subgroup of index $n$ are exactly $A_n$ and $S_n$. There is an OEIS enter for these numbers: A102842. There are exactly $486$ ...
4
votes
1answer
335 views

Is $(\mathbb{R},+)$ isomorphic to a subgroup of $S_\omega$?

Is $(\mathbb{R},+)$ isomorphic to a subgroup of $S_\omega$, the group of permutations of the set of non-negative integers $\omega$?
9
votes
1answer
275 views

Connections between linear representations and permutation representations

A finite group $\Gamma$ might be represented by a linear transformation $$\rho : \Gamma\to\mathrm{GL}(\Bbb R^d),$$ or by permutations $$\phi :\Gamma\to\mathrm{Sym}(n).$$ Of course, latter ones can ...
3
votes
1answer
143 views

Multiplication in $Z(\mathbb{C}S_n)$ [duplicate]

I am trying to multiply two generators of center $Z(\mathbb{C}[S_n])$ of ring algebra of symmetric group of $n$ elements. We know that these generators are given by sums of conjugacy classes in $S_n,$ ...
0
votes
2answers
204 views

Generators for permutation groups

Consider (e.g.) the full permutation group $G=S_6$. A valid set of generators and equations for $G$ is $r^6=m^2=(rm)^5=1$. I say this system has width $3$ (because there are $3$ equations), length $10$...
0
votes
1answer
92 views

Can the permutation group of a matrix be generated by the subset of row permutation and column permutation?

Consider a 3*3 matrix $\left( \begin{array}{*{20}{c}} {{m_{11}}}&{{m_{12}}}&{{m_{13}}}\\ {{m_{21}}}&{{m_{22}}}&{{m_{23}}}\\ {{m_{31}}}&{{m_{32}}}&{{m_{33}}} \end{array} \right)...
4
votes
1answer
126 views

Diameter for permutations of bounded support

Let $S\subset \textrm{Sym}(n)$ be a set of permutations each of which is of bounded support, that is, each $\sigma\in S$ moves $O(1)$ elements of $\{1,2,\dotsc,n\}$. Let $\Gamma$ be the graph whose ...
4
votes
1answer
99 views

Example of primitive permutation group with a regular suborbit and a non-faithful suborbit

I would like some examples of groups $G$ satisfying all of the following criteria: $G<Sym(n)$, the symmetric group on $n$ letters, and $G$ is primitive. $G$ has a regular suborbit, i.e. if $M$ is ...
26
votes
2answers
954 views

Does the symmetric group $S_{10}$ factor as a knit product of symmetric subgroups $S_6$ and $S_7$?

By knit product (alias: Zappa-Szép product), I mean a product $AB$ of subgroups for which $A\cap B=1$. In particular, note that neither subgroup is required to be normal, thus making this a ...
9
votes
0answers
131 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
252 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 ...
5
votes
1answer
345 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
87 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
133 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
103 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\...
15
votes
1answer
421 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 ...
2
votes
1answer
301 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
203 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
463 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$ ...
10
votes
1answer
191 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 ...
3
votes
2answers
220 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
74 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
75 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
274 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
75 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
145 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
785 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 ...