arXiv:1512.02170v2 [math.RT] 11 Jan 2016

The Littlewood-Richardson rule for wreath
products with symmetric groups and the quiver
of the category F ≀ FIn
Itamar Stein∗
Department of Mathematics
Bar Ilan University
52900 Ramat Gan
Israel

Abstract
We give a new proof for the Littlewood-Richardson rule for the wreath
product F ≀Sn where F is a finite group. Our proof does not use symmetric
functions but more elementary representation theoretic tools. We also
derive a branching rule for inducing the natural embedding of F ≀ Sn to
F ≀ Sn+1 . We then apply the generalized Littlewood-Richardson rule for
computing the ordinary quiver of the category F ≀ FIn where FIn is the
category of all injective functions between subsets of an n-element set.

1

Introduction

Let G be a finite group and let H ≤ G be a subgroup. By Maschke’s theorem,
group algebras (over C) are semisimple so every group representation is a finite
direct sum of irreducible ones. A basic question in the representation theory
of finite groups is the following one: Let V be some H-representation, what
∗ This paper is part of the author’s PHD thesis, being carried out under the supervision of
Prof. Stuart Margolis. The author’s research was supported by Grant No. 2012080 from the
United States-Israel Binational Science Foundation (BSF).

1

is the decomposition of the inducted representation IndG
H V into irreducible Grepresentations? Alternatively, let U be some G-representation, what is the
decomposition of the restriction ResG
H U into irreducible H-representations? By
Frobenius reciprocity, answering one of these questions essentially answers the
other one. Moreover, since both induction and restriction are additive, it is
enough to consider the case where U or V are irreducible representations. Even
considering this reduction, the question, in general, is very difficult. If G = Sn
the answer is known for certain natural choices of H and these solutions are often
called branching rules. The most classical case is where H = Sn−1 viewed as
the subgroup of all permutations that fix n. An important generalization is the
Littlewood-Richardson rule which gives the answer for the case H = Sk × Sn−k .
Let F and G be finite groups such that G acts on the left of a finite set X. We
denote by F ≀X G the wreath product of F and G. The representation theory
of F ≀X G is a well-studied subject (see [3] and [6, Chapter 4]) and the case
G = Sn with the natural action on {1, . . . , n} is of special importance. Finding
generalizations for the branching rules is a natural question. The “classical”
branching rule for inducing from F ≀ Sn to F ≀ Sn+1 was found by Pushkarev
[10]. In this paper we generalize the Littlewood-Richardson rule to the group
F ≀ Sn . After the present paper was already circulating, we became aware of the
paper [5] by Ingram, Jing and Stitzinger, where the same result was obtained
using symmetric functions. However, our approach is different. We use only
elementary representation theoretic tools and base our proof on the explicit
description of the irreducible representations of F ≀ Sn . In Section §5 we use the
generalized Littlewood-Richardson rule to retrieve Pushkarev’s result.
Then we turn to give an application to the representation theory of a natural
family of categories. Denote by FI the category of finite sets and injective
functions. The representation theory of FI is currently under active research
which was initiated in [4]. There is also research on the representation theory
of the wreath product F ≀ FI (see [8, 11, 13]). We will be interested here in the
finite version of this category. We denote by FIn the category of all subsets of
{1, . . . , n} and injective functions. In Section §6 we will give a description of the
ordinary quiver of the algebra of F ≀ FIn . The case where F is the trivial group
was originally done by [2] and a simple proof was later given in [9]. For the
general case, we imitate the method of [9] but where they use usual branching
rule for Sn we will use the generalization for F ≀ Sn .

2

2
2.1

Preliminaries
Wreath product

Throughout this paper F and G will be finite groups such that G acts on the
left of some finite set X. An element f ∈ F X is a function from X to F . Note
that F X is a group, multiplication being defined componentwise. We can also
define a left action of G on F X by
(g ∗ f )(x) = f (g −1 x).
It is easy to verify that this is indeed a left action.
Definition 2.1. The wreath product of F with G denoted F ≀X G is the semidirect product F X ⋊ G. In other words, it is the set F X × G with multiplication
given by
(f, g) · (f ′ , g ′ ) = (f (g ∗ f ′ ), gg ′ ).
If H ≤ G is a subgroup, we can restrict the action on X to H and get the group
F ≀X H which is a subgroup of F ≀X G.
Clearly, Sn acts on {1, . . . , k} (for n ≤ k) by permuting the first n elements and
fixing the other ones. We refer to this action as the standard action of Sn on
{1, . . . , k}. In this case we denote the wreath product with F by F ≀k Sn . The
focus of this paper will be the case where k = n and we will simply denote this
group by F ≀ Sn . There is a very natural way to think of this group. Recall
that we can identify Sn with the group of permutation matrices, that is, a
permutation π ∈ Sn can be identified with an n × n matrix A where

Ai,j


1 π(j) = i
=
.
0 otherwise

Similarly, we can identify F ≀ Sn with a group of matrices, but here the non-zero
entries can be any element of F . In other words, the tuple (f, π) is identified
with the n × n matrix A where
Ai,j


f (i) π(j) = i
.
=
0
otherwise

The multiplication of F ≀ Sn is then identified with matrix multiplication when
3

one assumes
0 · a = a · 0 = 0,

a+0=0+a=a

for every a ∈ F .
The following fact will be of use (see [3, Proposition 2.1.3] for proof).
Lemma 2.2 (Distributivity of the wreath product). Let G1 and G2 be groups
acting on disjoint sets X1 and X2 respectively, so G1 × G2 acts on the disjoint
˙ 2 . Then
union X = X1 ∪X
(F ≀X1 G1 ) × (F ≀X2 G2 ) ∼
= F ≀X (G1 × G2 ).

2.2

Complex group representations

