# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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?
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 ...
269 views

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 ...
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?
162 views

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 ...
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 ...
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 ...
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$ ...
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 ...
345 views

103 views

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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
### 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 ...