Questions tagged [symmetric-groups]
The symmetric group $S_n$ is the group of permutations of the set of integers $\{1,\dots,n\}$. This has $n!$ elements and is generated by the $n-1$ involutions exchanging consecutive integers. The symmetric groups form the simplest family of Coxeter groups.
436
questions
2
votes
0
answers
84
views
Combinatorial model for twisted involutions in $S_n$
Let $(W,S)$ be a Coxeter group and $*:S \to S$ be an automorphism of the Dynkin diagram of $W$ so that $*^2$ is the identity.
This induces a bijection $*:W \to W$ mapping $w = s_1 \dots s_n$ to $w^* = ...
5
votes
1
answer
363
views
Large subgroups of $S_n$ without large symmetric or alternating subgroups
I'm interested in determining the existence of a permutation group $G\subseteq S_n$ of the following form.
$G$ is large. Meaning that $G$ have at least $n!/2^{o(n)}$ elements. Equivalently, their ...
3
votes
0
answers
101
views
working with symmetric groups presented via nonstandard generators
This is follow-up to my earlier question.
Suppose that we have elements $\sigma_1,\ldots,\sigma_k\in S_n$, and that we established that these elements actually generate $S_n$.
Since that previous ...
1
vote
0
answers
60
views
A dimension formula for generalised symmetric powers of the natural module
I need a reference for the following well-known statement - does anyone know one?
Let $\mu$ a partition of $n$ into at most $d$ parts.
We let
$${\rm Sym}^\mu(\Bbbk^d)={\rm Sym}^{\mu_1}(\Bbbk^d) \...
2
votes
0
answers
84
views
Permutation factorizations according to number of generated orbits
Let $\pi$ be a permutation in $S_n$ with cycle type $\lambda$.
How many factorizations into two factors $\pi=\sigma_1\sigma_2$ are there, such that the subgroup $\langle \sigma_1,\sigma_2\rangle$ ...
7
votes
1
answer
265
views
Homotopy type of the semi-simplicial set of symmetric groups
Consider the collection of symmetric groups $\{\Sigma_n\}_{n\geq1}$ as a semi-simplicial set (i.e. a simplicial set without degeneracies) as follows. Consider $i\in\{1,\dots,n+1\}$ and $\pi\in\Sigma_{...
1
vote
2
answers
494
views
What are all the transitive extensions of cyclic groups?
"Let $G$ be a transitive group of permutations on a given set of letters. Let a new fixed letter be adjoined to every permutation of $G$. Then a transitive group $H$ of permutations on the ...
10
votes
1
answer
251
views
Edge-transitive Cayley graphs of $S_n$
I came across the following question which I haven't seen before:
Question. Fix $k\ge 3$. For infinitely many $n$, does there exists a generating set $\langle R_n \rangle = S_n$, $|R_n|=k$, such ...
5
votes
0
answers
254
views
Tabloid Construction of Permutation Representation of Hyperoctahedral Group
For a partition $\lambda \vdash n$, the permutation representation $M^{\lambda}$ of the symmetric group can be constructed in two ways. First, it may be written as the induced representation $M^{\...
4
votes
1
answer
455
views
Is the Normal centralizer problem in P?
Notation
$\le$ is used for the subgroup relation;
$P$ means polynomial time in input size;
$\Omega = \{1,2,3,\cdots,n\}$ is a input domain;
$\mathrm{Sym}(\Omega)$ means the symmetric group on $\...
10
votes
3
answers
673
views
Low-dimensional irreducible 2-modular representations of the symmetric group
I apologize if this question is a little too basic for MathOverflow, but it's somewhat outside of my background and I'm frustrated that the answer doesn't seem to be explicit in the literature even ...
4
votes
1
answer
750
views
Symmetric functions of eigenvalues
Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a smooth function, which is symmetric under the action of the symmetric group (acting on $\mathbb{R}^n$ by permuting the variables).
Let $M_{n\times n}$...
2
votes
1
answer
142
views
Number of permutations in a set in an algorithm
Previously I asked a question about the space usage in an algorithm of mine: Upper bound on the number of permutations in a set during an algorithm. This question does not depend on the previous one, ...
5
votes
1
answer
195
views
Murnaghan-Nakayama rule when all cycles have same size
Let $\lambda \vdash nk$. Let $n^k$ denote the partiton with $k$ parts of size $n$. We can compute $\chi^\lambda(n^k)$ by using the Murnaghan-Nakayama rule, as a signed sum over border-strip tableaux, (...
0
votes
1
answer
319
views
Dimension of irreducible representation associated to a Young tableau
This might be a classic question, but since I am new to representation theory of the symmetric group, I am asking it here.
Suppose that $\lambda_1 \geq \lambda_2 \geq \dots \lambda_k$ and $\rho$ be ...
6
votes
1
answer
438
views
Upper bound on the number of permutations in a set during an algorithm
Fix $n\geq 2$ and let $S_n$ be the symmetric group on $n$ letters with identity $e$. We consider elements of $S_n$ to be bijections $[n]\to [n]$ as well as sequences (one line notation). For $1\leq i&...
7
votes
2
answers
291
views
Generating symmetric groups with small cycles
This was asked but never answered at MSE.
Let $S_n$ denote the symmetric group and let $H$ be a subgroup which contains
an $n$-cycle. If $n$ is prime, and if $H$ also contains a 2-cycle, then ...
6
votes
0
answers
123
views
Natural maps between Schur functors: understanding the image
Let $V$ be a finite dimensional representation of symmetric group $\mathbb{S}_n.$ Consider a natural map
$$\pi \colon \Lambda^2 V \otimes \Lambda^2 V \longrightarrow \Lambda^4 V.$$
Let $[\Lambda^2 V]...
9
votes
2
answers
2k
views
alternating and symmetric powers of the standard representation of the symmetric group
Let $n \geq 7$ and $V = \mathbb{C}^n$ be the standard representation for $S_{n+1}$, the symmetric group of cardinal $(n+1)!$
Let $k$ be an integer such that $2 \leq k \leq n$. Is it true or false ...
12
votes
1
answer
377
views
Question on a reduction in Kirillov's paper on positivity of divided difference operators
As the title says, my question is on a specific argument in Kirillov - Skew divided difference operators and Schubert polynomials (journal, MSN) on positivity of divided difference operators. I recall ...
2
votes
0
answers
79
views
Characterization of permutations which have at most one successor in the covering relation of the weak Bruhat order
Let $W$ be the symmetric group on $n+1$ letters. Let $\ell$ be the length function on $W$.
As the title says, can we characterize all $v\in W$ such that there exists a $w\in W$ such that for all ...
3
votes
0
answers
158
views
Generating sets of the symmetric group that yield isomorphic Cayley graphs
Let $S$ and $S'$ be subsets of size $k$ of $\mathfrak{S}_n$.
Are there any necessary or sufficient conditions to determine whether or not $S$ and $S'$ yield isomorphic Cayley graphs?
Assuming we ...
1
vote
2
answers
245
views
A question about set of inversion
Let $w \in S_n$ and $inv(w) = \{(i,j): i,j \in \{1,\ldots,n\}, i<j, w(i)>w(j)\}$ the inversion set of $w$. Let ${\bf i}=(i_1,\ldots,i_m)$ be a sequence such that $s_{i_1}\cdots s_{i_m}$ is a ...
6
votes
0
answers
177
views
Permanent of the symmetric group
Let $A$ be the algebra corresponding to a representation-finite block of a Schur algebra.
See for example 6.1. of https://arxiv.org/pdf/1607.05965.pdf for quiver and relations and some relevance of ...
4
votes
1
answer
522
views
The number of permutations of a given cycle type that fix a string with a given histogram
Let $\lambda$ and $\mu$ be partitions of some integer $n \geq 1$. Let $d$ be the number of parts in $\mu$ and let $\bar{\mu} \in \{1,\dotsc,d\}^n$ denote the string $1^{\mu_1} 2^{\mu_2} \dotsb d^{\...
4
votes
1
answer
910
views
Induced representation of a Young subgroup
This might be a classic question, but since I am new to representation theory of the symmetric group, I am asking it here.
Suppose that $n=k+l+r$ where $k\geq l\geq r\geq 0$. Let $G$ be the symmetric ...
1
vote
0
answers
283
views
Classification of transitive subgroups of finite symmetric groups generated by double transpositions
I want to classify (up to isomorphism) all transitive subgroups of symmetric group $S_n$ which are generated by double transpositions (product of two transpositions). Is there a characterization for ...
5
votes
3
answers
556
views
Character values at a cyclic permutation of a symmetric group
Let $S_n$ be the symmetric group of degree $n$ and $\sigma\in S_n$ be
a cyclic permutation of order $p$, where $p$ is a prime and $p>n/2$. Consider
ordinary irreducible characters of $S_n$. Are ...
12
votes
0
answers
317
views
Bijective proof of an identity involving number of standard Young tableaux and semistandard tableaux
Question. Can you find a bijective proof of the identity
$$ \operatorname{dim}(S^{\lambda} \mathbb{C}^m)\ \operatorname{dim}(S^{\lambda'} \mathbb{C}^n) \ f^{n^m}
= \dim \Lambda^p (\mathbb{C}^m \...
6
votes
1
answer
283
views
Reference request: Reduced reflection length in Coxeter groups
I recently read this paper, where the authors define on page 26 what they call the reduced reflection length. For that we take a Coxeter group $G$ with Coxeter generators $S$ and transpositions $T$. ...
6
votes
2
answers
365
views
Provoking involutions further
Let $\mathfrak{S}_n$ denote the permutation group, and $I_0(n)=\sum_{j\geq0}\binom{n}{2j}\frac{(2j)!}{2^jj!}$ stand for involutions see A000085 for more interpretations. There is also these numbers $...
16
votes
1
answer
471
views
Irreducible representations occuring in $\mathrm{Ind}_G^{S_{|G|}}1$ for $G$ finite group
Let $G$ be a finite group with $|G|=n$, let $S_G=S_n$ be the group of $n!$ permutations of the set $G$. Then $G$ is a subgroup of $S_G$ via left-translation (i.e. $g\in G$ corresponds to the ...
3
votes
0
answers
63
views
A constraint satisfaction problem on matrix sum involving symmetric group
Given $n\in\Bbb N$ what is the smallest with $m>n$ we need such that there is a non-negative $\epsilon<1$ and $\Phi_i,\Psi_j\in\Bbb C^{m\times m}$ at every $i,j\in[n]$ ($[n]=\{1,\dots,n\}$) such ...
9
votes
1
answer
386
views
What is this symmetric simplex category, concretely?
Let $\Delta_+$ denote the category of finite ordinal numbers with monotonic maps (the subscript indicates that $0$ is included, so this is the augmented simplex category). This has a monoidal ...
3
votes
2
answers
211
views
trace and involution permutations: Part II
This is a follow up on my earlier MO question.
Let $\operatorname{Inv}(\mathfrak{S}_n):=\{\pi\in\mathfrak{S}_n: \pi^2=1\}$ be the set of involutions in the symmetric group $\mathfrak{S}_n$. Denote $...
13
votes
1
answer
631
views
trace and involution permutations: Part I
Let $\operatorname{Inv}(\mathfrak{S}_n):=\{\pi\in\mathfrak{S}_n: \pi^2=1\}$ be the set of involutions in the symmetric group $\mathfrak{S}_n$. Denote $I_n:=\#\operatorname{Inv}(\mathfrak{S}_n)$. Let $\...
6
votes
0
answers
191
views
hooks and contents: Part II
This is a 2nd installment to my earlier MO question for which Mark Wildon furnished a clean answer.
$\mathcal{O}(\pi)$ and $\mathcal{E}(\pi)$ stand for the number of odd and even cycles of a ...
6
votes
1
answer
393
views
hooks and contents: Part I
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R Stanley proved the following ...
9
votes
2
answers
747
views
Solutions of $x^d=1$ in the symmetric group
L Moser and M Wyman, On solutions of $x^d = 1$ in symmetric groups, Canad. J. Math., 7 (1955), pages 159-168, explored asymptotic behavior of the cardinality of such permutations:
$$f_d(n):=\#\{\pi\in\...
7
votes
2
answers
232
views
What can be said of a $6$-core Young diagram whose $2$-and $3$-cores are empty
Let $\lambda$ be a partition. Suppose that $\lambda$ is both $2$- and $3$-decomposable, in the sense that $\lambda$ admits a total decomposition by both $2$-rim hooks (aka dominos) and $3$-rim hooks. ...
3
votes
1
answer
267
views
Packing of anisotropic objects
The most famous version of packing problems deals with perfectly symmetrical shapes such as spheres. But how about anisotropic shapes? More prcisely, if we want to compare spherocylinders (cylinders ...
2
votes
0
answers
166
views
Signs in relations of Brundan--Kleshchev versus Khovanov--Lauda
The following relations in the definition of the quiver Hecke algebra in Brundan--Kleshchev's paper are
$$
y_r \psi_r e(\underline{i}) =(\psi_r y_{r+1} - \delta_{i_r,i_{r+1}})e(\underline{i});\\
$$
...
2
votes
1
answer
215
views
Symmetric group acting on the set of boolean functions
Let $S_n$ act on the set of boolean functions of size $n$ in the following way:
If $f$ is a boolean function and $\alpha \in S_n$, then $g=\alpha f$ and $g(x)=f(\alpha(x))$ where $x$ is boolean ...
1
vote
2
answers
165
views
Rank of a symmetric ideal
Let $\Sigma_m$ be the permutation group on $m$ letters and $R=\mathbb{C}[x_1,x_2,\dots,x_m]$. Let $\Sigma_m$ act on $R$ in the usual way. Let $R^{\Sigma_m}$ denote the ring of $\Sigma_m$ invariant ...
2
votes
0
answers
146
views
Generalized character formula
I am looking for alternative/simpler expressions for the sum
$F_{\mu_1,\mu_2,\mu_3}(h,k)\equiv\frac{1}{|G|}\sum_{g\in G} \chi_{\mu_1}(g)\chi_{\mu_2}(g h)\chi_{\mu_3}(g k)$
where $g,h,k\in G$ and $\...
7
votes
0
answers
188
views
Reference for an "elementary" combinatorial fact
This is a question I've been meaning to ask for quite some time.
Fact. For $n\in\mathbb N$ consider the set of segments $R=\{[i,j], 1\le i<j\le n\}$. Let a subset $E\subset R$ be nice iff $E$ is ...
15
votes
2
answers
702
views
Gelfand-Tsetlin algebras and "Jucys-Murphy elements" for $\mathfrak{gl}_n$
I'm trying to figure out/find in literature the details concerning Gelfand-Tsetlin algebras for $\mathfrak{gl}_n(\mathbb C)$ (Okounkov-Vershik style, if you wish).
Consider the chain $$\mathcal U(\...
3
votes
0
answers
218
views
$S_n$ action on the sequences of transpositions
It is well-known, that any element $\rho$ of the symmetric group $S_n$ with $n-p$ cycles admits a unique presentation as a product of a sequence of transpositions $\{(a_i\,b_i)\}_{i = 1}^p$ with $a_i &...
22
votes
1
answer
575
views
A symmetric-like group and the quaternion group $Q_8$
It is well known that the symmetric group $S_n$ admits presentation with
$\{(ij) \mid i\neq j\}$ as the set of generators and the following list of relations
(in every formula distinct letters denote ...
2
votes
1
answer
235
views
"flavored" equivalence classes of permutations
We say two permutations $\pi_1$ and $\pi_2$ in the symmetric group $\mathfrak{S}_n$ are $k$-equivalent, denoted
$\pi_1 \sim_k \pi_2$, if one can be
determined from the other after a finite number of ...