We only consider representations over C in this paper. A G-representation is a
pair (U, ρ) where U is a finite dimensional vector space and ρ : G → End(U )
is a group homomorphism. This is equivalent to an action of G on the vector
space U by linear transformations. We will sometimes omit the homomorphism
and say that U is a G-representation. For u ∈ U we will usually write g · u
or even gu instead of ρ(g)(u). Let U and V be two G-representations. We
∼ V ) if there is a vector space
say that U is isomorphic to V (and write U =
isomorphism T : U → V such that T (g · u) = g · T (u) for every g ∈ G and u ∈ U .
The direct sum U ⊕ V of two G-representations is again a G-representation
according to g · (u + v) = gu + gv. A subvector space V ⊆ U is called a
subrepresentation if it is closed under the action of G, that is, g · v ∈ V for
all g ∈ G and v ∈ V . A non-zero G-representation U is called irreducible
if its only subrepresentations are 0 and U . We denote the set of irreducible
representations of G (up to isomorphism) by Irr G. It is well known that every
G-representation is a finite direct sum of irreducible representations and that
the number of different irreducible G-representations (up to isomorphism) is the
number of conjugacy classes of G. We denote the trivial representation of any
group G by trG . Recall that if V is a G-representations, then V ∗ = Hom(V, C)
is also a G-representation with operation (g · ϕ)(v) = ϕ(g −1 v). Let U and V be
G-representations. The inner tensor product U ⊗ V is again a G-representation
with action defined by g · (u ⊗ v) = gu ⊗ gv and extending linearly. Now,
assume that U1 and U2 are G1 and G2 -representations respectively. The outer
tensor product U1 ⊗ U2 of U1 and U2 is the (G1 × G2 )-representation where
(g1 , g2 )·(u1 ⊗u2 ) = (g1 u1 )⊗(g2 u2 ). Although the two types of tensor product can
4

be distinguished by the context we prefer using different notation for outer tensor
product, denoting it by ⊠. Likewise, the simple tensors of U ⊠V will by denoted
by u ⊠ v. It is well known that Irr(G1 × G2 ) = {U ⊠ V | U ∈ Irr G1 , V ∈ Irr G2 }.
Another simple observation will be important.
Lemma 2.3. Let U1 and V1 (U2 and V2 ) be G1 (respectively, G2 )-representations.
Then
(U1 ⊠ U2 ) ⊗ (V1 ⊠ V2 ) ∼
= (U1 ⊗ V1 ) ⊠ (U2 ⊗ V2 )
as (G1 × G2 )-representations.
Proof. Define T : (U1 ⊠ U2 ) ⊗ (V1 ⊠ V2 ) → (U1 ⊗ V1 ) ⊠ (U2 ⊗ V2 ) by
T ((u1 ⊠ u2 ) ⊗ (v1 ⊠ v2 )) = (u1 ⊗ v1 ) ⊠ (u2 ⊗ v2 )
which clearly extends to a vector space isomorphism and also
T ((g1 , g2 ) · ((u1 ⊠ u2 ) ⊗ (v1 ⊠ v2 ))) = T ((g1 u1 ⊠ g2 u2 ) ⊗ (g1 v1 ⊠ g2 v2 ))
= (g1 u1 ⊗ g1 v1 ) ⊠ (g2 u2 ⊗ g2 v2 )
= (g1 , g2 ) · T ((u1 ⊠ u2 ) ⊗ (v1 ⊠ v2 ))
as required.
The character χU of the G-representation (U, ρ) is the function χU : G → C
defined by χU (g) = trace(ρ(g)). Recall that the multiplicity U ∈ Irr G as an
irreducible constituent in some G-representation V is given by the inner product
hχU , χV i =

1 X
χU (g)χV (g).
|G|
g∈G

Recall also that χV ∗ (g) = χV (g) and χU⊠V ((g1 , g2 )) = χU (g1 )χV (g2 ). In order
to simplify notation, we will usually omit the χ and write U also for the character
of U . Hence the above inner product will be written as
hU, V i =

1 X
U (g)V (g).
|G|
g∈G

5

2.3

Restriction and induction

Let (U, ρ) be a G-representation and let H ≤ G be a subgroup. The restriction
G
of (U, ρ) to H denoted (ResG
H U, ResH ρ) is an H-representation defined by

ResG
H ρ(h)(u) = ρ(h)(u)
that is, restricting the homomorphism to the subgroup H. Note that dim ResG
HU
= dim U and if U is an irreducible G-representation then ResG
H U does not have
to be an irreducible H-representation. Let (U, ρ) be an H-representation, the
G
induction to G denoted (IndG
H U, IndH ρ) is the tensor product

IndG
H U = CG ⊗ U
CH

where the G action is given by
g · (s ⊗ u) = (gs) ⊗ u
where s ∈ CG and u ∈ U . However, we will usually use the following more
concrete description. Choose S = {s1 , . . . , sl } to be representatives of the left
cosets of H in G (where l = [G : H]). Note that any element g ∈ G can be
written in a unique way as g = si h where si ∈ S and h ∈ H. Every element of
IndG
H U is a formal sum of the form
α1 (s1 , u1 ) + . . . + αl (sl , ul )
where ui ∈ U and αi ∈ C. In other words, as a vector space IndG
H U is

l
M

U,

i=1

that is, l copies of U . The action is defined on elements of the form (si , u) by
g · (si , u) = (sj , h · u)
where sj and h are unique such that gsi = sj h. The required action is given by
extending linearly. Note that dim IndG
H U = [G : H] dim U . It is important to
G
mention that the representations IndH U and ResG
H V depend not only on the
groups G and H but also on the specific embedding of H into G. Hence we
will have to give the specific embeddings when discussing these representations.
Both induction and restriction are transitive and additive, that is, if K ≤ H ≤ G

6

then
G
H
∼
IndG
H IndK U = IndK U,

G
G
∼
IndG
H (U ⊕ V ) = IndH U ⊕ IndH V

and
G
G
∼
ResH
K ResH U = ResK U,

G
G
∼
ResG
H (U ⊕ V ) = ResH U ⊕ ResH V.

For restriction this is a trivial statement and for induction the proof is [3, Propositions 1.1.10 and 1.1.11]. An important fact that relates induction to restriction
is the following one (for proof see [3, Corollary 1.1.20 ]).
Theorem 2.4 (Frobenius reciprocity). Let H ≤ G and let U and V be G and
H-representations respectively. Then the multiplicity of V in ResG
H U equals the
multiplicity of U in IndG
HV.
Using characters, Frobenius reciprocity can be written as the following equality
G
hIndG
H V, U i = hV, ResH U i.

2.4

Representations of the symmetric group

We will recall some elementary facts regarding the representation theory of the
symmetric group. More details can be found in [6, 12]. Recall that an integer
composition of n is a tuple λ = [λ1 , . . . , λk ] of non-negative integers such that
λ1 + · · · + λk = n while an integer partition of n (denoted λ ⊢ n) is an integer
composition such that λ1 ≥ λ2 ≥ · · · ≥ λk > 0. From now on, when dealing
with a partition λ we will write its elements in superscript λ = [λ1 , . . . , λk ]
because we want to reserve the subscript for multipartitions. Note that 0 has
one partition, namely the empty partition, denoted by ∅. We can associate to
any partition λ a graphical description called a Young diagram, which is a table
with λi boxes in its i-th row. For instance, the Young diagram associated to
the partition [3, 3, 2, 1] of 9 is:

We will identify the two notions and regard integer partition and Young diagram
as synonyms. It is well known that irreducible representations of Sn are indexed
by integer partitions of n. We denote the irreducible representation associated
to the partition λ (also called its Specht module) by S λ . Explicit description of
S λ can be found in [12, Section 2.3]. It will be often convenient to draw the
diagram λ instead of writing S λ . For instance we may write
7

⊕
instead of: S λ ⊕ S δ for partitions λ = [3] and δ = [2, 1].
We will now describe several branching rules for Sn . Here the advantage of
using Young diagrams becomes clear. Recall that we can think of Sn as the
group of all permutations of {1, . . . , n + 1} that leave n + 1 fixed. Hence, we can
view Sn as a subgroup of Sn+1 . We call this the standard embedding of Sn into
Sn+1 . In this case the branching rules are well known and very natural (proof
can be found in [12, Section 2.8]).
Theorem 2.5 (Classical branching rules). Let λ ⊢ n be a Young diagram.
1. Denote by Y + (λ) the set of Young diagrams obtained from λ by adding
one box. Then
M
S
IndSnn+1 S λ =
Sγ .
γ∈Y + (λ)

2. Similarly, denote by Y − (λ) the set of Young diagrams obtained from λ by
removing one box. Then
ResSSnn−1 S λ =

M

Sγ .

γ∈Y − (λ)

Example 2.6. Let λ =

then
IndSS43 S λ =

⊕

⊕

and
ResSS32 S λ =

⊕

.

We now turn our attention to the Littlewood-Richardson branching rule. If
we identify Sk (Sr ) with the group of all permutations of {1, . . . , k + r} that
leave {k + 1, . . . , k + r} (respectively, {1, . . . , k}) fixed we can view Sk × Sr as a
subgroup of Sk+r . Given λ ⊢ k and δ ⊢ r the Littlewood–Richardson rule gives
S
(S λ ⊠ S δ ) into irreducible Sk+r -representations.
the decomposition of IndSk+r
k ×Sr

8

In other words, if we write this decomposition as
M

S

(S λ ⊠ S δ ) =
IndSk+r
k ×Sr

cγλ,δ S γ

γ⊢(k+r)

it gives a combinatorial interpretation for the coefficients cγλ,δ (called the Littlewood–Richardson coefficients). The aim of this paper is to generalize the
classical branching rules and the Littlewood-Richardson rule to the group F ≀ Sn
for any finite group F . Although the details of the Littlewood-Richardson rule
for Sn will not be essential in the sequel, we give them here for the sake of
completeness. For this we have to introduce some more notions. First we generalize the notion of a Young diagram. For k ≤ n, let λ = (λ1 , · · · , λr ) ⊢ k
and γ = (γ 1 , · · · , γ s ) ⊢ n be partitions such that λi ≤ γ i for every 1 ≤ i ≤ r.
The skew diagram γ/λ is the diagram obtained by erasing the diagram λ from
the diagram γ. For instance if λ = [2, 1] and γ = [4, 3, 1] then γ/λ is the skew
diagram
.
A skew tableau is a skew diagram whose boxes are filled with numbers. We call
the original diagram the shape of the tableau. Let t be a skew tableau with n
boxes such that the number of boxes with entry i is δ i . The content of t is the
composition δ = [δ 1 , . . . , δ l ]. We say that a skew tableau is semi-standard if its
columns are increasing and its rows are non-decreasing. For instance

1 1
2 3

(2.1)

2

is a semi-standard skew tableau of shape [4, 3, 1]/[2, 1] with content [2, 2, 1]. The
row word of a skew tableau t is the string of numbers obtained by reading the
entries of t from right to left and top to bottom. For instance, the row word of
tableau 2.1 is 11322. A string of numbers is called a lattice permutation if for
every prefix of this string and for every number i, there are no less occurrences
of i than occurrences of i + 1. For instance, the string 11322 is not a lattice
permutation since the prefix 113 contains one 3 and no 2’s. Now we can state
the Littlewood-Richardson rule (for proof see [6, Theorem 2.8.13]).
Theorem 2.7. The Littlewood-Richardson coefficient cγλ,δ is the number of
9

semi-standard skew tableaux of shape γ/λ with content δ whose row word is
a lattice permutation.
Example 2.8. If λ = [2, 1], δ = [3, 2] and γ = [4, 3, 1] then cγλ,δ = 2 since there
are two skew tableaux with the required properties. These are:
1 1
2 2

1 1
1 2

1

2

Remark 2.9. Note that for many values of γ we have cγλ,δ = 0, that is, S γ is not
S

an irreducible constituent of IndSk+r
(S λ ⊠ S δ ). For instance, this happens for
k ×Sr
every γ such that γ i < λi for some i.
Remark 2.10. Note that the classical branching rule for induction can be deduced from the Littlewood-Richardson rule if we set r = 1.

3

Representation theory of F ≀ Sn

The goal of this section is to describe the irreducible representations of F ≀ Sn .
We follow the approach of [3], but we introduce different notation that will be
more convenient to our purpose. We also prove some technical lemmas that will
be of later use.

3.1

Inflation

Definition 3.1. Let G be a finite group and let N E G be a normal subgroup.
Let (U, ρ) be a representation of G/N . We denote by (U , ρ) the G-representation
defined as follows. As a vector space, U = U , and the G-action is
ρ(g)(u) = ρ(gN )(u) ∀u ∈ U.
Following [3] we call U the inflation of U .
Note that dim U = dim U and if U is an irreducible G/N -representation then
U is an irreducible G-representation as well.
The specific case we will be interested in is the following. If F and G are finite
groups, then F X E F ≀X G and (F ≀X G)/F X ∼
= G so any G-representation U
can be inflated into an (F ≀X G)-representation with action
(f, g) · u = gu.
10

Lemma 3.2. Let G1 and G2 be groups acting on the disjoint sets X1 and X2
respectively and let U1 and U2 be G1 and G2 -representations. Note that Ui is
an (F ≀Xi Gi )-representation and U1 ⊠ U2 is an (F ≀X (G1 × G2 ))-representation
˙ 2 ). Then
(where X = X1 ∪X
U1 ⊠ U2 ∼
= U1 ⊠ U2
as (F ≀X1 G1 ) × (F ≀X2 G2 ) ∼
= F ≀X (G1 × G2 )-representations.
Proof. As vector spaces both representations are spanned by elements of the
form u1 ⊠ u2 for ui ∈ Ui . An element ((f1 , g1 ), (f2 , g2 )) ∈ F ≀X1 G1 × F ≀X2 G2
acts in both representations by
((f1 , g1 ), (f2 , g2 )) · (u1 ⊠ u2 ) = g1 u1 ⊠ g2 u2 .

3.2

Conjugacy and extensions

Let N E G be a normal subgroup. Then we can define an action of G on the
set Irr N . For every (U, ρ) ∈ Irr N we define g · (U, ρ) = (g U,g ρ) where
g

U = U,

g

ρ(n) = ρ(g −1 ng)

for all g ∈ G and n ∈ N .
In the case of F X E F ≀ G this action has a simple form. Recall that the set of
irreducible representations of F X is
Irr F X = {( ⊠ Ux , ⊠ ρx ) | (Ux , ρx ) ∈ Irr F }.
x∈X

x∈X

Lemma 3.3 ([3, Lemma 2.4.1]). Denote (U, ρ) = ( ⊠ Ux , ⊠ ρx ) ∈ Irr F X then
x∈X

x∈X

(f, g) · U = ⊠ Ug−1 x
x∈X

for all (f, g) ∈ F ≀ G.
Definition 3.4. Assume that H ≤ G satisfies that (Uhx , ρhx ) ∼
= (Ux , ρx ), for
every x ∈ X and h ∈ H. In other words, F ≀ H is a subgroup of the stabilizer of

11

U . Define an (F ≀ H)-representation (ExH U, ExH ρ) in the following way. As a
vector space, ExH U = U and the group action is:
ExH ρ(f, h)( ⊠ ux ) = ⊠ ρh−1 x (f (x))(uh−1 x ) = ⊠ ρx (f (x))(uh−1 x ).
x∈X

x∈X

x∈X

(ExH U, ExH ρ) is called the extension of U with respect to H. When no ambie , ρe) instead of (ExH U, ExH ρ).
guity arises we write (U
e , ρe) is indeed an (F ≀ H)-representation.
Lemma 3.5. (U

Proof. We remark that this proof is essentially [3, Lemma 2.4.3]. Given (f1 , h1 ),(f2 , h2 ) ∈
F ≀ H what we need to prove is:
(3.1)

ρe((f1 , h1 ) · (f2 , h2 ))( ⊠ ux ) = ρe((f1 , h1 ))(e
ρ((f2 , h2 ))( ⊠ ux )).
x∈X

x∈X

The left hand side of Equation (3.1) is:
ρe((f1 , h1 ) · (f2 , h2 ))( ⊠ ux ) = ρe((f1 (h1 ∗ f2 ), h1 h2 ))( ⊠ ux ) =
x∈X

x∈X

= ⊠ ρh−1 h−1 x ((f1 (h1 ∗ f2 ))(x))uh−1 h−1 x .
x∈X

2

1

2

1

Since ρhx = ρx for every h ∈ H this equals
⊠ ρx ((f1 (h1 ∗ f2 ))(x))uh−1 h−1 x = ⊠ ρx (f1 (x)f2 (h1−1 x))uh−1 h−1 x .

x∈X

2

x∈X

1

2

1

The right hand side of Equation (3.1) is

ρe((f1 , h1 ))(ρ̃((f2 , h2 ))( ⊠ ux )) = ρe((f1 , h1 ))( ⊠ ρh−1 x (f2 (x))(uh−1 x )).
x∈X

x∈X

2

2

Again, since ρh−1 x = ρx the last expression equals
2

ρe((f1 , h1 ))( ⊠ ρx (f2 (x))(uh−1 x )) = ⊠ ρh−1 x (f1 (x))(ρh−1 x (f2 (h−1
1 x))(uh−1 h−1 x ))
x∈X

2

x∈X

= ⊠

x∈X

1

1

2

ρx (f1 (x))(ρx (f2 (h1−1 x))(uh−1 h−1 x ))
2
1

= ⊠ ρx (f1 (x)f2 (h1−1 x))uh−1 h−1 x .
x∈X

So we get the desired equality.

12

2

1

1

Remark 3.6. Let H ≤ K ≤ G and let U = ⊠ Ux be an F X -representation
x∈X

such that F ≀ K is a subgroup of the stabilizer of U . Note that
≀K
ExH U = ResF
F ≀H ExK U.

Lemma 3.7. Let G1 and G2 be groups acting on disjoint sets X and Y respectively. Let U = ⊠ Ux and V = ⊠ Uy be F X and F Y -representations
x∈X

y∈Y

respectively. Assume that H1 ≤ G1 , H2 ≤ G2 are subgroups such that F ≀ H1
and F ≀ H2 are subgroups of the stabilizers of U and V respectively. Then
ExH1 U ⊠ ExH2 V ∼
= ExH1 ×H2 (U ⊠ V )
as F ≀X ∪Y
(H1 × H2 ) ∼
= (F ≀X H1 ) × (F ≀Y H2 )-representations.
˙
Proof. Both vector spaces are spanned by elements of the form ( ⊠ ux ) ⊠
x∈X

( ⊠ uy ) and in both cases the group action is
y∈Y

((f1 , h1 ), (f2 , h2 ))·(( ⊠ ux )⊠( ⊠ uy )) = ( ⊠ f1 (x)·uh−1 x )⊠( ⊠ f2 (y)·uh−1 y ).
x∈X

3.3

y∈Y

x∈X

1

y∈Y

2

Irreducible representations of F ≀ Sn

We now return to the specific case of F ≀ Sn . From now on, fix some indexing
for the set of irreducible representation of F , say Irr F = {U1 , . . . , Ul }. Without
loss of generality, we assume that U1 is the trivial representation of F . Let
1 ≤ ij ≤ l for j = 1, . . . , n and let
n

n

j=1

x=1

(U, ρ) = ( ⊠ Uij , ⊠ ρij )
be an irreducible F n -representation. We define its type to be the integer composition
type(U ) = (n1 , . . . , nl )
such that ni is the number of j ∈ {1, . . . , n} such that Uij ∼
= Ui . Clearly
l
X
ni = n and ni ≥ 0 for every 1 ≤ i ≤ l. It is clear that two irreducible
i=1

representations are in the same orbit of conjugation if and only if they have the

13

same type. Moreover, the stabilizer of U is isomorphic to F ≀ (Sn1 × · · · × Snl ).
Given a specific composition n = (n1 , . . . , nl ) define
Un = U1⊠n1 ⊠ · · · ⊠ Ul⊠nl
that is, the first n1 representations in the product are U1 , the next n2 representations are U2 etc. Clearly, the type of Un is n and the set {Un | n is
an integer composition of n} serve as a set of representatives for the orbits of
conjugation. A tuple Λ = (λ1 , . . . , λl ) such that λi ⊢ ni for every i is called a
multipartition of n with l components. We will also call it a multipartition of
the composition n and denote this by Λ n. We denote by S Λ the (irreducible)
Sn1 × · · · × Snl -representation S Λ = S λ1 ⊠ · · · ⊠ S λl . Finally we can define:
Definition 3.8. Let n = (n1 , . . . , nl ) be an integer composition of n and let
Λ = (λ1 , . . . , λl ) be a multipartition of n. Denote by ΦΛ = Φ(λ1 ,...,λl ) the F ≀ Sn
representation
fn ⊗ S Λ ).
(U
IndF ≀Sn
F ≀(Sn1 ×···×Snl )

Theorem 3.9. [3, Theorem 2.6.1] The set

{ΦΛ | n is some integer composition of n and Λ is a multipartition of n}
is a complete list of the irreducible representations of F ≀Sn . Moreover, ΦΛ ∼
= ΦΛ′
′
if and only if Λ = Λ .
We define a multi-Young diagram to be a tuple of Young diagrams. As we
identify partitions and Young diagrams, we also identify multipartitions and
multi-Young diagrams. Hence, multi-Young diagrams (with l components) index
the irreducible representations of F ≀ Sn . For instance, if Λ = ([2], [2, 1], [1, 1, 1])
then the irreducible representation ΦΛ of (say) S3 ≀ S8 corresponds to the multiYoung diagram
(

,

,

).

Remark 3.10. Note that trF , the trivial representation of F = F ≀S1 , corresponds
to the multi-Young diagram
( , ∅, . . . , ∅).

14

Let λ be some partition of n. We set Φiλ = Φ(∅,...,∅,λ,∅,...,∅) where the nonempty partition is in the i-th position. Note that
⊠n ⊗ S λ .
Φiλ = Ug
i

Remark 3.11. Since {U1 , . . . , Ul } are irreducible representations of F = F ≀ S1
then Ui can be also written as Φi([1]) .
A key observation is the following one.
Proposition 3.12. Let n = (n1 , . . . , nl ) be an integer composition of n and let
Λ = (λ1 , . . . , λl ) be a multipartition of n. The following isomorphism holds:
F ≀S
ΦΛ ∼
= IndF ≀Snn1 ×···×F ≀Sn (Φ1λ1 ⊠ · · · ⊠ Φlλl ).
l

Proof. By definition
≀Sn
ΦΛ = IndF
F ≀(Sn

1 ×···×Snl )

fn ⊗ S Λ )
(U

if we write this more explicitly we get
≀Sn
ΦΛ = IndF
F ≀Sn

1 ×···×F ≀Snl

^
(U1⊠n1 ⊠ · · · ⊠ Ul⊠nl ) ⊗ (S λ1 ⊠ · · · ⊠ S λl )

Using Lemma 3.2 and Lemma 3.7 this equals:
≀Sn
IndF
F ≀Sn

1 ×···×F ≀Snl

^
]
(U1⊠n1 ⊠ · · · ⊠ Ul⊠nl ) ⊗ (S λ1 ⊠ · · · ⊠ S λl ).

