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.
163
questions
-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 ...
