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.

learn more… | top users | synonyms

4
votes
1answer
117 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 ...
1
vote
1answer
186 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 ...
10
votes
1answer
211 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 ?
4
votes
0answers
115 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 $...
3
votes
2answers
219 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,
3
votes
2answers
338 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 ...
3
votes
0answers
51 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 ...
11
votes
2answers
517 views

The Simultaneous Conjugacy Problem in the symmetric group $S_N$

We are interested in the following notions in the case $G=S_N$, the symmetric group on $\{1,\dots,N\}$. Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define $$(g_1,\...
6
votes
2answers
478 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-...
5
votes
1answer
339 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 ...
5
votes
2answers
355 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,...
0
votes
0answers
65 views

A question about divided differences

I want to ask a question about divided differences. Let $n\equiv0,1 \pmod 4$ is a positive integer. We know that for any polynomial $f\in \mathbb{Z}[x_1,x_2,\cdots,x_n]$, $$\partial_{w_0}(f)=\left(\...
4
votes
1answer
118 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 ...
6
votes
1answer
149 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 ...
0
votes
0answers
50 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 ...
0
votes
0answers
6 views

Probability of disjoint cycles

Let $c_1,c_2\in S_n$ be two disjoint cycles of length $|c_1|$ and $|c_2|$ respectively. Let $I(c_i)$ be the coordinates on which permutation $c_i$ acts at $i\in\{1,2\}$. Note by choice we have $I(c_1)\...
6
votes
1answer
136 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_{\...
4
votes
1answer
156 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 ...
8
votes
4answers
731 views

universality of Macdonald polynomials

I have been recently learning a lot about Macdonald polynomials, which have been shown to have probabilistic interpretations, more precisely the eigenfunctions of certain Markov chains on the ...
3
votes
1answer
188 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!)$-...
11
votes
2answers
657 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), ...
10
votes
1answer
257 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 ...
5
votes
2answers
153 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, \...
3
votes
1answer
98 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}...
9
votes
1answer
521 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 ...
9
votes
2answers
361 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 ...
11
votes
1answer
321 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|}{...
6
votes
1answer
154 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,\...
14
votes
2answers
489 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 $(...
4
votes
3answers
135 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?
6
votes
1answer
267 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)$ ...
59
votes
4answers
3k views

Is ${\rm S}_6$ the automorphism group of a group?

The automorphism group of the symmetric group $S_n$ is $S_n$ when $n$ is not $2$ or $6$, in which cases it is respectively $1$ and the semidirect product of $S_6$ with the (cyclic) group of order $2$. ...
15
votes
2answers
440 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 ...
16
votes
1answer
460 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 ...
2
votes
0answers
98 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 ...
3
votes
0answers
52 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)$?
2
votes
0answers
76 views

$\mathbb{C}[x_1, \dots, x_n]$ is a free $\mathbb{C}[x_1, \dots, x_n]^{S_n}$-module with certain generators [duplicate]

Let the symmetric group $S_n$ act on $\mathbb{R}^n$ by permutation of coordinates. This makes $S_n$ a subgroup of $\text{GL}_n(\mathbb{R}$ and the algebra $\mathbb{C}[x_1, \dots, x_n]^{S_n}$ is the ...
7
votes
1answer
277 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 $...
1
vote
0answers
65 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, ...
5
votes
0answers
91 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 \...
6
votes
2answers
291 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.
13
votes
4answers
943 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 ...
26
votes
4answers
1k views

What are the applications of immanants?

Definitions of determinant: $\det(A) = \sum_{\sigma \in S_n}(-1)^{\operatorname{sgn} \sigma}\prod_{i}a_{i, \sigma(i)}$ and permanent: $\mathrm{per}(A) = \sum_{\sigma \in S_n}\prod_{i}a_{i, \sigma(i)...
4
votes
1answer
111 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\...
6
votes
1answer
387 views

In general, are 'Young symmetrisers' given by Littlewood-Richardson 'Orthogonal projection Operators'?

Consider $V^{\otimes n}$ where $V$ is vector space and the representation of GL(V) acting in the usual way. Now if I consider tensor products or plethysms of irreducible spaces, this is not in general ...
4
votes
1answer
232 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 ...
15
votes
1answer
277 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 ...
4
votes
2answers
324 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 ...
4
votes
1answer
103 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 ...
16
votes
3answers
1k views

Rhombus tilings with more than three directions

The point of this question is to construct a list of references on the following subject: Fix vectors $v_1$, $v_2$, ..., $v_g$ in $\mathbb{R}^2$, all lying in a half plane in that cyclic order. I am ...