Now, using Lemma 2.3 this equals:
≀Sn
IndF
F ≀Sn

1 ×···×F ≀Snl

^
]
(U1⊠n1 ⊗ S λ1 ) ⊠ · · · ⊠ (Ul⊠nl ⊗ S λl )

≀Sn
IndF
F ≀Sn

(Φ1λ1 ⊠ · · · ⊠ Φlλl )

which is precisely
1 ×···×F ≀Snl

as required.

15

4

Littlewood-Richardson rule for F ≀ Sn

In this section we generalize the standard Littlewood-Richardson rule for Sn to
the case of F ≀ Sn . As mentioned above this is a new proof for [5, Theorem 4.7].
Given two integers k and r and two integer compositions
k = (k1 , . . . , kl ),

l
X

ki = k

l
X

ri = r

i=1

r = (r1 , . . . , rl ),

i=1

let Λ = (λ1 , . . . , λl ) and ∆ = (δ1 , . . . , δl ) be multipartitions of k and r respectively. We want to find the decomposition of
F ≀S

(ΦΛ ⊠ Φ∆ )
IndF ≀Sk+r
k ×F ≀Sr
into irreducible representations. In other words, if we write
F ≀S

(ΦΛ ⊠ Φ∆ ) =
IndF ≀Sk+r
k ×F ≀Sr

