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.
462 questions
4
votes
1
answer
528
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^{\...
- 499
4
votes
1
answer
1k
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 ...
- 901
1
vote
0
answers
285
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 ...
- 11
5
votes
3
answers
599
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
348
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 \...
- 381
6
votes
1
answer
301
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$. ...
- 809
6
votes
2
answers
366
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 $...
- 43.2k
16
votes
1
answer
484
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 ...
- 691
3
votes
0
answers
64
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 ...
- 13.9k
9
votes
1
answer
424
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 ...
- 5,482
3
votes
2
answers
216
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 $...
- 43.2k
13
votes
1
answer
637
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 $\...
- 43.2k
6
votes
0
answers
196
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 ...
- 43.2k
6
votes
1
answer
407
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 ...
- 43.2k
9
votes
2
answers
762
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\...
- 43.2k
7
votes
2
answers
236
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. ...
- 113
3
votes
1
answer
278
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 ...
user88381
2
votes
0
answers
173
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});\\
$$
...
- 1,413
2
votes
1
answer
219
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 ...
- 337
1
vote
2
answers
168
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 ...
- 422
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 $\...
- 43
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 ...
- 3,513
15
votes
2
answers
762
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,513
3
votes
0
answers
226
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 &...
- 401
22
votes
1
answer
599
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 ...
- 493
2
votes
1
answer
238
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 ...
- 43.2k
14
votes
1
answer
933
views
Church-Farb on the cohomology of pure braid groups and character polynomials, intuition behind proof of result?
Fix $n \ge 2$. Let $V_n$ be the $\binom{n}{2}$-dimensional vector space (over $\mathbb{C}$) generated by a set of vectors $\{w_{ij} : 1 \le i < j \le n\}$. Let $\bigwedge^* V_n$ be the exterior ...
- 193
8
votes
1
answer
200
views
factorization of polynomials wrt the major index stat
Let $\mathfrak{S}_n$ be the permutation group on $\{1,\dots,n\}$. Given $\pi=\pi_1\pi_2\dots\pi_n\in\mathfrak{S}_n$, its major index statistic is denoted maj$(\pi)$. Define the polynomials
$$Q_{n,k}(x)...
- 43.2k
13
votes
2
answers
556
views
Stabilization of representation of the symmetric group
In their seminal work on "representation stability" (https://arxiv.org/abs/1008.1368), Church and Farb deal with a stabilization procedure for representations (up to isomorphism) (over $\mathbf C$) of ...
- 2,521
49
votes
4
answers
6k
views
How to constructively/combinatorially prove Schur-Weyl duality?
How is Schur-Weyl duality (specifically, the fact that the actions of the group ring $\mathbb{K}\left[ S_{n}\right] $ and the monoid ring
$\mathbb{K}\left[ \left( \operatorname*{End}V,\cdot\...
- 33.8k
8
votes
2
answers
1k
views
Symmetric group action on Young Tableaux
Let $S_n$ be the symmetric group and let $\lambda$ be a partition of $n$ and let $S$ be the set of all standard young tableaux of shape $\lambda$. Is there a well defined action of $S_n$ on the set $S$...
- 673
0
votes
1
answer
232
views
Number of Boolean algebra subintervals in weak order of $S_n$
I'm wondering if anybody has an easy way to compute the number of subintervals in weak order of $S_n$ (considered as a Coxeter group of type $A_{n-1}$) that are isomorphic to Boolean algebras. I know $...
- 2,168
7
votes
0
answers
543
views
Representation theory of symmetric group for dummies
I have to grade a master project on representations of symmetric groups (char $0$) third time in my life and finally I came to a conclusion that I have to get a grasp of the matter. I am aware of ...
- 14.3k
3
votes
4
answers
610
views
Factorization in the group algebra of symmetric groups
Let $S_n$ be the symmetric group on $\{1, \ldots, n\}$. Let
\begin{align}
T=\sum_{g\in S_n} g.
\end{align}
Are there some references about the factorization of $T$?
In the case of $n=3$, we have
\...
- 6,201
3
votes
0
answers
414
views
Kazhdan-Lusztig basis of the symmetric group algebra $\mathbb{K}S_n$
Let $S_n$ be the symmetric group on the set $\{1,2,\ldots,n\}$ and $\mathbb{K}$ a field. Denote by $\mathbb{K}S_n$ the symmetric group algebra.
What's Kazhdan-Lusztig basis of $\mathbb{K}S_n$? I ...
- 331
4
votes
3
answers
947
views
Maximal pairwise distance between $k$ permutations
How can k permutations on n-set be arranged to maximize minimal pairwise Kendall tau distance (i.e. number of discordant pairs) between them?
For two permutations this is obviously when the second ...
23
votes
1
answer
1k
views
On an asymptotic formula of Keating and Snaith involving the Riemann zeta function
Keating and Snaith have a famous conjecture on the asymptotics of the
integral $\int_0^T |\zeta(\frac 12+it)|^{2k}\, dt$, where $\zeta$
denotes the Riemann zeta function. See page 510 of the book ...
- 50.8k
3
votes
2
answers
531
views
sum over permutations equals zero?
The question we are considering concerns a sum over all permutation $\sigma \in S_n$ (symmetric group) of a certain rational function:
$$\sum_{\sigma \in S_n} \frac{\sigma_{j1} \sigma_{j2}... \sigma_{...
- 33
2
votes
2
answers
275
views
How to recognize different types of irreps
Do the first two columns of the character table of the permutation group $S_n$ (the conjugacy classes () and (1 2) - that's a fairly standard order) always suffice to identify an irrep? (E.g. take $...
- 4,829
6
votes
1
answer
341
views
Sum of Young symmetrisers of a given shape
Preliminaries and notation:
Let $n\in \mathbb{Z}_{>0}$ and $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_s)\vdash n$ be a partition. Given a Young diagram of shape $\lambda$, we can associate it ...
- 87
1
vote
1
answer
240
views
free group actions on a contractible topological space [closed]
Let $\Sigma_k$ be the symmetric group on $k$-letters. Let $W$ be a contractible topological space with a free $\Sigma_k$-action (from the left). Let $X$ be a $CW$-complex and let $X^k$ be the ...
- 1,990
10
votes
1
answer
276
views
Looking for a good terminology for permutations having no substring
What is the good name for permutations of [1,...,n+1] having no substring [k,k+1]
http://oeis.org/A000255 ?
- 1,482
4
votes
0
answers
210
views
Characterizing the RSK corespondance
The Robinson-Schensted-Knuth correspondence is an algorithm which takes as input a word $w$ on the alphabet $\{1,\dots,n\}$ of length $k$ and returns a pair of a tableau $P(w)$ and a standard tableau $...
- 8,524
3
votes
0
answers
61
views
Isometry from a representation to the representation tensored with itself
Suppose, the group $ G=S(2^{\infty})$ has a unitary representation $ \pi $ on a separable infinite dimensional Hilbert space $ H $.
(The group $ S(2^{\infty}) $ is the direct limit of the following ...
- 817
3
votes
2
answers
924
views
sum over all integer partitions, of the product of the factorials of the terms
I'm looking for something making tractable the sum, over all partitions into k terms of an integer n, of the product of the factorials of all the terms.
Thanks,
- 31
6
votes
2
answers
532
views
A question about (unicity of certain cycles in a Cayley graph of a) symmetric group
Let $S=\{(1,2),(1,2,3,\ldots,n),(1,2,3,\ldots,n)^{-1}=(1,n\ldots,2)\}$ be a subset of the symmetric group $S_n$. We know that $(1,2,\ldots,n)(1,2)=(2,3,\ldots,n)$, and thus $$[(1,2,\ldots,n)(1,2)]^{n-...
- 377
4
votes
1
answer
419
views
On the symmetric group of 2^n elements
Consider the set $ X_1^n=\{1,2,...,2^n\} $. Then define $ X_2^n $ to be the set of two element subsets of $ X_1^n $. I will construct $ X_i $ by induction on $ i $. $ X_i^n $ is the set of two element ...
- 817
6
votes
2
answers
529
views
A question about homogenous polynomials of degree $\frac{n(n-1)}{2}$
Let $n$ be a positive integer and $S_n$ be the symmetric group on $\{1,2,\ldots,n\}$.
For any $w\in S_n$ and polynomial $f\in \mathbb{R}[x_1,x_2,\ldots,x_n]$, denote $w(f)=f(x_{w(1)},x_{w(2)},\ldots,...
- 1,997
5
votes
1
answer
204
views
A decomposition of $w_0$ which is similar to the reduced decomposition
Some basic definitions about reduced decomposition:
In the symmetric group $S_n$, let $s_i$ denote the adjacent transposition $(i,i+1),i\in \{1,2,\cdots,n-1\}.$ Since $S_n$ is generated by adjacent ...
- 1,997
10
votes
1
answer
413
views
Super-plethysm?
Let $U$ be a representation of $S_m$ and $V$ a representation of $S_n$. Then the representation $\operatorname{Ind}_{S_m\wr S_n}^{S_{mn}}(U^{\otimes{n}}\otimes V)$ has a nice interpretation in terms ...
- 2,537