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.

Filter by
Sorted by
Tagged with
7 votes
2 answers
361 views

What makes skew characters of the symmetric group special?

For integer partitions $\mu\subset\lambda$ we can define the skew character $\chi^{\lambda/\mu}$ (for example?) via the Littlewood-Richardson rule. Many combinatorial gadgets and algorithms extend in ...
Martin Rubey's user avatar
  • 5,503
8 votes
0 answers
186 views

Non-zero group determinant for symmetric group

Let $G$ be a finite group. Given complex numbers $x=\{x_g: g\in G\}$, one can define a $|G|\times |G|$ matrix $X$, with entries $X_{g,h} = x_{gh^{-1}}$. Let's consider $G$ being the symmetric group $...
gondolier's user avatar
  • 1,829
2 votes
0 answers
71 views

CAS for finite-dimensional complex representations of $S_n$

Does there exist a computer algebra system that can work with finite-dimensional complex representations of the symmetric groups on finitely many letters? It should have the following functionality: (...
user avatar
2 votes
1 answer
134 views

Minimum local permutation data needed to globally merge locally sorted sequences?

We have $k$ blocks of integer sequences $B_1,\dots,B_k$ where $B_i$ is a sequence $$a_{i,1},\dots,a_{i,n_i}$$ with $a_{i,j}\leq a_{i,j+1}$. Denote the permutation matrix $M_{\ell,\ell'}$ that merges $...
VS.'s user avatar
  • 1,816
0 votes
0 answers
122 views

Combinatorics of merging sequences from multinomial coefficients

If you have $m$ sequences $a_{11},\dots,a_{1n_1}$ through $a_{m1},\dots,a_{mn_m}$ each sorted in ascending order (assume there are no duplicates) then there is an unique way to merge them. How many ...
VS.'s user avatar
  • 1,816
11 votes
0 answers
248 views

Which irreducible representations of the symmetric group are eigenspaces of class sums?

In the setting of complex representations of finite groups, a class sum $1_C=\sum_{g\in C} g$ acts on an irreducible representation $V$ as $\lambda(C,V)\operatorname{Id}$, where $\lambda(C,V)=|C|\...
Hjalmar Rosengren's user avatar
5 votes
0 answers
229 views

Narayana numbers as character values?

The Catalan numbers show up as character values of the symmetric group: Let $\lambda = (n,n)$, a partition with two parts. Then $\chi^\lambda(1^{2n}) = \frac{1}{n+1}\binom{2n}{n}$, the $n$:th Catalan ...
Per Alexandersson's user avatar
2 votes
0 answers
92 views

Representations of the symmetric group from subgroups

Consider the finite symmetric group on $n$ letters $S_n$ and $\chi$ a representation on a finite dimensional complex vector space $V$. Further assume that you know the dimension of the invariant sub-...
Jaime's user avatar
  • 41
3 votes
0 answers
273 views

Constructing a centrally primitive idempotent in the group algebra of the symmetric group

Consider the group algebra of the symmetric group $ \mathbb{C} S_k$. Given some Young tableau $T$ of shape $\lambda$, let $a_{\lambda,T}$ and $b_{\lambda,T}$ be the row symmetrizer and column ...
Felix Huber's user avatar
12 votes
2 answers
945 views

How rare are unholey permutations?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$. Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
H A Helfgott's user avatar
  • 19.3k
11 votes
2 answers
699 views

A criterion for finite abelian group to embed into a symmetric group

Let $G$ be a finite abelian group. Write $G\approx \mathbb{Z}/p_1^{i_1}\mathbb{Z}\times\dots \mathbb{Z}/p_m^{i_m}\mathbb{Z}$, with $m\ge 0$, $p_1,\dots,p_m$ primes (not necessarily distinct) and $i_k\...
user avatar
3 votes
0 answers
133 views

Is there some sort of formula for $t(S_n)$?

Let $G$ be a finite group. Define $t(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > t(G)$ and $\langle X \rangle = G$, then $XXX = G$. Is there some sort of formula for $t(S_n)...
Chain Markov's user avatar
  • 2,618
2 votes
1 answer
94 views

Do highly symmetric cones have "small" supporting hyperplanes?

Let $C$ be a full-dimensional cone in $\mathbb{R}^{d}$, defined as the positive span of $c = {n \choose 3} \gg d$ vectors. $C$ is highly symmetric in the following sense: each such vector is labelled ...
GMB's user avatar
  • 1,379
9 votes
0 answers
109 views

Smith normal form of conjugacy class actions

This question was inspired by Smith Normal Form of a Cayley Graph of the Symmetric Group. Let $\mathbb{Q}S_n$ denote the group algebra over $\mathbb{Q}$ of the symmetric group $S_n$. Identify a ...
Richard Stanley's user avatar
15 votes
1 answer
606 views

Characteristic classes of symmetric group $S_4$

For the symmetric group $S_3$, it is classically known that \begin{equation} H^*(S_3;\mathbb{Z})\cong \mathbb{Z}[x,y]/(2x,6y,x^2-3y), \end{equation} where $|x|=2$ and $|y|=4$. Moreover, $x$ can be ...
Bob's user avatar
  • 439
6 votes
1 answer
260 views

Is there some sort of formula for $\tau(S_n)$?

Let $G$ be a finite group. Define $\tau(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > \tau(G)$, then $XXX = \langle X \rangle$. Is there some sort of formula for $\tau(S_n)$, ...
Chain Markov's user avatar
  • 2,618
11 votes
1 answer
538 views

Probability of words summing to $1$ in $S_n$ or $\mathrm{PGL}_2(n)$

$\DeclareMathOperator\PGL{PGL}\DeclareMathOperator\Conj{Conj}$Let $G$ be the symmetric group $S_n$ or the projective general linear group $\PGL_2(n)$. Let $X$ be a cyclically reduced word in the ...
LeechLattice's user avatar
  • 9,411
2 votes
1 answer
171 views

Enumeration and structure of abelian 2-subgroups of a symmetric group

I am struggling with a group theoretic problem arising in my research. Given a symmetric group $\Sigma_{n}$, let's consider all its abelian 2-subgroups up to conjugation. Is it possible to give a ...
Ling's user avatar
  • 311
7 votes
4 answers
1k views

Maximum conjugacy class size in $S_n$ with fixed number of cycles

Context: It is well known that given a permutation in $S_n$ with $a_i$ $i$-cycles (when written as a product of disjoint cycles), the size of the conjugacy class is given by $$ \frac{n!}{\prod_{j=1}^...
metallicmural99's user avatar
3 votes
0 answers
53 views

Groups that can occur as graph automorphisms of a fixed size graph

From theorem $4$ and corollary $1$ in this book we have that graph isomorphism has to do with automorphism group of a graph. We also know every group is the automorphism group of a graph by Frucht's ...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
146 views

A certain kind of permutations and transport of Bruhat chains under conjugation

Let $(W,S)$ be a finite Coxeter system. Let us consider the following situation: Let $v_1,v_2,w\in W$ such that $v_1=wv_2w^{-1}$. Let $s_{\beta_r}\ldots s_{\beta_1}$ be a reduced expression of $v_2$. ...
Christoph Mark's user avatar
1 vote
0 answers
176 views

Relation between groups $A_n$, $B_n$, $D_n$ and $S_n$ or inversions of random elements in Coxeter groups

First of of all I'm trying to find a general interpretation to the following facts below. Let's look at the property of Kendall-Mann numbers $M(n)$ which are row maxima of Triangle of Mahonian ...
Mikhail Gaichenkov's user avatar
3 votes
1 answer
256 views

Growth rate of $|{\rm cd}(S_n)|$

The question What is the order of magnitude for the function $n\mapsto |{\rm cd}(S_n)|$? The motivation In my research on character degrees of finite groups, I have in recent years been focusing on ...
John McVey's user avatar
  • 1,018
3 votes
1 answer
304 views

Covering with Deck group $\mathfrak{S}_3$

I am looking for the easiest possible example of a connected covering $X\to X/\mathfrak{S}_3$ ($\mathfrak{S}_3$ the third symmetric group). More precisely, I want $X$ and $X/\mathfrak{S}_3$ to be ...
FKranhold's user avatar
  • 1,623
1 vote
0 answers
96 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)...
eti902's user avatar
  • 835
30 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 ...
John McVey's user avatar
  • 1,018
5 votes
1 answer
269 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$ ...
darij grinberg's user avatar
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(\...
Anthonny's user avatar
  • 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_{\...
T. Amdeberhan's user avatar
2 votes
0 answers
132 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 ...
Anthonny's user avatar
  • 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 ...
Anthonny's user avatar
  • 151
1 vote
0 answers
127 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\...
FKranhold's user avatar
  • 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)....
MarcO's user avatar
  • 553
4 votes
0 answers
253 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 ...
Alexander Chervov's user avatar
1 vote
0 answers
64 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})=\...
neelkanth's user avatar
  • 141
15 votes
1 answer
701 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 ...
Saal Hardali's user avatar
  • 7,549
4 votes
1 answer
673 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 ...
MarcO's user avatar
  • 553
3 votes
0 answers
165 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}(\...
mrde05's user avatar
  • 39
19 votes
1 answer
725 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 ...
Timothy Chow's user avatar
10 votes
2 answers
730 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) ...
eti902's user avatar
  • 835
1 vote
1 answer
134 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 ...
neverevernever's user avatar
0 votes
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 ...
neverevernever's user avatar
13 votes
3 answers
608 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 ...
JeremyR's user avatar
  • 380
13 votes
2 answers
821 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}; \\...
Sam Hopkins's user avatar
  • 22.5k
4 votes
0 answers
95 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 ...
Dirk's user avatar
  • 809
6 votes
0 answers
195 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 ...
Chris Bowman's user avatar
  • 1,191
6 votes
1 answer
175 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 \...
Evan Jenkins's user avatar
  • 7,107
3 votes
1 answer
247 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 ...
Hans's user avatar
  • 2,169
8 votes
1 answer
200 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) = |\...
Dirk's user avatar
  • 809
15 votes
1 answer
710 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 ...
Chris Bowman's user avatar
  • 1,191

1 2 3
4
5
9