MM

Γ
CΛ,∆
ΦΓ

n Γ n

where the outer sum is over all integer compositions n of k + r, we want to find
Γ
the coefficients CΛ,∆
. We start with a specific case.

Proposition 4.1. Let λ ⊢ k and δ ⊢ r then
F ≀S

(Φiλ ⊠ Φiδ ) =
IndF ≀Sk+r
k ×F ≀Sr

M

cγλ,δ Φiγ

γ⊢(k+r)

where cγλ,δ is the Littlewood-Richardson coefficient.
Before proving this results we need some lemmas.
Lemma 4.2. Let H ≤ G be a subgroup of G. Let U be an H-representation
then
IndF ≀X G U ∼
= IndG U
H

F ≀X H

as (F ≀X G)-representations.
Proof. Let s1 , . . . , sl be representatives of the H cosets in G. Note that (1F , si )
for i = 1, . . . , l are representatives for the F ≀X H cosets in F ≀X G where 1F is
16

the constant function 1F (x) = 1F . Now, define
F ≀X G
T : IndG
H U → IndF ≀X H U

by
T ((si , u)) = ((1F , si ), u)
and extending linearly. Clearly, T is a vector space isomorphism. Now, given
(f, g) ∈ F ≀X G
T ((f, g) · (si , u)) = T (g(si , u))
= T ((sj , hu))
= ((1F , sj ), hu)
assuming that gsi = sj h for h ∈ H. Note that
(f, g)(1F , si ) = (f (g ∗ 1F ), gsi ) = (f 1F , gsi ) =
= (f, sj h) = (1F , sj )(s−1
j ∗ f, h)
hence
(f, g) · T ((si , u)) = (f, g) · ((1F , si ), u)
= ((1F , sj ), (s−1
j ∗ f, h) · u)
= ((1F , sj ), hu)
so
T ((f, g) · (si , u)) = (f, g) · T ((si , u))
as required.
Lemma 4.3 ([3, Proposition 1.1.15]). Assume H ≤ G and let U (V ) be a G
(respectively H)-representation. Then
G
G
∼
IndG
H (ResH (U ) ⊗ V ) = U ⊗ IndH V.

Lemma 4.4. Let V be an (F ≀X G)-representation. Let H ≤ G and let W be
some H-representation.

17

Then
F ≀X G
F ≀X G
G
∼
IndF
≀X H (ResF ≀X H (V ) ⊗ W ) = V ⊗ IndH W .

