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
1
vote
0
answers
97
views
Two versions of the Murnaghan-Nakayama rule
I have always see the following Murnaghan-Nakayama rule for a partition $\lambda$ and a permutation $\sigma \in \mathfrak{S}_n$ of cycle structure $(\sigma_1, ..., \sigma_n)$:
$$
\chi_{\lambda}(\sigma)...
- 891
31
votes
2
answers
1k
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 ...
- 1,068
5
votes
1
answer
290
views
Toggles for non-broken-circuit sets in matroids
Let $M$ be a matroid with ground set $E$. If $t$ is a total order on $E$, and if $S$ is a nonempty subset of $E$, then $\max_t S$ will mean the $t$-largest element of $S$ (that is, the maximum of $S$ ...
- 33.8k
2
votes
0
answers
90
views
How to prove this identity on summations and partitions?
Let $f$ be a symmetric function of $s$ variables. The identity is
$$\sum_{all \ k's}^\infty f(k_1,k_2,k_3,...,k_s)=\sum_{n=s}^\infty \sum_{\lambda\vdash n}\frac{s!\prod_l \lambda_l}{z_\lambda} f(\...
- 151
10
votes
2
answers
1k
views
A cancellation property for permutations?
Let $S_n$ be the group of $n$-permutations. Denote the number of inversions of $\sigma\in S_n$ by $\ell(\sigma)$.
QUESTION. Assume $n>2$. Does this cancellation property hold true?
$$\sum_{\...
- 43.2k
2
votes
0
answers
135
views
A symmetric function that appears in the coefficients of a power expansion
Let's say we have the expression
$$\sum_{k_1=1}^\infty\sum_{k_2=1}^\infty\sum_{k_3=1}^\infty\sum_{k_4=1}^\infty\sum_{k_5=1}^\infty x^{k_1+k_2+k_3+k_4+k_5} f(k_1,k_2+k_3,k_4+k_5)$$
where $f(a,b,c)$ is ...
- 151
1
vote
0
answers
93
views
Has this result about the number of permutations of a given cycle type (or centralizers) been proved?
I was playing with the cardinality of conjugacy classes of the symmetric groups, which we know is the number of permutations of a given cycle type and there is a natural one-to-one correspondence ...
- 151
1
vote
0
answers
130
views
Word length norm in the symmetric group $\mathfrak{S}_r$
Consider on the symmetric group $\mathfrak{S}_r$ the generating system $\{\tau_i;\,1\le i\le r-1\}$ with $\tau_i = \langle i,i+1\rangle$ and the corresponding word length norm $N$. Now let $\tau\in\...
- 1,623
2
votes
0
answers
49
views
Explicit symmetry adapted basis for the symetric square of the standard representation
I already posted a related question here, which is more detailed: https://math.stackexchange.com/posts/2786382/edit
The permutation group $S_n$ has standard representation $S^{(n-1,1)}$ (irreducible)....
- 583
4
votes
0
answers
266
views
Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)
In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...
- 24.9k
1
vote
0
answers
66
views
To find $\dim(D^{\mu})=\dim\frac{S^{\mu}}{S^{\mu}\cap S^{\mu\perp}}$
Let $S_6$ be the symmetric group of degree $6$ and $F$ be any finite field of characteristic $2.$ Then $2$-regular partition of $6$ are $(5,1)$, $(4,2)$ and $(3,2,1)$ . I have to find $$\dim(D^{\mu})=\...
- 141
15
votes
1
answer
748
views
Schur-Weyl duality and q-symmetric functions
Disclaimer: I'm far from an expert on any of the topics of this question. I apologize in advance for any horrible mistakes and/or inaccuracies I have made and I hope that the spirit of the question ...
- 7,789
4
votes
1
answer
745
views
Decomposition into irreducible of a representation of the wreath product $S_d\wr S_n$
Let $S_d, S_n$ be the permutation groups of $d,n$ elements.
An intuitive representation of the wreath product $S_d\wr S_n$ is $V_1\otimes...\otimes V_n$, where each $V_i$ is of dimension $d$. Writing ...
- 583
3
votes
0
answers
174
views
Induced Homomorphism on Cohomology of Symmetric Group 3
For the symmetric group $S_3$, there is an inclusion $i:\mathbb{Z}/3\mathbb{Z}\hookrightarrow S_3$. How can I assert that the induced homomorphism $$i^{\ast}:H^{n}(S_3,\mathbb{Z})\rightarrow H^{n}(\...
- 39
20
votes
1
answer
884
views
Young's natural representation of the symmetric group
The literature on the representation theory of the symmetric group contains some terminology that I find puzzling, and I am wondering if someone here knows the full story.
One of the standard ways to ...
- 82.7k
10
votes
2
answers
781
views
Closed formulas for the character of the symmetric group
I know the Murnaghan–Nakayama rule, but I am wondering if there is any closed formulas for the character of the symmetric group. I know the following:
$$\chi_{n}(\sigma) = 1$$
$$\chi_{11...1}(\sigma) ...
- 891
1
vote
1
answer
136
views
The number of permutations with a special condition
Suppose we are considering $S_n$. For any permutation, let $h$ be the number of derangement and $N$ be the number of cycles with length no less than 2.
I'm interested in the number of permutations ...
- 1,495
1
vote
3
answers
2k
views
The number of permutations with specified number of cycles and fixed points
I'm interested in the number of permutations for a specified number of fixed points and cycles.
Suppose we are in $S_n$. For any permutation in $S_n$, let $h$ be the number of changed points (the ...
- 1,495
13
votes
3
answers
678
views
Is this sum of cycles invertible in $\mathbb QS_n$?
I am interested the following element of the group algebra $\mathbb{Q}S_n$:
\begin{align}
\phi_n=2e+(1\ 2)+(1\ 2\ 3)+\dotsb+(1\ldots n)
\end{align}
where $e$ is the identity permutation. My question ...
- 380
13
votes
2
answers
841
views
Cycle generating function of permutations with only odd cycles
Let $\mathrm{ODD}(n)$ be the set of permutations in $\mathfrak{S}_n$ whose cycle lengths are all odd. It is known that
$$ \#\mathrm{ODD}(n) = \begin{cases} ((n-1)!!)^2 &\textrm{ if $n$ is even}; \\...
- 24.2k
4
votes
0
answers
98
views
Ref. request: Enumerating elements of Bruhat cells
Given a field $F$ and a natural number $n$, let $B$ be the group of lower triangular, invertible $n \times n$ matrices over $F$. Then
$$GL_n(F) = \biguplus_{\pi \in S_n} B \pi B,$$
where we embed the ...
- 809
6
votes
0
answers
206
views
Combinatorics of $p$-Kazhdan--lusztig polynomials
When can we (and can we not!) understand the dimensions of simple modules, $D(\lambda)$, of symmetric groups in a combinatorial fashion?
Let's assume that I'm going to try to do this using the theory ...
- 1,413
6
votes
1
answer
181
views
Can $S_n$ be partitioned into subsets containing an involution and satisfying $∀σ≠τ, ∃j$ s.t. $σ(j)≠τ(j),σ^{−1}(j)=τ^{−1}(j)$?
Background
Let $\sigma, \tau \in S_n$. We will say that $\sigma$ and $\tau$ are locally orthogonal and write $\sigma \perp \tau$ if there exists $j \in \{1, 2, \ldots, n\}$ such that $\sigma(j) \neq \...
- 7,237
3
votes
1
answer
258
views
Cycle Structure of a Permutation Based on the Binary Representation
This is a question I posted on math.stackexchange.com before but never got an answer. I am cross-posting it here.
Define a permutation $\sigma$ on the set $X=\{1,2,...,n\}$, $n$ is a natural number ...
- 2,239
8
votes
1
answer
203
views
Reference request: Coxeter length and irreducible characters
Let $S_n$ be the symmetric group on $\{1,2,\ldots, n\}$ and $\ell$ the Coxeter length on $S_n$. There is a well-known formula to compute this length, namely for a $\pi \in S_n$ we have
$$\ell(\pi) = |\...
- 809
15
votes
1
answer
749
views
Character theoretic proof of the Littlewood–Richardson rule?
The Littlewood–Richardson coefficients are the multiplicities
$$
c(\lambda,\mu,\nu)= \dim_{\mathbb{C}}\operatorname{Hom}_{S_n}(S(\nu),S(\lambda/\mu))
$$
and the Littlewood–Richardson rule says that ...
- 1,413
2
votes
0
answers
85
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^* = ...
- 1,989
5
votes
1
answer
365
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 ...
- 311
3
votes
0
answers
103
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 ...
- 16.9k
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) \...
- 1,413
2
votes
0
answers
85
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$ ...
- 2,552
7
votes
1
answer
272
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_{...
- 517
1
vote
2
answers
513
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 ...
- 347
10
votes
1
answer
269
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 ...
- 17k
5
votes
0
answers
267
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^{\...
- 297
4
votes
1
answer
465
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 $\...
- 313
10
votes
3
answers
734
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 ...
- 1,298
4
votes
1
answer
814
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}$...
- 9,853
2
votes
1
answer
148
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, ...
- 2,168
5
votes
1
answer
198
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, (...
- 15.8k
0
votes
1
answer
353
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 ...
- 901
6
votes
1
answer
452
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&...
- 2,168
7
votes
2
answers
307
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 ...
- 1,411
6
votes
0
answers
124
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]...
- 4,316
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 ...
- 7,300
12
votes
1
answer
385
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 ...
- 1,066
2
votes
0
answers
81
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 ...
- 1,066
3
votes
0
answers
164
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,164
1
vote
2
answers
259
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,201
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 ...
- 26.5k