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
0
votes
0
answers
62
views
normal sets and conjugate generating sets of $S_n$
In this arXiv paper (p. 13), Steinhardt defines a normal set in $S_n$ as follows:
Definition: A split set of more than two cycles generating $S_n$ is said to be normal if any element is adjacent to ...
- 146
25
votes
3
answers
4k
views
Simplicity of alternating group $A_n$
I am teaching an introductory group theory course, and it has come to the inevitable proof that $A_n$ is simple for $n\geq 5$. Now, there seem to be a number of proofs that I can find – one the "...
- 96.4k
6
votes
1
answer
184
views
non-orientability of vector bundles induced from a symmetric group action
Let $\Sigma_k$ be the symmetric group on $k$-letters. Let $M$ be a manifold with a free $\Sigma_k$-action. Then we can form a $k$-dimensional vector bundle
$$
\xi:\mathbb{R}^k\longrightarrow M\times_{\...
- 1,990
5
votes
1
answer
299
views
Sum of skew characters over hooks and "odd" partitions
Let us call a partition odd if all its parts are odd, and let $Odd(n)$ be the set of all odd partitions of $n$, e.g. $Odd(6)=\{(5\,1),(3\, 3),(3\,1^3),(1^6)\}$.
Let $H(n)$ denote the set of all hook ...
- 2,552
6
votes
1
answer
843
views
Symmetry Group of a Polynomial
Given a polynomial $P \in \mathbb{Z}[X_1,\ldots,X_n]$, is there a poly-time algorithm which computes the group of permutations of variables that leaves $P$ unchanged? (Clearly, the trivial $O(n!)$-...
- 61
18
votes
3
answers
2k
views
What is the probability that two random permutations have the same order?
I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), ...
- 333
6
votes
2
answers
630
views
Generalized cycle index polynomial for the symmetric group
The answer to a particular calculation in quantum information theory gives me the following expression:
Given $M$ specific elements of the symmetric group $S_n$, define the polynomial
$$Z_n(\pi_1, \...
- 163
8
votes
1
answer
1k
views
Weingarten function for unitary group
Studying integration over unitary group I came across this function, the Weingarten function Wg, such that
$$ \int_{\mathcal{U}(N)} \prod_{k=1}^{n} U_{i_kj_k}
U^*_{m_k r_k} dU=\sum_{\tau,\sigma\in S_n}...
- 1,549
11
votes
1
answer
536
views
Invariant ring of $S_5$
The irreducible representations of the Symmetric group $S_5$ are classified by the partitions of $5$. For the standard representation which corresponds to the partition (4,1) the ring of invariants is ...
- 195
9
votes
1
answer
617
views
Problems which use S₄ → S₃
I need examples of problems which use, directly or indirectly, the homomorphism $S_4\to S_3$ in the solution (its kernel is $\mathbb{Z}_2\oplus\mathbb{Z}_2$).
Obvious candidates:
Lagrange resolvent (...
- 45k
11
votes
2
answers
779
views
Characters of permutation groups
Let $N$ be a fixed positive integer, and denote by $C(m)$ the number of
permutations on an $N$-element set that have exactly $m$ cycles (counting
$1$-cycles). Then it is in the literature that the ...
- 4,679
6
votes
1
answer
270
views
factorization of the cohomology of configuration space
This question is a follow-up to my previous question factorization of the regular representation of the symmetric group, which was answered in a very satisfactory way.
Let $\operatorname{Conf}(n,\...
- 2,537
15
votes
2
answers
838
views
factorization of the regular representation of the symmetric group
Let $\mathbb{C}[S_n]$ be the regular representation of the symmetric group $S_n$, and let $\mathbb{C}^n$ be the vector representation.
Question: Does there exist a representation $V$ (of dimension $(...
- 2,537
6
votes
3
answers
434
views
Repository of graph classes that are tough to test non-isomorphic pairs from isomorphic pairs
(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs?
(2) Is there a repository of adjacencies from such classes?
- 13.9k
12
votes
1
answer
510
views
Can a large transitive permutation group need many generators?
let $G$ be a transitive permutation group acting on $\{1, \ldots, n\}$, and let $d(G)$ be the minimal number of generators of $G$. Is it true, that for $n\rightarrow\infty$ we have $\frac{d(G)\log|G|}{...
21
votes
1
answer
1k
views
Okounkov-Vershik approach to representation theory of $S_n$
This is a rather soft question. I was wondering if someone could explain on a fundamental and intuitive level, what the Okounkov-Vershik approach to representation theory of $S_n$ is all about. It's ...
- 291
3
votes
0
answers
340
views
what is the link between plethysm in regular representation of the symmetric group and plethysm in Schur functions.
I am trying to understand first how one can define the plethysm say $s_\lambda \circ s_\mu$ as a module in the regular representation of the symmetric group.
1)How is it connected to the plethysms ...
- 349
6
votes
1
answer
307
views
G-Correlation of Vectors
Let $\vec{a},\vec{b} \in \mathbb{R}^{n}$. Consider the function $f: S_n \to \mathbb{R}$ given by $f(\sigma):= \sum_{i=1}^{n} a_i b_{\sigma(i)}$. Let $G$ be a subgroup of $S_n$, given by $O(\log n)$ ...
- 14.6k
1
vote
0
answers
147
views
$G$-harmonic polynomials, dimension of $\text{Harm}(\mathbb{R}^n, S_n)$? [closed]
Definition. Let $\text{Harm}(\mathbb{R}^n, G)$ be the space of $G$-harmonic polynomials on $\mathbb{R}^n$.
My question is, what is the dimension of $\text{Harm}(\mathbb{R}^n, S_n)$?
- 19
16
votes
2
answers
722
views
Minimal maximal subgroup of the symmetric group
The question is pretty much in the title: What is the maximal subgroup of $S_d$ of maximal index (so minimal size)? A slight variant (I am not sure if it leads to a different answer) is: what if we ...
- 96.4k
8
votes
2
answers
825
views
Linear relations among permutation matrices
Given a permutation $\sigma\in S_n$, let $P_\sigma$ denote the corresponding $n\times n$ permutation matrix. It is easy to see that for $n=3$, there is only one linear relation up to scaling given by $...
- 83
3
votes
0
answers
197
views
Partial orders on tabloids
Let $n \in \mathbb{N}$ and let $\lambda \vdash n$, a partition of $n$. By a $\lambda$-tabloid I mean a row-tabloid of shape $\lambda$. There is a well-known order on the set of $\lambda$-tabloids, ...
6
votes
0
answers
191
views
A particular proof of the Littlewood Richardson rule
Given $\lambda \subseteq \nu$ we define a tableau of shape $\nu\setminus \lambda$ and weight $\mu$ to be a map ${\sf T}: [\nu\setminus\lambda] \rightarrow \{1,\ldots, r\}$ such that $\mu_c=|\{ x \...
- 1,413
8
votes
2
answers
464
views
Faithful projective representations of symmetric groups
This is a reference request.
Do you know where I can find the dimensions of the faithful projective representations of $S_n$ and $A_n$ for $n\ge 5$?
Thank you in advance.
- 845
14
votes
4
answers
2k
views
Number of squares in a finite group
This was asked at MSE but never answered.
Let $G$ be a finite group and denote by $sq(G)$ the number of squares in $G$ i.e. the number of elements in $G$ which possess a square root. For example, if
...
- 1,411
3
votes
2
answers
1k
views
The number of subgroups of ${\frak S}_n$
Because of my interest in this question, I listed the subgroups of ${\frak S}_n$ for $1\le n\le4$. I found that the number of subgroups are, respectively, $1,2,6,24$. It might be a coincidence, or it ...
- 52.3k
6
votes
1
answer
445
views
references for faithful orthogonal (or unitary) representation of symmetric groups
Let $S_n$ be the symmetric group of $n$ points. I want to find references (or proofs) for the following statement (1).
(1). There does not exist any faithful orthogonal representation
$$
S_n\...
- 543
5
votes
1
answer
419
views
canonical action of symmetric groups on orthogonal groups
There is a canonical faithful orthogonal representation of the symmetric group $S_{n+1}$, for $n\geq 1$:
$$
S_{n+1}\to O(n)
$$
given as follows.
(1). I regard $O(n)$ as the isometry group of the unit ...
- 543
15
votes
1
answer
708
views
Cohomology of configuration space as a representation of the symmetric group
Let $X_n$ be the space of $n$ distinct labeled points in $\mathbb{R}^3$, which is equipped with an action of the symmetric group $S_n$. It is well known that the total cohomology of $X_n$ is ...
- 2,537
4
votes
2
answers
620
views
Explicit description of the principal block of the symmetric group
Let $k$ be a field of prime characteristic $p$ and $\Sigma_n$ be the symmetric group.
If I have a concrete $k[\Sigma_n]$-module $M,$ how to compute the direct summand corresponding to the principal ...
- 1,484
5
votes
1
answer
250
views
Relations among Young symmetrizers of non-standard tableaux
For any Young tableau, one can form the Young symmetrizer. I'm naturally interested in young symmetrizers coming from standard tableaux, but I'm forced to look at Young symmetrizers of non-standard ...
- 928
4
votes
1
answer
195
views
bijection between S-modules and Schur functors
Given a $\mathbb{S}$-module, we can construct a Schur functor, which is an endo functor in the category of vectorspaces. But given a Schur functor, how can we get back the $\mathbb{S}$-module? In ...
- 101
9
votes
1
answer
356
views
Diameter of the modified bubble-sort graph
The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...
- 406
5
votes
1
answer
437
views
Which subgroup order of the symmetric group is the most frequent?
Question: What is the most frequent order of subgroups of $S_n$?
More precisely: Let $a_k$ be the number of subgroups of $S_n$ with order $k$. What is the maximum of $a_k$?
This question came up ...
- 3,004
2
votes
0
answers
674
views
What is the definition of plethysm in the representation theory of permutation groups
Let $s_\lambda \circ s_\mu$ be a plethysm. Here let $\lambda, \mu$ be $m,n$ box Young diagrams.
I have seen the definition of plethysms in symmetric functions. I would like to understand the ...
- 349
1
vote
0
answers
165
views
Character sums over a fixed subset of skew tableaux
Let $f(\lambda)$ count the number standard young tableaux of shape $\lambda\vdash n$ and $\lambda=(\lambda_1,\cdots,\lambda_r)$. Let $\mu \vdash k$ be a partition for $k<n$. It is a consequence of ...
- 4,952
4
votes
0
answers
1k
views
Permutation-invariant matrix representation
The question guide says that Mathoverflow is for research level mathematics. While I do not perform research in mathematics (I study quantum chemistry), I believe this question is research-level ...
- 121
10
votes
4
answers
940
views
Is there a non-explicit characterization of the Specht modules?
It is a basic fact about the symmetric group $S_n$ that its irreducible representations are indexed by partitions of $n$.
My question is, can the association between partitions and irreps be ...
- 258
8
votes
1
answer
455
views
Is there any good survey on the hook length formula and related topics?
I am recently doing some research related to the hook length formula.
The hook formula counts the number of Young tableaux of certain type.
I find there are plenty of research already been done and ...
- 393
24
votes
0
answers
894
views
Nekrasov-Okounkov hook length formula
I am now reading the paper An explicit expansion formula for the powers of the Euler Product in terms of partition hook lengths by Guo-Niu Han. The author rediscovered what he calls the Nekrasov-...
- 609
1
vote
0
answers
237
views
Integral Cohomology of Symmetric Groups
Does anybody know a reference for the explicit description of the integral cohomology ring of $S_5$ and $S_6$. I can not find them anywhere in the internet. For $S_4$, I found C. B. Thomas's nice ...
- 131
16
votes
2
answers
818
views
Decomposing $(\mathbb C^n)^{\otimes m}$ as a representation of $S_n\times S_m$
$V=\mathbb C^n$ is a $\mathbb CS_n$-module, where $S_n$ is the symmetric group of degree $n$, via the representation sending a permutation to the corresponding permutation matrix. The tensor power $V^...
- 38.6k
3
votes
0
answers
153
views
Adding a row to a Young Tableau via Novelli-Pak-Stoyanovskii
Let $T_{\lambda}$ be the set of standard young tableaux (SYT) of shape $\lambda_1\geq \lambda_2\cdots\geq \lambda_n$. Now consider pushing a row $\mu$ with $\mu\geq \lambda_1$ onto $Y$ to give shape $\...
- 4,952
3
votes
0
answers
156
views
Exact growth rate of Longest Increasing Subsequence expectation
Let $S_n$ be the symmetric group, $\pi\in S_n$ a uniformly random permutation and $L_n:=L_n(\pi)$ denoting the length of the longest increasing subsequence (LIS). We know that $\lim_{n\rightarrow\...
- 4,952
4
votes
1
answer
759
views
cohomology ring of symmetric group of order $3$
Let $S_3$ be the symmetric group of order $3$. What is the cohomology ring
$$
H^*(S_3;\mathbb{Z})?$$
My attempt: I want to use mathematical induction on $n$ for $S_n$.
For $n=1$, $S_1$ is trivial. ...
- 1,990
12
votes
0
answers
249
views
What Is The Minimal Monomial of the Symmetric Group?
In the symmetric group $S_n$ what is the shortest sequence $c_1,\ldots,c_k\in S_n$ such that, for all $x\in S_n$ the following product of conjugates of $x$:
$$x^{c_1}x^{c_2}\ldots x^{c_k}$$
equals the ...
- 590
3
votes
0
answers
75
views
Is $LIS(\pi)+LIS(\sigma)+LIS(\sigma\pi^{-1})$ lower bounded?
In the title, $LIS$ stands for the length of longest increasing subsequence and Greek letters stand for permutations from symmetric group $S_n$.
Considering some cases such as $\pi^{-1}=\sigma=...
- 61
1
vote
0
answers
116
views
research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$
Is there any research on the structure/properties of permutation matrix/table with $(i,j)th$ entry as $\pi_j\circ \pi_i^{-1}$, where $\{\pi_1,\pi_2,...,\pi_{k!}\}=S_k$?
I know if we apply the ...
- 61
2
votes
0
answers
156
views
Special sets of involutions generating ${\rm S}_n$
For which positive integers $k$ and $r$ are there involutions $g_{n,i} \in {\rm S}_n$
$(n \in \mathbb{N}, \ i = 1, \dots, k)$ such that the following hold?:
for any $n$, the $g_{n,i}$ $(i = 1, \dots, ...
- 19.6k
12
votes
1
answer
861
views
Connected components $0-1$ matrices
Let $M$ be a $0-1$ matrix.
Here a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where ...
- 13.9k