Proof. Apply Lemma 4.3 and Lemma 4.2.
Proof of Proposition 4.1. According to the definition
F ≀S
F ≀S
g
⊠k ⊗ S λ ) ⊠ (U
⊠r ⊗ S δ )).
((Ug
(Φiλ ⊠ Φiδ ) = IndF ≀Sk+r
IndF ≀Sk+r
i
i
k ×F ≀Sr
k ×F ≀Sr

Using Lemma 2.3 this equals
F ≀S
g
⊠r
⊠k ⊠ U
λ
δ
((Ug
IndF ≀Sk+r
i ) ⊗ (S ⊠ S ))
i
k ×F ≀Sr

and by Lemma 3.2 and Lemma 3.7 this equals
^
F ≀S
⊠(k+r)
) ⊗ (S λ ⊠ S δ )).
((Ui
IndF ≀Sk+r
k ×F ≀Sr
If we use more precise notation, this is actually
⊠(k+r)

F ≀S

((ExSk ×Sr Ui
IndF ≀Sk+r
k ×F ≀Sr

) ⊗ (S λ ⊠ S δ ))

but according to Remark 3.6 this equals
⊠(k+r)

F ≀S

F ≀S

((ResF ≀(Sk+r
ExSk+r Ui
IndF ≀Sk+r
k ×F ≀Sr
k ×Sr )

) ⊗ (S λ ⊠ S δ )).

Returning to imprecise notation, this is
^
F ≀S
F ≀S
⊠(k+r)
)) ⊗ (S λ ⊠ S δ ))
(Ui
((ResF ≀Sk+r
IndF ≀Sk+r
k ×F ≀Sr
k ×F ≀Sr
where now

^
⊠(k+r)
Ui

is an (F ≀ Sk+r )-representation.
By Lemma 4.4 this equals
^
S
⊠(k+r)
(S λ ⊠ S δ )
⊗ IndSk+r
Ui
k ×Sr

18

but according to the standard Littlewood-Richardson rule
S

(S λ ⊠ S δ ) =
IndSk+r
k ×Sr

X

cγλ,δ S γ .

γ⊢(k+r)

Hence our representation equals
^
⊠(k+r)
⊗
Ui

X

cγλ,δ S γ =

γ⊢(k+r)

X

^
⊠(k+r)
⊗ Sγ ) =
cγλ,δ (Ui

γ⊢(k+r)

X

cγλ,δ Φiγ

γ⊢(k+r)

as required.
Now we turn to the general case. Let k = (k1 , . . . , kl ) and r = (r1 , . . . , rl )
be integers compositions of k and r respectively. We denote k + r = (k1 +
r1 , . . . , kl + rl ), an integer composition of k + r.
Theorem 4.5. Let Λ = (λ1 , . . . , λl )

k and ∆ = (δ1 , . . . , δl )

F ≀S

(ΦΛ ⊠ Φ∆ ) =
IndF ≀Sk+r
k ×F ≀Sr

M

r then

Γ
CΛ,∆
ΦΓ

Γ (k+r)

where
Γ
CΛ,∆
=

l
Y

cγλii ,δi .

i=1

Remark 4.6. Note that k + r is the only composition of k + r occurring in this
summation.
Before proving this result we need another technical lemma about induction.
Lemma 4.7. Assume H1 ≤ G1 (H2 ≤ G2 ) and let U1 (respectively, U2 ) be a
representation of H1 (respectively, H2 ). Then
G
G
G1 ×G2
IndH
(U1 ⊠ U2 ) ∼
= IndH11 U1 ⊠ IndH22 U2 .
1 ×H2

Proof. It is more convenient here to use the tensor product definition of induced
G1 ×G2
representation. Define a vector space isomorphism T : IndH
(U1 ⊠ U2 ) →
1 ×H2
G2
1
IndG
H1 U1 ⊠ IndH2 U2 by

T ((s1 , s2 ) ⊗ (u1 ⊠ u2 )) = (s1 ⊗ u1 ) ⊠ (s2 ⊗ u2 )

19

and extending linearly. Now take some (g1 , g2 ) ∈ G1 × G2 and note that
T ((g1 , g2 ) · ((s1 , s2 ) ⊗ (u1 ⊠ u2 ))) = T ((g1 s1 , g2 s2 ) ⊗ (u1 ⊠ u2 ))
= (g1 s1 ⊗ u1 ) ⊠ (g2 s2 ⊗ u2 )
= (g1 · (s1 ⊗ u1 )) ⊠ (g2 · (s2 ⊗ u2 ))
= (g1 , g2 ) · T ((s1 , s2 ) ⊗ (u1 ⊠ u2 )).
as required.
Proof of Theorem 4.5. According to Proposition 3.12, the representation
F ≀S

(ΦΛ ⊠ Φ∆ )
IndF ≀Sk+r
k ×F ≀Sr
equals

F ≀S

≀Sk
(IndF
IndF ≀Sk+r
F ≀Sk
k ×F ≀Sr

1

F ≀Sr
l
1
l
1
×···×F ≀Skl (Φλ1 ⊠· · ·⊠Φλl )⊠IndF ≀Sr1 ×···×F ≀Srl (Φδ1 ⊠· · ·⊠Φδl )).

Using Lemma 4.7 this equals
F ≀S

≀Sk ×F ≀Sr
(IndF
IndF ≀Sk+r
F ≀Sk ×···×F ≀Sk
k ×F ≀Sr
1

l

l
l
1
1
×F ≀Sr1 ×···×F ≀Srl (Φλ1 ⊠· · ·⊠Φλl ⊠Φδ1 ⊠· · ·⊠Φδl ))

which, by transitivity of induction, equals
F ≀S

IndF ≀Sk+r
k ×···×F ≀Sk
1

l

1
×F ≀Sr1 ×···×F ≀Srl (Φλ1

⊠ · · · ⊠ Φlλl ⊠ Φ1δ1 ⊠ · · · ⊠ Φlδl ).

Rearranging we get
F ≀S

IndF ≀Sk+r
k ×F ≀Sr
1

1 ×···×F ≀Skl ×F ≀Srl

((Φ1λ1 ⊠ Φ1δ1 ) ⊠ · · · ⊠ (Φlλl ⊠ Φlδl )).

Again using transitivity we can write this as
F ≀Sk

F ≀S

IndF ≀Sk+r
k +r
1

1

×···×F ≀Skl +rl

+r

×···×F ≀Skl +rl
((Φ1λ1 ⊠Φ1δ1 )⊠· · ·⊠(Φlλl ⊠Φlδl ))
1 ×···×F ≀Skl ×F ≀Srl

IndF ≀Sk1 ×F1 ≀Sr
1

and using Lemma 4.7 this equals
F ≀S

IndF ≀Sk+r
k +r
1

1

F ≀Skl+rl
F ≀Sk1 +r1
1
l
l
1
×···×F ≀Skl +rl (IndF ≀Sk1 ×F ≀Sr1 (Φλ1 ⊠Φδ1 )⊠· · ·⊠IndF ≀Skl ×F ≀Srl (Φλl ⊠Φδl )).

20

According to Proposition 4.1 we get
F ≀S

IndF ≀Sk+r
k +r
1

1

M

cγλ11 ,δ1 Φ1γ1 )
×···×F ≀Skl +rl ((
γ1 ⊢(k1 +r1 )

⊠ ··· ⊠ (

M

cγλll ,δl Φlγl ))

γl ⊢(kl +rl )

which equals
M

γ1 ⊢(k1 +r1 )

···

M

(

l
Y

F ≀S

cγλii ,δi IndF ≀Sk+r
k +r
1

γl ⊢(kl +rl ) i=1

1

1
×···×F ≀Skl +rl (Φγ1

⊠ · · · ⊠ Φ1γl ))

which, according to Proposition 3.12, is precisely
l
M Y
( cγλii ,δi )ΦΓ

Γ k+r i=1

as required.

5

Classical branching rules for F ≀ Sn

In this section we retrieve Pushkarev’s result of “classical” branching rules for
F ≀ Sn [10, Theorem 10]. Let n = (n1 , . . . , nr ) be an integer composition of
n and let Λ = (λ1 , . . . , λl )
n be a multipartition. We want to find the deF ≀S

≀Sn
composition into irreducible representations of IndF ≀Snn+1 ΦΛ and ResF
F ≀Sn−1 ΦΛ .
This is relatively easy using the results of the previous section. We start with

induction.
Theorem 5.1. With notation as above
F ≀S

IndF ≀Snn+1 ΦΛ =

l
M
(dim Ui
i=1

M

Φ(λ1 ,...,γ,...,λl ) )

γ∈Y + (λi )

where γ is in the i-th position of (λ1 , . . . , γ, . . . , λl ).
For the proof of Theorem 5.1 we need the following lemma.
Lemma 5.2. Let U be an H-representation and let K be some group, then
IndK×H
U∼
= CK ⊠ U.
H
Proof. Clearly {(k, 1) | k ∈ K} are representatives of the H ∼
= {1K } × H cosets
21

in K × H. Define T : IndK×H
U → CK ⊠ U by
H
T (((k, 1), u)) = k ⊠ u
which is clearly a vector space isomorphism and note that
T ((k ′ , h′ ) · ((k, 1), u)) = T (((k ′ k, 1), h′ u))
= k ′ k ⊠ h′ u
= (k ′ , h′ ) · (k ⊠ u)
= (k ′ , h′ ) · T (((k, 1), u))
so T is an isomorphism of (K × H)-representations.
Proof of Theorem 5.1. Noting that F ≀n+1 Sn = F ≀ Sn × F = F ≀ Sn × F ≀ S1
and by transitivity of induction
F ≀S

F ≀S

F ≀Sn ×F
ΦΛ .
IndF ≀Snn+1 ΦΛ = IndF ≀Snn+1
×F ≀S1 IndF ≀Sn

According to Lemma 5.2 this equals
F ≀S

IndF ≀Snn+1
×F ≀S1 ΦΛ ⊠ CF.
It is well-known that the decomposition of CF is
CF =

l
M

(dim Ui · Ui )

i=1

so we obtain
l
l
M
M
F ≀S
F ≀S
(dim Ui IndF ≀Snn+1
dim
U
·
U
))
=
(Φ
⊠
(
IndF ≀Snn+1
i
i
Λ
×F ≀S1 (ΦΛ ⊠ Ui )).
×F ≀S1
i=1

i=1

But Ui = Φi([1]) (see Remark 3.11) so we can write this as
l
M
F ≀S
i
(dim Ui IndF ≀Snn+1
×F ≀S1 (ΦΛ ⊠ Φ([1]) )).
i=1

Using Theorem 4.5 and Remark 2.10 this is precisely the required result.

22

Using Frobenius reciprocity we have the following corollary for restriction.
Corollary 5.3. With notation as above
≀Sn
ResF
F ≀Sn−1 ΦΛ =

l
M
(dim Ui
i=1

M

Φ(λ1 ,...,γ,...,λl ) )

γ∈Y − (λi )

where γ is in the i-th position of (λ1 , . . . , γ, . . . , λl ).
Example 5.4. Let Λ be the multipartition associated to the multi-Young diagram
(

,

,

)

so ΦΛ is an irreducible representation of S3 ≀S8 . Assuming we have indexed Irr S3
such that U1 is the trivial representation, U2 is the standard representation and
U3 is the alternating representation then
≀S9
ΦΛ
IndSS33 ≀S
8

is associated to
(

,

2(

,

,

)⊕(

,

,

) ⊕ 2(

(

6

,

,

,

,

,

) ⊕ 2(

,

)⊕(

,

,

,

)⊕

)⊕

).

Application: The quiver of the category algebra C(F ≀ FIn )

Denote by FIn the category of all injective functions between subsets of {1, . . . , n}.
In this section we apply the Littlewood-Richardson rule for computing the ordinary quiver of the category algebra of F ≀ FIn , the wreath product of a finite
group F with FIn . In the next two sections we give some preliminary background on the wreath product of a group with a category and on quivers. In
section 6.3 we give the description of the quiver.
23

6.1

The wreath product of a group with a category

All categories in this paper are finite. Hence we can regard a category C as a
set of objects, denoted C 0 , and a set of morphisms, denoted C 1 . If a, b ∈ C 0 then
C(a, b) is the set of morphisms from a to b. Let g ∈ C(a, b) and g ′ ∈ C(c, d) be
two morphisms. Recall that the composition g ′ · g is defined if and only if b = c
and we denote this fact by by ∃g ′ · g. A category D is called a subcategory of C if
it obtained from C by removing objects and morphisms. D is a full subcategory
if D(a, b) = C(a, b) for every a, b ∈ D0 . Let F be a finite group, let C be a finite
category and let H : C → Set be a functor from C to the category of finite sets.
Define a new category D in the following way. The set of objects is the same
as the set of objects of C, that is, D0 = C 0 . Given two objects a, b ∈ D0 , the
hom-set D(a, b) is {(f, g) | f ∈ F H(a) , g ∈ C(a, b)} where F H(a) is the set of all
functions f : H(a) → F . So we can write a specific morphism as (f, g). Now,
given two morphisms (f, g) ∈ D(a, b) and (f ′ , g ′ ) ∈ D(b, c) the composition is
(f ′ , g ′ ) · (f, g) = ((f ′ (H(g))) · f, g ′ g)
where · is componentwise multiplication of functions in F H(a) .
Definition 6.1. The category D defined above is called the wreath product of
F and C with respect to H and it is denoted by F ≀H C.
Since monoids are categories with one object, Definition 6.1 is also a definition
for the wreath product of a group G with a monoid M . In this case the functor
F is just an action of M on the left of some set X. Hence M acts on the right
of F X in the following way. Given g ∈ M and f ∈ F X the function f ∗ g is
defined by
(f ∗ g)(x) = f (g · x).
The wreath product F ≀X M is then just the right semidirect product F X ⋊ M .
Remark 6.2. One may note that if M is a group then Definition 6.1 does not
coincide with Definition 2.1. However, we will immediately prove that the two
ways to define a wreath product of groups are isomorphic. We have to use
different definition for wreath product in this section because Definition 2.1
does not generalize well to monoids and categories.
In the next lemma we denote by F wrX G the wreath product of Definition 6.1
which is apriory different from F ≀X G of Definition 2.1.
24

Lemma 6.3. Let F and G be finite groups such that G acts on the left X. Then
F wrX G ∼
= F ≀X G.
Proof. In this proof we denote by ∗1 (∗2 ) the left (right) action of G on F X as
in Definition 2.1 (respectively, Definition 6.1). Define T : F ≀X G → F wrX G by
T (f, g) = (f ∗2 g, g).
Clearly, T has an inverse
T −1 (f, g) = (f ∗2 g −1 , g).
Moreover, note that
T ((f, g) · (f ′ , g ′ )) = T (f · (g ∗1 f ′ ), gg ′ ) = T (f · (f ′ ∗2 g −1 ), gg ′ )
= ((f ∗2 (gg ′ )) · (f ′ ∗2 g ′ ), gg ′ )
while
T ((f, g)) · T ((f ′ , g ′ )) = (f ∗2 g, g) · (f ′ ∗2 g ′ , g ′ ) = ((f ∗2 (gg ′ )) · (f ′ ∗2 g ′ ), gg ′ )
so T is also a group homomorphism as required.

6.2

The ordinary quiver of an EI-category algebra

Recall that a unital C-algebra is a unital ring A that is also a vector space over
C such that c(ab) = (ca)b = a(cb) for all c ∈ C and a, b ∈ A. The algebras
that are of interest for us in this section are category algebras. Let D be a
finite category. The category algebra CD is the C-vector space with basis the
morphisms of the category, that is, all formal linear combinations
{c1 g1 + . . . + ck gk | ci ∈ C, gi ∈ D1 }
with multiplication being linear extension of
g′ · g =


g ′ g
0

25

∃g ′ · g
otherwise

.

A quiver is a non-directed graph where multiple edges and loops are permitted.
The (ordinary) quiver Q of an algebra A is a quiver that contains information
about the algebra’s representations. The exact definition is as follows. The vertices of Q are in a one-to-one correspondence with the set Irr A of all irreducible
representations of A (up to isomorphism). Given two irreducible representations
U and V the number of edges (more often called arrows) from U to V is
dim Ext1 (U, V ).
For the sake of simplicity, if Q is the quiver of the algebra of D we will call it
simply the quiver of D.
When considering quivers of categories we can restrict our discussion to a special
kind of categories. Two categories C and D are called equivalent if there are
functors F : C → D and G : D → C such that F G ∼
= 1D and GF ∼
= 1C where ∼
= is
natural isomorphism of functors. It is well known that C and D are equivalent
if and only if there is a fully faithful and essentially surjective functor from C to
D. If C and D are equivalent categories then they have the same quiver (since
their algebras are Morita equivalent, see [14, Proposition 2.2]). A category C is
called skeletal if no two objects of C are isomorphic. Note that any category C
is equivalent to some (unique) skeletal category called its skeleton. The skeleton
of C is the full subcategory having one object from every isomorphism class of
C. So we can restrict ourselves to discussing skeletal categories.
There is a special kind of categories whose quiver has a more concrete description. This description was discovered independently by Li [7] and by Margolis
and Steinberg [9]. For explaining it we need more definitions from category
theory. A category D is called an EI-category if every endomorphism is an isomorphism. In other words, every endomorphism monoid D(a, a) of this category
is a group. A morphism g ∈ D1 of an EI-category is called irreducible if it is not
an isomorphism but whenever g = g ′ g ′′ , either g ′ or g ′′ is an isomorphism. The
set of irreducible morphisms from a to b is denoted IRR A(a, b). The quiver of
skeletal EI-categories is described in the following theorem, which is [7, Theorem 4.7] or [9, Theorem 6.13] for the case of the field of complex numbers.
Theorem 6.4. Let D be a finite skeletal EI-category and denote by Q the
quiver of D. Let C IRR D(a, b) denote the C-vector space spanned by the set

26

IRR D(a, b). It is also an D(b, b) × D(a, a)-representation according to
(h′ , h) · g = h′ gh−1
for (h′ , h) ∈ D(b, b) × D(a, a) and g ∈ IRR D(a, b). Then
1. The vertex set of Q is

G

Irr D(a, a).

a∈D 0

2. If V ∈ Irr(D(a, a)) and U ∈ Irr(D(b, b)), then the number of arrows from
V to U is the multiplicity of U ⊠ V ∗ as an irreducible constituent of the
D(b, b) × D(a, a)-representation C IRR D(a, b).

6.3

The quiver of the category F ≀ FIn

As mentioned above, we denote by FIn the category of all injective functions
between subsets of {1, . . . , n}. In other words, the objects of FIn are subsets
of {1, . . . , n} and given two objects A and B the hom-set FIn (A, B) contains
all the injective functions from A to B. Note that ∅ is an initial object of this
category, that is, for every A ⊆ {1, . . . , n} there is a unique empty function from
∅ to A. We are interested in the category F ≀H FIn where H : FIn → Set is the
inclusion functor. We will omit the H and denote this category by F ≀ FIn . This
category has a natural description using matrices similar to the description of
F ≀ Sn . We can identify the hom-set F ≀ FIn (A, B) with a set of matrices whose
rows are indexed by elements of B and columns are indexed by elements of A.
The matrix M (f,g) identified with (f, g) ∈ F ≀ FIn (A, B) is defined by
(f,g)

Mi,j


f (j) g(j) = i
=
0
otherwise

where i ∈ B and j ∈ A. g is a total function so M (f,g) has no zero columns.
Moreover, since g is an injective function M (f,g) is column and row monomial,
that is, every row and column contains at most one non-zero element. Hence
F ≀ FIn (A, B) can be identified with the set of all column and row monomial
matrices over F without zero columns where the columns are indexed by A
and the rows are indexed by B. Composition of morphisms then corresponds
′ ′
to matrix multiplication. Note that the multiplication M (f ,g ) · M (f,g) of two
matrices of this form where (f, g) ∈ F ≀ FIn (A, B) and (f ′ , g ′ ) ∈ F ≀ FIn (C, D)

27

is defined if and only if B = C. In other words, multiplication is defined if
′

′

and only if the columns of M (f ,g ) and the rows of M (f,g) are indexed by the
same set. It is easy to see that any endomorphism monoid F ≀ FIn (A, A) of
this category is isomorphic to the group F ≀ SA hence this category is actually
an EI-category. Our goal is to describe the quiver of F ≀ FIn . The case where
F is the trivial group was originaly done in [2, Theorem 8.1.2]. A different
computation of this case using Theorem 6.4 is done in [9, Example 6.15] and
here we merely imitate their method. As explained in the previous section
we can work with the skeleton of F ≀ FIn . For the sake of simplicity we will
denote this skeleton by SF n . It is clear that two objects A and B of F ≀ FIn are
isomorphic if and only if |A| = |B|. Hence we can identify the skeleton SF n with
the full subcategory of F ≀FIn whose objects are the empty set and {1, . . . , k} for
k = 1, . . . , n. So we can identify the objects of SF n with 0, . . . , n. Now the homset SF n (k, r) is identified with all the r × k matrices over F which are column
and row monomial and without zero columns. Composition of morphisms then
corresponds to matrix multiplication as explained above. By Theorem 6.4 we
know that the vertices of the quiver of SF n are in one-to-one correspondence
with irreducible representation of the endomorphism groups, which are F ≀ Sk
for 0 ≤ k ≤ n. In other words:
Corollary 6.5. Let F be a group with l distinct irreducible representations.
The vertices in the quiver of F ≀ FIn can be identified with all the multi-Young
diagrams with k boxes and l components where 0 ≤ k ≤ n.
The next step is to identify the irreducible morphisms of SF n .
Lemma 6.6. The irreducible morphisms of SF n are precisely the morphisms
from k to k + 1 for 0 ≤ k ≤ n − 1. In other words,

SF (k, r)
n
IRR SF n (k, r) =
0

r =k+1

.

otherwise

Proof. It is clear that any morphism in SF n (k, k+1) is irreducible. On the other
hand, take some morphism (f, g) ∈ SF n (k, r) and assume that k+1 < r. Choose
j ∈ {1, . . . , r} not in the image of g. Define inc : {1, . . . , k} → {1, . . . , k + 1}
to be the inclusion function and g ′ : {1, . . . , k + 1} → {1, . . . , r} is the function

28

defined by


g(i) i ≤ k
g ′ (i) =
.
j
i=k+1

It is clear that g ′ and inc are not bijections and that g = g ′ ◦ inc. Denote by
1F the constant function 1F : {1, . . . , k + 1} → F defined by 1F (i) = 1F for
i = 1, . . . , k + 1. Since g ′ and inc are not bijections it is clear that (1F , g ′ ) and
(f, inc) are not isomorphisms. Moreover,(1F , g ′ ) · (f, inc) = (f, g) so (f, g) is not
an irreducible morphism as required.
From Theorem 6.4 and Lemma 6.6 we can immediately deduce the following
corollary.
Corollary 6.7. Let V ∈ Irr F ≀ Sk and U ∈ Irr F ≀ Sr be two vertices in the quiver
of F ≀ FIn such that r 6= k + 1 then there are not arrows from V to U .
It is left to consider the situation where r = k + 1. We have to study the representation C IRR(SF n (k, k + 1)) = C SF n (k, k + 1) under the action described
in Theorem 6.4. This is a permutation representation, i.e., it is a linearization
of the action of F ≀ Sk × F ≀ Sk+1 on the set SF n (k, k + 1) given by
((h′ , π ′ ), (h, π)) · (f, g) = (h′ , π ′ ) · (f, g) · (h, π)−1 .
Lemma 6.8. The above action is transitive.
Proof. Chose some (f, g) ∈ SF n (k, k + 1) and let j ∈ {1, . . . , k + 1} be the only
element not in the image of g. Define π ′ ∈ Sk+1 by

g −1 (i) i 6= j
π ′ (i) =
.
k + 1 i = j
Recall that g is injective so g −1 (i) is well defined if i ∈ im g. It is clear that
π ′ g = inc : {1, . . . , k} → {1, . . . , k + 1}. Now define h′ : {1, . . . , k + 1} → F by
h′ (i) =


(f (g −1 (i)))−1
1

i 6= j

.

i=j

It is easy to see that (h′ , π ′ ) · (f, g) = (1F , inc) hence the action is transitive
(even if we multiply only on the left).
29

It is well-known that if the action of G on some set X is transitive then the
permutation representation CX is IndG
K (trK ) where K = stab(x) is the stabilizer
of some x ∈ X and trK is its trivial representation.
So our representation is also of this form. We want to understand better the
stabilizer of some x ∈ SF n (k, k + 1). It is convenient to choose x = (1F , inc)
and to use the matrix interpretation discussed above.
Lemma 6.9. Choose x = (1F , inc) ∈ SF n (k, k + 1). The stabilizer stab(x) is
isomorphic to (F ≀ Sk ) × F .
Proof. (1F , inc) is identified with the (n + 1) × n matrix with 1 along its main
diagonal and 0 elsewhere.


1


 0
(1F , inc) = 

 0

0
..
.

0

0

0
1

0 ···

0





 
 
=
 
 



I
0

···

0



.



It is easy to see that given any matrix A ∈ F ≀ Sk if we want some B ∈ F ≀ Sk+1
such that





B





I
0

···

0







A = 







I
0 ···

0







then B must be of the form




B=



0
..
.
0

A−1
0

···

0

a





 = A−1 ⊕ (a)



where a can be any element of F . Hence
stab((1F , inc)) = {(A ⊕ (a), A) | A ∈ F ≀ Sk ,

a ∈ F} ∼
= (F ≀ Sk ) × F

as required.
Proposition 6.10. Let V ∈ Irr F ≀ Sk and U ∈ Irr F ≀ Sk+1 identified with two
vertices of the quiver. The number of arrows from V to U is the multiplicity of U
30

F ≀S

as an irreducible constituent in the F ≀Sk+1 -representation Ind(F ≀Sk+1
(V ⊠trF ).
k )×F
Proof. Denote K = stab((1F , inc)). According to Theorem 6.4 and the above
discussion, the required number is the multiplicity of U ⊠ V ∗ as an irreducible
F ≀S

×F ≀S

k
constituent in the F ≀ Sk+1 × F ≀ Sk -representation IndK k+1
trK where
trK is the trivial representation of K. Using inner product of characters, and

recalling that we use the same notation for the representation and its character,
this number is
F ≀Sk+1 ×F ≀Sk

hU ⊠ V ∗ , IndK

trK i.

By Frobenius reciprocity this equals
F ≀Sk+1 ×F ≀Sk

hU ⊠ V ∗ , IndK

F ≀Sk+1 ×F ≀Sk

trK i = hResK

Recall that K = {(A ⊕ (a), A) | A ∈ F ≀ Sk ,

F ≀Sk+1 ×F ≀Sk

hResK

1
|K|

(U ⊠ V ∗ ), trK i. =

1
=
|K|
1
=
|K|

(U ⊠ V ∗ ), trK i.

a ∈ F } so

X

U ⊠ V ∗ (A ⊕ (a), A)

X

U (A ⊕ (a))V ∗ (A)

X

U (A ⊕ (a))V (A)

(A⊕(a),A)∈K

(A⊕(a),A)∈K

(A⊕(a),A)∈K

We want to think of the last term as an inner product of (F ≀Sk )×F -representations,
but neither U nor V is an (F ≀ Sk ) × F -representations. However,
F ≀S

U (A ⊕ (a)) = ResF ≀Skk+1
×F U (A ⊕ (a))
and
V (A) = V (A) trF (a) = (V ⊠ trF )(A, a)
as a K ∼
= (F ≀ Sk ) × F representation. Hence
1
|K|

X

U (A ⊕ (a))V (A)

(A⊕(a),A)∈K

equals

31

1
|(F ≀ Sk ) × F |

X

F ≀S

(Res(F ≀Sk+1
U )(A ⊕ (a))(V ⊠ trF )(A, a)
k )×F

(A,a)∈F ≀Sk ×F

which is the inner product
F ≀S

hRes(F ≀Sk+1
U, V ⊠ trF i.
k )×F
Using again Frobenius reciprocity this equals
F ≀Sk+1

hU, IndK

(V ⊠ trF )i

which is precisely the required number.
Clearly K ∼
= (F ≀ Sk ) × F = (F ≀ Sk ) × (F ≀ S1 ). Note also that the embedding
K ֒→ F ≀Sk+1 is precisely the standard embedding of the Littlewood-Richardson
rule. By Theorem 4.5 we can conclude:
Theorem 6.11. The vertices of the quiver of F ≀ FIn are in one-to-one correspondence with multi-Young diagrams with with k boxes and l components where
l = | Irr F | and 0 ≤ k ≤ n. Let k = (k1 , . . . kl ) and r = (r1 , . . . , rl ) be two integer compositions of k and r respectively and let Λ = (λ1 , . . . , λl )
k and
∆ = (δ 1 , . . . , δl )
r be multipartitions of k and r respectively. There can be
no more than one arrow from ΦΛ to Φ∆ . There is an arrow if and only if the
following holds:
• r = k + 1.
• r1 = k1 + 1 and ri = ki for 2 ≤ i ≤ l.
• λ1 is obtained from δ1 by adding one box, and λi = δi for 2 ≤ i ≤ l.
Proof. We have already seen that there are no arrows from ΦΛ to Φ∆ unless
r = k + 1 (Corollary 6.7). If r = k + 1 then Proposition 6.10 implies that the
number of arrows from ΦΛ to Φ∆ is the multiplicity of Φ∆ as an irreducible
F ≀S

F ≀S

k+1
constituent in IndF ≀Skk+1
×F (ΦΛ ⊠ trF ) = IndF ≀Sk ×F ≀S1 (ΦΛ ⊠ trF ). Recall that by
Remark 3.10 the multi-Young diagram corresponds to trF is

( , ∅, . . . , ∅)

32

so the result follows immediately from the Littlewood-Richardson rule for F ≀Sn .

Example 6.12. The quiver of the category S3 ≀ FI2 is given in the following
figure:
(

(∅,

, ∅)

, ∅, ∅)

( , ∅, ∅)

( , ∅, ∅)

( ,

, ∅) ( , ∅,

)

(∅, ∅, ∅)

(∅,

, ∅)

)

(∅,

, ∅)

(∅,

,

(∅, ∅,

) (∅, ∅,

)

(∅, ∅,

)

Clearly, two multipartitions Λ = (λ1 , . . . , λl ) and ∆ = (δ 1 , . . . , δl ) are in the
same connected component if and only if λi = δi for i = 2, . . . , l. Hence connected components can be parametrized by multipartitions of k with l − 1 components where k = 0, . . . , n. Denote by Pl (n) the number of multipartitions of n
with l components. A generating function for this sequence and other formulas
can be found in [1]. The following result is immediate.
Corollary 6.13. Let F be a non-trivial finite group and denote l = | Irr F |.
Then the quiver of F ≀ FIn has
n
X

Pl−1 (k)

k=0

connected components.
Acknowledgements: The author is grateful to Tullio Ceccherini-Silberstein
for examining this work and for his very helpful remarks.

References
[1] George E. Andrews. A survey of multipartitions: congruences and identities. In Surveys in number theory, volume 17 of Dev. Math., pages 1–19.
Springer, New York, 2008.

33

[2] Bridget Helen Brimacombe. The Representation Theory of the Incidence
Algebra of an Inverse Semigroup. ProQuest LLC, Ann Arbor, MI, 2011.
Thesis (Ph.D.)–Carleton University (Canada).
[3] Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli. Representation theory and harmonic analysis of wreath products of finite groups,
volume 410 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2014.
[4] Thomas Church, Jordan S. Ellenberg, and Benson Farb. FI-modules
and stability for representations of symmetric groups. Duke Math. J.,
164(9):1833–1910, 2015.
[5] Frank Ingram, Naihuan Jing, and Ernie Stitzinger. Wreath product symmetric functions. Int. J. Algebra, 3(1-4):1–19, 2009.
[6] Gordon James and Adalbert Kerber. The representation theory of the symmetric group, volume 16 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Co., Reading, Mass., 1981. With a
foreword by P. M. Cohn, With an introduction by Gilbert de B. Robinson.
[7] Liping Li. A characterization of finite EI categories with hereditary category
algebras. J. Algebra, 345:213–241, 2011.
[8] Liping Li. Upper bounds of homological invariants of FI_G-modules. arXiv
preprint arXiv:1512.05879, 2015.
[9] Stuart Margolis and Benjamin Steinberg. Quivers of monoids with basic
algebras. Compos. Math., 148(5):1516–1560, 2012.
[10] I. A. Pushkarev. On the theory of representations of the wreath products
of finite groups and symmetric groups. Zap. Nauchn. Sem. S.-Peterburg.
Otdel. Mat. Inst. Steklov. (POMI), 240(Teor. Predst. Din. Sist. Komb. i
Algoritm. Metody. 2):229–244, 294–295, 1997.
[11] Eric Ramos. Homological invariants of FI-modules and FI_G-modules.
arXiv preprint arXiv:1511.03964, 2015.
[12] Bruce E. Sagan. The symmetric group, volume 203 of Graduate Texts in
Mathematics. Springer-Verlag, New York, second edition, 2001. Representations, combinatorial algorithms, and symmetric functions.

34

[13] Steven V Sam and Andrew Snowden. Representations of categories of Gmaps. arXiv preprint arXiv:1410.6054, 2014.
[14] Peter Webb. An introduction to the representations and cohomology of
categories. In Group representation theory, pages 149–173. EPFL Press,
Lausanne, 2007.

35

