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
2 votes
0 answers
84 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^* = ...
Zach H's user avatar
  • 1,899
5 votes
1 answer
363 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 ...
verifying's user avatar
  • 311
3 votes
0 answers
101 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 ...
Vladimir Dotsenko's user avatar
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) \...
Chris Bowman's user avatar
  • 1,191
2 votes
0 answers
84 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$ ...
Marcel's user avatar
  • 2,510
7 votes
1 answer
265 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_{...
User371's user avatar
  • 537
1 vote
2 answers
494 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 ...
M Dean's user avatar
  • 349
10 votes
1 answer
251 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 ...
Igor Pak's user avatar
  • 16.3k
5 votes
0 answers
254 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^{\...
Max Hopkins's user avatar
4 votes
1 answer
455 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 $\...
fddwd's user avatar
  • 303
10 votes
3 answers
673 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 ...
Jeff Yelton's user avatar
  • 1,308
4 votes
1 answer
750 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}$...
Matthias Ludewig's user avatar
2 votes
1 answer
142 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, ...
Matt Samuel's user avatar
  • 1,978
5 votes
1 answer
195 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, (...
Per Alexandersson's user avatar
0 votes
1 answer
319 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 ...
Omid Hatami's user avatar
6 votes
1 answer
438 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&...
Matt Samuel's user avatar
  • 1,978
7 votes
2 answers
291 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 ...
user2052's user avatar
  • 1,401
6 votes
0 answers
123 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]...
Daniil Rudenko's user avatar
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 ...
Libli's user avatar
  • 7,210
12 votes
1 answer
377 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 ...
Christoph Mark's user avatar
2 votes
0 answers
79 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 ...
Christoph Mark's user avatar
3 votes
0 answers
158 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 ...
Anthony Labarre's user avatar
1 vote
2 answers
245 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 ...
Jianrong Li's user avatar
  • 6,101
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 ...
Mare's user avatar
  • 25.7k
4 votes
1 answer
522 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^{\...
Māris Ozols's user avatar
4 votes
1 answer
910 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 ...
Omid Hatami's user avatar
1 vote
0 answers
283 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 ...
user112249's user avatar
5 votes
3 answers
556 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 ...
Alexey Staroletov's user avatar
12 votes
0 answers
317 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 \...
Piotr Śniady's user avatar
6 votes
1 answer
283 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$. ...
Dirk's user avatar
  • 809
6 votes
2 answers
365 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 $...
T. Amdeberhan's user avatar
16 votes
1 answer
471 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 ...
JoS's user avatar
  • 681
3 votes
0 answers
63 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 ...
Turbo's user avatar
  • 13.6k
9 votes
1 answer
386 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 ...
HeinrichD's user avatar
  • 5,392
3 votes
2 answers
211 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 $...
T. Amdeberhan's user avatar
13 votes
1 answer
631 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 $\...
T. Amdeberhan's user avatar
6 votes
0 answers
191 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 ...
T. Amdeberhan's user avatar
6 votes
1 answer
393 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 ...
T. Amdeberhan's user avatar
9 votes
2 answers
747 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\...
T. Amdeberhan's user avatar
7 votes
2 answers
232 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. ...
Philip Engel's user avatar
3 votes
1 answer
267 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 ...
user avatar
2 votes
0 answers
166 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});\\ $$ ...
Chris Bowman's user avatar
  • 1,191
2 votes
1 answer
215 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 ...
Ashot's user avatar
  • 337
1 vote
2 answers
165 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 ...
Evan Wilson's user avatar
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 $\...
anonononon's user avatar
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 ...
Igor Makhlin's user avatar
  • 3,493
15 votes
2 answers
702 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(\...
Igor Makhlin's user avatar
  • 3,493
3 votes
0 answers
218 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 &...
user79456's user avatar
  • 401
22 votes
1 answer
575 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 ...
Sergey Sinchuk's user avatar
2 votes
1 answer
235 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 ...
T. Amdeberhan's user avatar

1
3 4
5
6 7
9