ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

arXiv:1707.00366v1 [math.RT] 2 Jul 2017

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN
Abstract. Let p be a prime number. In this article we study the restriction to Sn−1 of
irreducible characters of degree coprime to p of Sn . In particular, we study the combinatorial
properties of the subgraph Yp′ of the Young graph Y. This is an extension to odd primes of the
work done in [1] for p = 2.

1. Introduction
Let P denote the set of partitions of natural numbers. For λ a partition of n and µ ∈ P we
let (λ, µ) ∈ E if and only if χµ is an irreducible constituent of (χλ )Sn−1 . Here we denoted by
χλ the ordinary irreducible character of the symmetric group Sn naturally labelled by λ (this
notation will be kept throughout the article). The Young graph Y has P as its set of vertices
and E as its set of edges.
In the representation theory of symmetric groups, the study of the Young graph has proved
a fruitful tool in the modern development of the subject. For example, the recent approach to
this area first presented in [9] (see also [7, Chapter 2]) derives the entire representation theory of
symmetric groups from the combinatorial properties of Y. It is somewhat surprising that only
very recently in [1], the following remarkable fact was shown to hold.
Theorem 1 (Unique Parent Theorem in [1]). Let n ∈ N and let χ be an irreducible character of
odd degree of Sn . Then the restriction χSn−1 has a unique irreducible constituent of odd degree.
Let p be a prime number and let Yp′ be the induced subgraph of Y on those vertices (partitions)
labelling irreducible characters of degree coprime to p. Theorem 1 shows that Y2′ is a rooted
tree. Starting from this beautiful observation, the rest of [1] is devoted to describing the highly
regular combinatorial structure of Y2′ . We remark that the relevance of [1] transcends the study
of the Young graph. In fact, Theorem 1 was recently used to construct several types of character
correspondences (see [2], [3] and [4]).
The main aim of this paper is to study the combinatorial structure of Yp′ for any odd prime
p. As remarked in [1, Section 7], Theorem 1 is false for odd primes and Yp′ is never a tree for
p ≥ 3. Yet notably, given any prime p and any irreducible character χ of degree coprime to p of
Sn , Theorem A (below) describes the number of irreducible constituents of degree coprime to p
of χSn−1 . In particular, this extends Theorem 1 to all primes.
For λ ∈ P(n) we denote by λ−
p′ the subset of P(n − 1) consisting of all partitions µ such that
µ
χ is an irreducible constituent of degree coprime to p of (χλ )Sn−1 . Moreover we define En to
be the set
o
n
λ
En = |λ−
p′ | : λ ⊢ n and p ∤ χ (1) ,
λ
and we let br(n) be the maximal value in En (i.e. br(n) = max{|λ−
p′ | : λ ⊢ n and p ∤ χ (1)}).
Our first result describes En and gives a recursive formula for the exact value of br(n).

The first author’s research was funded by Trinity Hall, University of Cambridge.
1

2

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

P
Theorem A. Let n ∈ N and let p be a prime. Let n = tj=1 aj pnj be the p-adic expansion of
n, for some 0 ≤ n1 < n2 < · · · < nt . Then En = {1, 2, . . . , br(n) − 1, br(n)} and
n1

br(n) = br(a1 p ) +

t
X

Φ(aj , br(mj ))

j=2

where mj =

Pj−1
i=1

ai pni , and where Φ is the function described explicitly in Definition 2.1 below.

In Section 5 we determine exactly br(apk ) for any prime p, any k ∈ N0 and any a ∈ {1, . . . , p −
1}. The following result serves as the base case for computing br(n) for any natural number n,
using the recursive expression given in Theorem A.
Theorem B. Let p be an odd prime, k ∈ N0 and a ∈ {1, . . . , p − 1}. Then


if k = 0,
f (2a)
2a−(p−1)
k
br(ap ) = p − 1 + 2⌊
⌋ if k = 1 and p2 < a < p,
6


2a
otherwise.

Here f (x) = max{y ∈ N0 | y(y + 1) ≤ x}.

Theorem B is stated only for odd primes since we know that if p = 2, then br(2k ) = 1 for all
k ∈ N0 , by [1].
Theorems A and B provide us with a recursive formula for br(n), the maximal number of
downward edges from level n to level n − 1 of Yp′ . In the second part of our article we show that
the slightly involved expression for the value of br(n) described in Theorem A can be bounded
from above by a much nicer function of the p-adic digits of n.
P
Theorem C. Let n ∈ N and let p be a prime. Let n = tj=1 aj pnj be the p-adic expansion of
n, for some 0 ≤ n1 < n2 < · · · < nt . Then 1 ≤ br(n) ≤ Bn , where
t j
t j
X
X
aj k
aj k
n1
≤ 2a1 +
.
Bn = br(a1 p ) +
2
2
j=2

j=2

Theorem C has some interesting direct applications (see Section 4). For instance, in Remark 4.2 below, we observe that when p ∈ {2, 3} then Bn = br(n). In particular our result is a
generalization of Theorem 1. Moreover, for any prime p we observe that the upper bound Bn is
attained for every n having all of its p-adic digits lying in {0, 1, 2, 3}.
We further show that the upper bound Bn given in Theorem C is indeed a good approximation
of br(n). In fact, the following result shows that the difference εn := Bn − br(n) can be bounded
by a constant depending only on the prime p, and not on n ∈ N.
Theorem D. For any n ∈ N, we have εn < p2 log2 (p).

A consequence of Theorem D is that for any odd prime p we have sup{br(n) : n ∈ N} = ∞.
This is false when p = 2, by Theorem 1.
2. Notation and Preliminaries
In this section we fix the notation that will be used throughout the article and recall some
basic facts in the representation theory of symmetric groups (we refer the reader to [6] and [10]
for detailed accounts of the theory). We begin by introducing the technical notation necessary
to state and prove Theorem A.

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

3

Definition 2.1. For a ∈ N0 and L ∈ N, define
)
( L
X
f (ai ) a1 + · · · + aL ≤ a and ai ∈ N0 ∀ 1 ≤ i ≤ L ,
Φ(a, L) := max
i=1

where f (x) = max{y ∈ N0 | y(y + 1) ≤ x}.

We now record some properties of this function Φ which will be useful for later proofs.
Lemma 2.2. Let a ∈ N0 and L ∈ N. Then Φ(a, L) ≤ ⌊a/2⌋. In particular, if L ≥ ⌊a/2⌋ then
Φ(a, L) = ⌊a/2⌋.
Proof. Observe that for all integers x ≥ 2, we have f (x) ≤ f (2) + f (x − 2). Hence
Φ(a, L) ≤ ⌊a/2⌋ · f (2) + f (δ)

where δ ∈ {0, 1} and δ ≡ a (mod 2). But f (2) = 1 and f (1) = f (0) = 0, so the assertions
follow.

Lemma 2.3. Let k ∈ N. Then 2k−1 ≤ Φ(2k + 2, 2k−1 ) ≤ 2k−1 + 1.
Proof. When k = 1, we note that Φ(4, 1) = 1. Now assume k ≥ 2. The upper bound follows
from Lemma 2.2. The lower bound follows from the fact that 2k + 2 = 6 + 2 · (2k−1 − 2) + 0,
and f (6) + f (2) · (2k−1 − 2) + f (0) = 2k−1 .

2.1. Combinatorics of partitions. Let n be a natural number. We denote by P(n) the set
of partitions of n and we let
[
P(n).
P=
n∈N

The notation λ ∈ P(n) is sometimes replaced by λ ⊢ n. For any natural number e, we denote
by Ce (λ) and Qe (λ) = (λ0 , λ1 , . . . , λe−1 ) the e-core and the e-quotient of λ respectively. The
e-weight of λ is the natural number we (λ) defined by we (λ) = |λ0 | + |λ1 | + · · · + |λe−1 |. We
remark that given a partition λ of n, the e-quotient Qe (λ) is uniquely determined up to a cyclic
shift of its components. Moreover, it is well-known that (up to the above mentioned shift) any
partition is uniquely determined by its e-core and e-quotient (we refer the reader to [10] for a
detailed discussion on the topic).
Let He (λ) be the set of hooks of λ having length divisible by e and let H(Qe (λ)) = ∪ei=1 H(λi ).
As explained in [10, Theorem 3.3], there is a bijection between He (λ) and H(Qe (λ)) mapping
hooks in λ of length ex to hooks in the quotient of length x. Moreover the bijection respects
the process of hook removal. Namely, the partition µ obtained by removing a ex-hook from λ is
such that Ce (µ) = Ce (λ) and the e-quotient of µ is obtained by removing a x-hook from one of
the e partitions involved in the e-quotient of λ. The other fundamental result we need to recall
is [10, Proposition 3.6], which can be stated as follows.
Proposition 2.4. Let λ ∈ P(n). The number of e-hooks that must be removed from λ to obtain
Ce (λ) is we (λ). Moreover we (λ) = |He (λ)| = (|λ| − |Ce (λ)|)/e.
James’ Abacus. All of the operations on partitions concerning addition and removal of ehooks described above are best performed on James’ abacus. We give here a brief description
of this important object, and introduce some pieces of notation that will be used extensively
throughout. We refer the reader to [6, Chapter 2] for a complete account of the combinatorial
properties of James’ abacus.
Let λ be a partition of n and let A be an e-abacus configuration for λ. Denote by A0 , A1 ,
. . . , Ae−1 the runners in A from left to right and label the rows by integers such that the row

4

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

numbers increase downwards. As is customary, all abaci contain finitely many rows and hence
finitely many beads, but in all instances enough to perform all of the necessary operations. For
j ∈ {0, . . . , e − 1}, denote by |Aj | the number of beads on runner j. Moreover, we denote by A↑
the e-abacus obtained from A by sliding all beads on each runner as high as possible. Extending
the notation just introduced, we denote by A↑0 , . . . , A↑e−1 the runners of A↑ . As explained in
[6, Chapter 2], A↑ is an e-abacus for Ce (λ). Let the operation of sliding any single bead down
(resp. up) one row on its runner be called a down-move (resp. up-move). Of course, such a move
is only possible for a bead in position (i, j) (that is, in row i on runner Aj ) if the respective
position (i ± 1, j) was empty initially. Sometimes we call an empty position a gap. We say that
position (x, y) is the first gap in A if there are beads in positions (i, j) for all i < x and all j,
and in positions (x, j) for all j < y.
On the level of partitions, performing a down- or up-move corresponds to adding or removing
an e-hook, respectively. In analogy with the notation used for partitions, we denote by w(A)
the total number of up-moves needed to obtain A↑ from A. Similarly, for i ∈ {0, . . . , e − 1} we
let w(Ai ) be the number of those up-moves that were performed on runner i in the transition
from A to A↑ . It is easy to see that we (λ) = w(A) = w(A0 ) + · · · + w(Ae−1 ).
Suppose that c is a bead in position (i, j) of A. We say that c is a removable bead if j 6= 0 and
there is no bead in (i, j − 1), or if j = 0 and there is no bead in (i − 1, e − 1). Denote by A←c
the abacus configuration obtained by sliding c into position (i, j − 1) (respectively (i − 1, e − 1)).
Clearly A←c is an abacus configuration for a partition µ ∈ λ− , and conversely any µ ∈ λ− can
be represented by A←c for some such c, since removable beads in an abacus of λ correspond to
removable nodes in the Young diagram of λ. Here and throughout the remainder of the article
we denote by λ− the subset of P(n − 1) consisting of all partitions whose Young diagram can
be obtained from that of λ by removing a node.
Finally, for j ∈ {0, . . . , e − 1} we denote by Rem(Aj ) the number of removable beads in A
lying on runner Aj . In particular, we have that |λ− | = Rem(A0 ) + · · · + Rem(Ae−1 ).
Lemma 2.5. Let e ∈ N. Let λ be a partition of any natural number, and denote by A an
e-abacus configuration for λ. Suppose c is a removable bead on runner Aj and let µ ⊢ n − 1 be
the partition represented by A←c . Then
(
|Aj | − |Aj−1 | − 1 if j 6= 0
we (µ) = we (λ) +
|A0 | − |Ae−1 | − 2 if j = 0.
Proof. First suppose j 6= 0. Without loss of generality we can relabel the rows of the e-abacus
A such that all rows labelled by negative integers do not have empty positions. To ease the
notation we let B := A←c . Clearly w(Ai ) = w(Bi ) for all i 6= j − 1, j in {0, . . . , e − 1}. Hence
we (µ) − we (λ) = w(Bj−1 ) + w(Bj ) − w(Aj−1 ) − w(Aj ).

Let s and t be the numbers of beads lying in rows labelled by non-negative integers in runners
Aj−1 and Aj respectively. Suppose that the s beads on Aj−1 lie in rows 0 ≤ x1 < · · · < xs and
that the t beads on Aj lie in rows 0 ≤ y1 < · · · < yt . Then
w(Aj−1 ) + w(Aj ) =

s
X
i=1

(xi − (i − 1)) +

t
X
i=1

(yi − (i − 1)) =

s
X
i=1

xi +

t
X
i=1

yi −

s(s−1)
2

−

t(t−1)
2 .

Suppose that the bead c lies in row yl for some l ∈ {1, . . . , t}. Since c is removable, yl 6=
xi for all i ∈ {1, . . . , s}. Thus the beads on Bj−1 lie in rows 0 ≤ x′1 < · · · < x′s+1 with
′
with
{x′1 , . . . , x′s+1 } = {x1 , . . . , xs , yl } and the beads on Bj lie in rows 0 ≤ y1′ < · · · < yt−1

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

5

′ } = {y , . . . , y
{y1′ , . . . , yt−1
1
l−1 , yl+1 , . . . , yt }. Hence

t
s
t−1
s+1
X
X
X
X
′
′
yi −
xi +
(y1 − (i − 1)) =
(xi − (i − 1)) +
w(Bj−1 ) + w(Bj ) =
i=1

i=1

i=1

s(s+1)
2

i=1

and we conclude that we (µ) − we (λ) = t − s − 1 = |Aj | − |Aj−1 | − 1.
The case when j = 0 is similar.

−

(t−1)(t−2)
2



Remark 2.6. In this note, given a partition λ and a fixed e-abacus configuration A for λ we
let λi be the partition corresponding to the runner Ai , considered as a 1-abacus. The resulting
e-quotient (λ0 , λ1 , . . . , λe−1 ) depends on the choice of the abacus A (a different choice of the
e-abacus may induce a cyclic shift on the components of the e-quotient). Nevertheless, all of
the results presented in Section 2 onwards hold independently of this observation. For instance,
the e-weight we (λ) introduced at the beginning of Section 2.1 does not depend on the choice of
the e-abacus; the same discussion holds for Theorem 2.8 below.
2.2. Characters of Sn . For each n ∈ N, the elements of the set Irr(Sn ) of irreducible characters
of Sn are naturally labelled by partitions of n. For λ ∈ P(n), the corresponding irreducible
character is denoted by χλ . In this article we will often identify the labelling partition with the
corresponding irreducible character, and hence write λ ∈ Irr(Sn ) to denote at once the partition
λ of n and the irreducible character χλ . The meaning of this notation will always be clear from
the context. We recall the Branching rule (see [5, Chapter 9]) which tells us that
X
(χλ )Sn−1 =
χµ .
µ∈λ−

By convention we let S0 be the trivial 1-element group and P(0) = {∅}.
From now on let p be a prime. We denote by Irrp′ (Sn ) the set of irreducible characters of Sn
of degree coprime to p. We say that λ is a p′ -partition of n (written λ ⊢p′ n) if λ ∈ Irrp′ (Sn ).
Thus the set En may be written as {|λ−
p′ | : λ ⊢p′ n}, and we remark here that br(n) = max En is
well-defined. Indeed, for any n ∈ N, if λ ⊢p′ n then |λ−
p′ | ≥ 1, so En is non-empty and br(n) ≥ 1.

Irreducible characters of Sn of p′ -degree were completely described in [8]. We restate this
result in language that will be particularly convenient for our purposes.
Theorem 2.7. Let n be a natural number and let λ ∈ Irr(Sn ). Let a ∈ {1, . . . , p−1} and k ∈ N0
be such that apk ≤ n < (a + 1)pk . Then λ ∈ Irrp′ (Sn ) if and only if Cpk (λ) ∈ Irrp′ (Sn−apk ).

Theorem 2.7 says that λ is a p′ -partition if and only if wpk (λ) = a and the partition Cpk (λ)
obtained from λ by successively removing all possible pk -hooks is a p′ -partition of n − apk . It
will sometimes be useful to use the following equivalent version of Theorem 2.7.
P
Theorem 2.8. Let n = kj=0 aj pj be the p-adic expansion of n ∈ N. Let λ ∈ Irr(Sn ) and let
Qp (λ) = (λ0 , λ1 , . . . , λp−1 ). Then λ ∈ Irrp′ (Sn ) if and only if
(i) Cp (λ) ⊢ a0 , and
(ii) for all t ∈ {0, 1, . . . , p − 1} there exists b1t , b2t , . . . , bkt ∈ N0 such that
p−1
X
t=0

bjt = aj for all j ∈ {1, . . . k}, and such that λt ⊢p′
p′ -partitions

k
X

bjt pj−1 .

j=1

Proof. This characterization of
of n ∈ N can be easily proved using the p-core tower
associated to any partition of n. We refer the reader to [10, Chapters I and II] for the precise
description of this combinatorial object.


6

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

3. The core map and the proofs of Theorems A and C
In this section we prove some combinatorial statements that will play a fundamental role in
the proofs of all of our main theorems. As a consequence of these observations, we are able to
give proofs of Theorems A and C. As appropriately remarked later in this section, the proof of
Theorem B is postponed to Section 5 to improve readability.
Notation 3.1. Unless otherwise stated, in this section we fix n ∈ N such that n = apk + m
for some k ≥ 1, a ∈ {1, . . . , p − 1} and 0 < m < pk . To be precise this will be the standing
assumption from Lemma 3.2 to Proposition 3.11.
Lemma 3.2. Let λ ⊢ n be such that wpk (λ) = w ≤ a and denote by A a pk -abacus configuration
for λ. Suppose c is a removable bead on runner Aj and let µ ⊢ n − 1 be the partition represented
by A←c . Then wpk (µ) = w if and only if
(
1 + |Aj−1 | if j 6= 0,
|Aj | =
2 + |Apk −1 | if j = 0.
Proof. This is immediate by Lemma 2.5.



The following result, which we believe is of independent interest, is one of the key steps in
proving Theorem A.
−
Theorem 3.3. Let λ ⊢p′ n and let α ∈ λ−
p′ . Then Cpk (α) ∈ µp′ , where µ := Cpk (λ). In
particular we deduce that the map
−
C p k : λ−
p′ −→ µp′ ,
is well-defined. Moreover, it is surjective.

Proof. Let A be the pk -abacus configuration for µ having first gap in position (0, 0). It is easy
to see that rows i ≥ 1 must be empty, since |µ| = m < pk . (We will not need rows i with |i| > a,
so we may assume row −a is the top row of the abacus and +a the bottom row.) So |A0 | = a
and a ≤ |Aj | ≤ a + 1, for all j ∈ {0, . . . , pk − 1}. Let B be the pk -abacus configuration for λ
such that B ↑ = A. By Proposition 2.4, we have wpk (λ) = a and we see that B is obtained from
A after performing exactly a down-moves.
Let c be the bead in B such that B ←c is an abacus configuration for α, and suppose c lies
on runner Bj . Since α is a p′ -partition of n − 1 = apk + (m − 1) ≥ apk we deduce from
Theorem 2.7 that wpk (α) = a. Hence by Lemma 3.2 we have |Bj | = 1 + |Bj−1 | (j cannot be 0
because |Bl | = |Al | ∈ {a, a + 1} for all l ∈ {0, . . . , pk − 1}). It follows that there exists a bead
d in position (0, j) of A and that position (0, j − 1) of A is empty. Hence A←d is a pk -abacus
configuration for Cpk (α), which by Theorem 2.7 must be a p′ -partition. Thus Cpk (α) ∈ µ−
p′ and
−
−
the map Cpk : λp′ −→ µp′ is well-defined.
To show that the map is surjective we proceed as follows. Let A be the pk -abacus configuration
←d is a pk -abacus
for µ as described above. For any β ∈ µ−
p′ there exists a bead d in A such that A
configuration for β. Let j ∈ {1, . . . , pk − 1} be such that d is in position (0, j) in A and such
that position (0, j − 1) is empty. Let B be the pk -abacus for λ described above. Clearly we have
that |Bj | = |Aj | = 1 + |Aj−1 | = 1 + |Bj−1 |. Hence there exists a row y ∈ {−a, . . . , a} such that
position (y, j − 1) of B is empty and such that there is a bead (say e) in position (y, j). Let α be
the partition corresponding to the pk -abacus B ←e. By Lemma 3.2 we deduce that wpk (α) = a.
Moreover it is clear that Cpk (α) = β ∈ Irrp′ (Sn−apk ). By Theorem 2.7 we deduce that α ∈ λ−
p′
and therefore Cpk is surjective.


ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

7

−
Corollary 3.4. Let λ ⊢p′ n. Then |Cpk (λ)−
p′ | ≤ |λp′ |.

Keeping n = apk + m as in Notation 3.1, we now introduce the following notation. Given
γ ⊢p′ m, define
br(n, γ) := max{|λ−
p′ | : λ ⊢p′ n and Cpk (λ) = γ}.

Clearly br(n), the main object of our study, is equal to the maximal br(n, γ), where γ is any
p′ -partition of m. Corollary 3.4 allows us to give the following definition.
Definition 3.5. Let n = apk +m be as in Notation 3.1, and let γ ⊢p′ m. We define N (a, pk , γ) ∈
N0 to be such that |γp−′ | + N (a, pk , γ) = br(n, γ).
One of the main goals of the present section is to prove the following fact.
Proposition 3.6. Let γ ⊢p′ m and let L = |γp−′ |. Then N (a, pk , γ) = Φ(a, L), where Φ is as
described in Definition 2.1.
In order to prove Proposition 3.6, we need to introduce the following combinatorial concepts.
Definition 3.7. Let n = apk + m be as in Notation 3.1, and let γ ⊢p′ m. Denote by Aγ the
pk -abacus configuration for γ having first gap in position (0, 0). Define RAγ to be the subset of
{0, 1, . . . , pk − 1} such that j ∈ RAγ if and only if there is a removable bead c on runner j of Aγ
such that the partition corresponding to the pk -abacus A←c
is a p′ -partition of m − 1.
γ

Since Aγ has first gap in position (0, 0) and since |γ| = m < pk we deduce that all removable
beads in Aγ lie in row 0. Hence |RAγ | = |γp−′ |. By definition of removable bead, we have in
particular that 0 ∈
/ RAγ , and for 1 ≤ j ≤ pk − 2 we have that if j ∈ RAγ then j + 1 ∈
/ RA γ .

Lemma 3.8. Let γ ⊢p′ m. Let λ ⊢p′ n be such that Cpk (λ) = γ and let B be the pk -abacus for
λ such that B ↑ = Aγ . Let c be a removable bead on runner j of B and let µ be the partition of
n − 1 corresponding to B ←c . Then µ is a p′ -partition if and only if j ∈ RAγ .

Proof. Let A := Aγ . First suppose j ∈ RA . In particular, j 6= 0. Then
|Bj | = |Aj | = |Aj−1 | + 1 = |Bj−1 | + 1,

so wpk (µ) = a by Lemma 3.2. We also have that (B ←c )↑ is an abacus configuration for Cpk (µ).
Moreover if d is the bead in position (0, j) of A then (B ←c )↑ = A←d . Therefore we deduce that
Cpk (µ) ∈ γp−′ and hence that µ ⊢p′ n − 1, by Theorem 2.7.
Now suppose that j ∈
/ RA . If j = 0 then |B0 | = |A0 | =
6 |Apk −1 | + 2 = |Bpk −1 | + 2. Hence
′
wpk (µ) 6= a by Lemma 3.2 and therefore µ is not a p -partition, by Theorem 2.7. Now we may
assume that j 6= 0. If |Aj | =
6 |Aj−1 | + 1 then |Bj | =
6 |Bj−1 | + 1 and hence wpk (µ) 6= a, by
Lemma 3.2. In particular µ is not a p′ -partition, by Theorem 2.7. If |Aj | = |Aj−1 | + 1, then
Cpk (µ) ∈ γ − is represented by the pk -abacus (B ←c )↑ . Again we have that (B ←c )↑ = A←d , where
d is the bead in position (0, j) of A. Since j ∈
/ RA we deduce that Cpk (µ) is not a p′ -partition.
It follows that µ ⊢ n − 1 is not a p′ -partition, by Theorem 2.7.


Corollary 3.9. Let γ ⊢p′ m and let λ ⊢p′ n be such that Cpk (λ) = γ. Let B be the pk -abacus
for λ such that B ↑ = Aγ . Then
X
|λ−
Rem(Bj ).
|
=
′
p
j∈RAγ

Recall from Definition 2.1 that f (x) = max{y ∈ N0 | y(y + 1) ≤ x}. The following lemma
describes the key relationship between this function f and certain removable beads, which will
be necessary for the proof of Proposition 3.6 (below).

8

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

Lemma 3.10. Let λ ∈ {∅, (1)} and let Tλ denote the 2-abacus configuration of λ having first
gap in position (0, 0). Let x ∈ N0 and let Tλ (x) be the set of all 2-abaci U such that w(U ) = x
and U ↑ = Tλ . Then
(
f (x) + 1 if λ = (1),
max{Rem(U1 ) | U ∈ Tλ (x)} =
√
if λ = ∅.
⌊ x⌋
Proof. This is clear if x = 0 or x = 1, so we may assume now that x ≥ 2 (and hence f (x) > 0).
We first fix λ = (1); this is the case that we will need to use in the proof of Proposition 3.6
below. Since λ is now fixed, we ease the notation by letting T(1) = T and T(1) (x) = T (x), for
all x ∈ N0 . Moreover, let F (x) := max{Rem(U1 ) | U ∈ T (x)}. We first show that there exists
A ∈ T (x) such that Rem(A1 ) = F (x) and such that w(A0 ) = 0 (equivalently w(A1 ) = x).
Let U ∈ T (x) be such that w(U0 ) = ℓ and Rem(U1 ) = r for some l ∈ {1, 2, . . . , x} and some
r ∈ {0, 1, . . . , F (x)}. Then there exists a 2-abacus V ∈ T (y) for some y ≤ x such that w(V0 ) < ℓ
and Rem(V1 ) ≥ r. This follows from the following observation. Since ℓ ≥ 1 there exists i ∈ Z
such that there is a bead in position (i, 0) of U and such that position (i − 1, 0) of U is empty.
Denoting beads by X and gaps by O, consider the four possibilities for rows i − 1 and i of U :
i−1
i

OO
XX

OO
XO

OX
XX

OX
XO

In the first three instances, we can move the bead in (i, 0) to (i − 1, 0), to obtain the desired
abacus configuration V . In the fourth case, we need to additionally move the bead in (i− 1, 1) to
(i, 1). Hence, if B ∈ T (x) is such that Rem(B1 ) = F (x) then there exists y ≤ x and A′ ∈ T (y)
such that Rem(A′1 ) = F (x), w(A′0 ) = 0 and w(A′1 ) = y. Let (i, 1) be the lowest position occupied
by a bead (say d) in A′ . Moving d to position (i + (x − y), 1) we obtain a 2-abacus configuration
A ∈ T (x) such that Rem(A1 ) = Rem(A′1 ) = F (x), w(A0 ) = 0 and w(A1 ) = x, as desired.
We want to prove that F (x) = f (x)+1. First suppose for a contradiction that F (x) ≥ f (x)+2,
and let A ∈ T (x) be such that Rem(A1 ) = F (x) and w(A0 ) = 0. By construction there exists
integers 0 ≤ j1 < j2 < · · · < jf (x)+2 such that there is a bead in position (jk , 1) of A for
all k ∈ {1, . . . , f (x) + 2}. This implies that w(A) = w(A1 ) ≥ (f (x) + 1)(f (x) + 2) > x, a
contradiction. Hence F (x) ≤ f (x) + 1.
Now let y := f (x)(f (x) + 1) ≤ x. Let B be the 2-abacus configuration obtained from T by
first sliding down the bead in position (0, 1) to position (f (x) + x − y, 1) and then sliding down
the bead in position (i, 1) to position (i + f (x), 1) for i = −1, −2, . . . , −f (x). Clearly B ∈ T (x)
and Rem(B1 ) = f (x) + 1. We conclude that F (x) = f (x) + 1, as desired.
The case λ = ∅ is similar.


Proof of Proposition 3.6. Let λ ⊢p′ n be such that Cpk (λ) = γ and |λ−
p′ | = br(n, γ). Let B be
k
↑
the p -abacus for λ such that B = Aγ . In particular, B is obtained from Aγ by performing a
down-moves. Let RAγ = {j1 , . . . , jL }. Then by Corollary 3.9, we have
k

L + N (a, p , γ) = br(n, γ) =

|λ−
p′ |

=

L
X

Rem(Bji ).

i=1

Let ai = w(Bji −1 ) + w(Bji ) for i ∈ {1, 2, . . . , L}, so a1 + · · · + aL ≤ a. Since no two numbers
in RAγ are consecutive (as remarked after Definition 3.7), we can regard the pairs of runners
of (Bj1 −1 , Bj1 ), (Bj2 −1 , Bj2 ), . . . , (BjL −1 , BjL ) as L disjoint 2-abaci, whose 2-cores are all equal
to the 2-abacus T(1) considered in Lemma 3.10. It is easy to see that the 2-abacus identified
by the pair (Bji −1 , Bji ) lies in T(1) (ai ) for all i ∈ {1, . . . , L}. Lemma 3.10, together with the
′
k
maximality of |λ−
p′ | among all the p -partitions of n with p -core equal to γ, allows us to deduce

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

9

that Rem(Bji ) = f (ai ) + 1, for all i ∈ {1, . . . , L}. Hence we obtain
N (a, pk , γ) =

L
X
i=1

Rem(Bji ) − L =

L
X

f (ai ).

i=1

We conclude the proof by showing that
)
( L
X
′
′
′
′
k
f (ai ) | a1 + · · · + aL ≤ a, ai ∈ N0 ∀ i = Φ(a, L).
N (a, p , γ) = max
i=1

Suppose for a contradiction that there exists a natural number y ≤ a and (a′1 , . . . , a′L ) a
PL
′
k
composition of y such that
i=1 f (ai ) > N (a, p , γ). Since f is a non-decreasing function,
without loss of generality we can assume that y = a. Then by using constructions analogous
to those in the proof of Lemma 3.10, we can construct a partition λ̃ ⊢p′ n with Cpk (λ̃) = γ,
wpk (λ̃) = a and pk -abacus configuration B̃ satisfying B̃ ↑ = Aγ such that w(B̃ji ) = a′i and
Rem(B̃ji ) = f (a′i ) + 1 for all i ∈ {1, . . . , L}. This implies that
br(n, γ) ≥ |λ̃−
p′ | = L +

L
X
i=1

f (a′i ) > L + N (a, pk , γ) = |λ−
p′ | = br(n, γ),

which is a contradiction. Hence N (a, pk , γ) = Φ(a, L).
Proposition 3.11. Let γ ⊢p′ m. Then br(n) = br(n, γ) if and only if
particular, br(n) = br(m) + Φ(a, br(m)).


|γp−′ |

= br(m). In

Proof. First suppose that br(n) = br(n, γ). Let λ ⊢p′ n be such that Cpk (λ) = γ and |λ−
p′ | =
−
−
−
br(n), so that br(n) = |γp′ |+Φ(a, |γp′ |) by Proposition 3.6. Let δ ⊢p′ m be such that |δp′ | = br(m).
Then, since Φ(X, Y ) is non-decreasing in each argument (when the other argument is fixed), we
have
br(n) ≥ br(n, δ) = |δp−′ | + Φ(a, |δp−′ |) = br(m) + Φ(a, br(m)) ≥ |γp−′ | + Φ(a, |γp−′ |) = br(n),

whence equalities hold in the above. This proves all three statements: br(m) = |γp−′ | gives the
only if direction; br(n) = br(n, δ) gives the if direction (with δ in place of γ); and the final
assertion is clear.

This is enough to deduce that the second statement of Theorem A holds.
P
Corollary 3.12. Let n = tj=1 aj pnj be the p-adic expansion of n, for some 0 ≤ n1 < · · · < nt .
Pj−1
ai pni , then
Let mj = i=1
n1

br(n) = br(a1 p ) +

t
X

Φ(aj , br(mj )).

j=2

Proof of Theorem C. This is a straightforward consequence of Lemma 2.2 and Corollary 3.12.

In the last part of this section we aim to complete the proof of Theorem A, by studying the
λ
set En = {|λ−
p′ | : λ ⊢ n and p ∤ χ (1)}. We first state and assume the following theorem.
Theorem 3.13. Let p be a prime, k ∈ N0 and a ∈ {1, 2, . . . , p−1}. Then Eapk = {1, 2, . . . , br(apk )}.

10

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

The proof of Theorem 3.13 is rather more technical, and so has been postponed to Section 5.
More precisely, Theorem 3.13 follows from Propositions 5.1, 5.4 and 5.14, which are proved in
Section 5 below.
The next statement extends the observations already made in Lemma 3.10, and is crucial to
completing the description of the set En .

Lemma 3.14. Let B = T(1) denote the 2-abacus configuration of the partition (1) having first
gap in position (0, 0). Let x ∈ N0 and let T (x) be the set consisting of all 2-abaci U such that
w(U ) = x and U ↑ = B. Then {Rem(U1 ) | U ∈ T (x)} = {1, 2, . . . , f (x) + 1}.

Proof. From Lemma 3.10 we know that f (x) + 1 is the maximal value in {Rem(U1 ) | U ∈ T (x)}.
For any r ∈ {0, 1, . . . , f (x)}, let U (r) be the 2-abacus configuration obtained from B by first
sliding down the bead in position (0, 1) to position (x − r(r + 1), 1) and then (if r > 0) sliding
down the bead in position (i, 1) to position (i+ r, 1) for i = −1, −2, . . . , −r. Clearly U (r) ∈ T (x)
and Rem(U (r)1 ) = r + 1.

Pt
Theorem 3.15. Let n ∈ N and let p be a prime. Let n = j=1 aj pnj be the p-adic expansion
of n, for some 0 ≤ n1 < n2 < · · · < nt . Then En = {1, 2, . . . , br(n)}.

Proof. We prove the assertion by induction on t, the p-adic length of n. If t = 1 then the
statement follows from Theorem P
3.13.
nj and let γ be a p′ -partition of m such that |γ − | =
Assume that t ≥ 2. Let m = t−1
j=1 aj p
p′
br(m). For convenience, let L = br(m) and k = nt . As in Definition 3.7 let A := Aγ be the
pk -abacus configuration for γ having first gap in position (0, 0). Moreover, let RA = {j1 , . . . , jL }.
Applying Lemma 3.14 to the L pairs of runners (Aji −1 , Aji ) of A, we see that for each r ∈
{0, 1, . . . , Φ(at , L)}, there exists a sequence of at down-moves that can be performed on A to
produce a pk -abacus B r such that
X
Rem(Bjr ) = L + r.
j∈RA

Let λ(r) be the partition of n corresponding to B r . Clearly Cpk (λ(r)) = γ and by Theorem 2.7
we deduce that λ(r) ⊢p′ n. Moreover, |λ(r)−
p′ | = L + r by Corollary 3.9. Hence L + r ∈ En , and
thus {L, L + 1, . . . , br(n)} ⊆ En , noting that L + Φ(at , L) = br(n, γ) = br(n) by Proposition 3.11.
If L = 1 then the proof is complete; otherwise, using the inductive hypothesis we have that for
any i ∈ {1, 2, . . . , L−1}, there exists γ(i) ⊢p′ m such that |γ(i)−
p′ | = i. Taking r = 0 and replacing
γ by γ(i) in the above construction, we construct β(i) ⊢p′ n such that Cpk (β(i)) = γ(i) and
|β(i)−

p′ | = i + 0. Hence {1, 2, . . . , L − 1} ⊆ En , and we conclude that En = {1, 2, . . . , br(n)}.
Proof of Theorem A. This follows directly from Corollary 3.12 and Theorem 3.15.



4. The upper bound Bn
P
In this section we prove Theorem D. Let n ∈ N and let n = tj=1 aj pnj be the p-adic expansion
of n, for some 0 ≤ n1 < · · · < nt . Recall that
t j
X
aj k
n1
.
Bn = br(a1 p ) +
2
j=2

From Lemma 2.2 and Corollary 3.12, we see that br(n) ≤ Bn , and the difference εn = Bn − br(n)
can be written as
t
X
(⌊aj /2⌋ − Φ(aj , br(mj )))
εn =
j=2

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

where mj =
below.

Pj−1
i=1

11

ai pni . The following statement will be useful in the proof of Theorem D,

Lemma 4.1. Lets, t ∈ N0 with
1 , . . . , bt ∈ {0, 1, . . . , p − 1} with b0 , b1 , . . . , bs not
 s ≤t.PLet b0 , b
Ps
t
j
j
≤ br
all zero. Then br
j=0 bj p
j=0 bj p .

Proof. This follows directly from Proposition 3.11.



Proof of Theorem D. Fix n ∈ N and its p-adic expansion as above. Let ε(j) = ⌊aj /2⌋ −
Φ(aj , br(mj )). If aj ≤ 3 then ε(j) = 0 by Lemma 2.2, since br(mj ) ≥ 1. Hence if aj ≤ 3
for all j ≥ 2, then in fact εn = 0. In particular if p ≤ 3 then εn = 0, so from now on we may
assume p ≥ 5 and that there exists i ∈ {2, . . . , t} such that ai ≥ 4. In particular, there exists a
unique k ∈ {1, . . . , t} and integers 1 = i0 < i1 < i2 < · · · < ik ≤ t such that for all j ∈ {1, . . . , k}

ij := min x ∈ {ij−1 + 1, . . . , t − 1, t} | ax ≥ 2j + 2 ,

and such that {x ∈ {ik + 1, . . . , t − 1, t} | ax ≥ 2k+1 + 2} = ∅. Note k must satisfy 2k < p,
because if 2k ≥ p then aik ≥ 2k + 2 > p − 1, contradicting the fact that aik is a p-adic digit.
We first show that br(mij ) ≥ 2j−1 for all j ∈ N by induction. This is clear for j = 1. For
j ∈ {2, . . . , t}, we have that
br(mij ) ≥ br(mij−1 +1 ) = br(mij−1 ) + Φ(aij−1 , br(mij−1 )) ≥ 2j−2 + Φ(2j−1 + 2, 2j−2 ) ≥ 2j−1 .

The inequalities above hold by Lemma 4.1, the fact that Φ is non-decreasing in each argument,
the inductive hypothesis and Lemma 2.3, while the equality follows from Proposition 3.11. Thus
for all x ≥ ij + 1 we have that
br(mx ) ≥ br(mij +1 ) = br(mij ) + Φ(aij , br(mij )) ≥ 2j−1 + Φ(2j + 2, 2j−1 ) ≥ 2j .

Now let x ∈ {2, . . . , t} be such that ij < x < ij+1 for some j ∈ {1, . . . , k}. Since x < ij+1 ,
we have ax ≤ 2j+1 + 1, and since x > ij , we have by the above discussion that br(mx ) ≥ 2j .
Therefore br(mx ) ≥ ⌊ax /2⌋ and hence ε(x) = 0, by Lemma 2.2. Similarly if x < i1 then ax ≤ 3
and so ε(x) = 0, while if x > ik then br(mx ) ≥ 2k ≥ ⌊ax /2⌋ and thus ε(x) = 0 also. Hence
εn =

k
X

ε(ij ).

j=1

Finally, for each j ∈ {1, . . . , k}, we have by Lemma 2.3 that
Hence

ε(ij ) = ⌊aij /2⌋ − Φ(aij , br(mij )) ≤
εn =

k
X
j=1

p−1
2

k−1
X
i
( p−1
ε(ij ) ≤
2 −2 ) = k·
i=0

− Φ(2j + 2, 2j−1 ) ≤

p−1
2

− (2k − 1) < k ·

p
2

p−1
2

<

p
2

− 2j−1 .
log2 p.


Remark 4.2. Theorem D shows that the difference between the upper bound Bn and the actual
value of br(n) is relatively small, and can be bounded independently of n. If p ∈ {2, 3} then
εn = 0, as observed in the first part of the proof of Theorem D above. In particular, fixing p = 2
we recover [1, Theorem 1]. As already mentioned in the introduction, the proof of Theorem D
also shows for any prime p, we have Bn = br(n) whenever all of the p-adic digits of n are at
most 3.

12

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

5. The value of br(apk ) and the set Eapk
The main goals in this section are to prove Theorem B (i.e. determining the value of br(apk ))
and to prove Theorem 3.13 (i.e. showing that Eapk = {1, 2, . . . , br(apk )}). As already remarked
in the introduction, these two results play the role of base cases for Theorem A.
From now on, let p be an odd prime. The case when k = 0 is straightforward and is described
in the following proposition.
Proposition 5.1. Let a ∈ {1, 2, . . . , p − 1}. Then br(a) = f (2a) and Ea = {1, 2, . . . , br(a)}.

Proof. Every partition of a − 1 is a p′ -partition, and we can always construct a partition λ of
a such that |λ− | = m for any 1 ≤ m ≤ f (2a), since f (2a) is the maximum number of parts of
distinct size achieved by a partition of a.

In the following proposition we provide a naive upper bound for br(apk ), for all k ∈ N and
a ∈ {1, . . . , p − 1}. As we will show in the rest of this section, this bound turns out to be tight
for almost all values of a and k.
Proposition 5.2. Let a ∈ {1, 2, . . . , p − 1} and let k ∈ N. Then br(apk ) ≤ 2a.

Proof. Let C and D be pk -abacus configurations such that D is obtained from C by performing
a single down-move. It is easy to see that the number of removable beads in D is at most the
number of removable beads in C plus two. Hence if λ is a partition such that Cpk (λ) = ∅ then
|λ− | ≤ 2wpk (λ). Now let n = apk and let λ ⊢p′ n be such that |λ−
p′ | = br(n). From Theorem 2.7

we know that Cpk (λ) = ∅ and wpk (λ) = a. The result follows.
To complete the proof of Theorem B, it will be convenient to split the remainder of this section
into two parts. In each part we will appropriately fix the natural numbers a and k according to
the statement of Theorem B.
5.1. Part I. In this first part, we consider the case k = 1 and a < p2 , and the case k ≥ 2.
Proposition 5.3. Let a ∈ {1, 2, . . . , p − 1} and let k ∈ N. If k = 1 and a <
br(apk ) = 2a.

p
2

or if k ≥ 2, then

Proof. From Proposition 5.2 we have that br(apk ) ≤ 2a. Hence it is enough to construct λ ⊢p′ apk
such that |λ−
p′ | = 2a. This is done as follows.
(i) First suppose that k = 1 and a < p2 . Let λ be the partition of ap defined by
λ = (p − 1, p − 2, . . . , p − a, a, a − 1, . . . , 2, 1).

The following diagram is the p-abacus configuration for λ having first gap in position (0, 0), where
we have indicated the row numbers on the left and the runner numbers above each column:
−1
0
1

0
×
◦
×

1
×
×
◦

2
×
◦
×

3
×
×
◦

···
···
···
···

2a − 2
×
◦
×

2a − 1
×
×
◦

2a
×
◦
◦

···
···
···
···

p−1
×
◦
◦

−
Since Cp (λ) = ∅ we have that λ ⊢p′ ap, by Theorem 2.7. Moreover, we observe that λ−
p′ = λ
by Lemma 2.5, and so |λ−
p′ | = 2a.
(ii) Suppose now that k ≥ 2. Let r = pk−1 − a > 0 and let λj = a + p − 2 + rp + (a − j)(p − 1) =
pk − (j − 1)(p − 1) − 1, for each j ∈ {1, 2, . . . , a}. Let λ be the partition of apk defined by

λ = λ1 , λ2 , . . . , λa , a, (a − 1)p−1 , (a − 2)p−1 , . . . , 2p−1 , 1p−1 .

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

13

The best way to verify that λ has the required properties is to look at it on James’ abacus. We
describe and depict below a p-abacus configuration A corresponding to λ:
- The first gap is in position (1, 0);
- Rows 1 ≤ i ≤ a − 1 have a gap only in position (i, 0);
- Row a has a bead only in position (a, 1);
- Rows a + 1 to a + r are all empty;
- Rows a + 1 + r ≤ i ≤ 2a + r have a bead only in position (i, 0);
- There is a gap in position (x, y) for all x > 2a + r.
1
..
.
a−1
a
a+1
..
.
a+r
a+1+r
..
.
2a + r

0
◦
..
.
◦
◦
◦
..
.
◦
×
..
.
×

1
×

2
×

···
···

×
×
◦

×
◦
◦

···
···
···

◦
◦

◦
◦

···
···

◦

◦

···

p−1
×
..
.
×
◦
◦
..
.
◦
◦
..
.
◦

From the structure of A we observe that Qp (λ) = (λ0 , ∅, . . . , ∅), where
λ0 = (pk−1 , . . . , pk−1 ).
|
{z
}
a times

From the discussion in Section 2.1 (or [10, Theorem 3.3]), we deduce that wpk (λ) = wpk−1 (λ0 ) = a
and Cpk (λ) = ∅. This shows that λ ⊢p′ apk , by Theorem 2.7.
Notice that λ has exactly 2a removable nodes, corresponding to the 2a removable beads in
A lying in positions (i, 1) and (a + r + i, 0) for i ∈ {1, . . . , a}. Let c be a removable bead in
position (i, 1) of A, for some i ∈ {1, . . . , a}. Then A←c corresponds to the partition µ ⊢ apk − 1
such that Cp (µ) = (p − 1) ⊢ p − 1 and Qp (µ) = (µ0 , µ1 , ∅, . . . , ∅), where
µ0 = (pk−1 − 1, . . . , pk−1 − 1, i − 1) and µ1 = (1a−i ).
{z
}
|
a times

1)pk−1

+ m, where m := pk−1 − a + (i − 1). This follows from
We observe that µ0 ⊢p′ (a −
Theorem 2.7, since wpk−1 (µ0 ) = a − 1 and Cpk−1 (µ0 ) = (m) ⊢p′ m. Moreover, we clearly have
that µ1 ⊢p′ a − i. We can now use Theorem 2.8 to deduce that µ ⊢p′ apk − 1 and therefore
µ ∈ λ−
p′ .
A similar argument shows that for every j ∈ {1, . . . , a} the p-abacus configuration A←d
obtained from A by sliding the bead d in position (a + r + j, 0) to position (a + r + j − 1, p − 1),
−
corresponds to a p′ -partition µ of apk − 1, that is, µ ∈ λ−

p′ . Thus |λp′ | = 2a.
Proposition 5.4. Let a ∈ {1, 2, . . . , p − 1} and let k ∈ N. If k = 1 and a <
Eapk = {1, 2, . . . br(apk )}.

p
2

or if k ≥ 2, then

Proof. From Proposition 5.3, we have that br(apk ) = 2a = max Eapk . Hence it is enough to
construct λ ⊢p′ apk such that |λ−
p′ | = m for each m ∈ {1, 2, . . . , 2a − 1}. This is done as follows.
(i) First suppose that k = 1 and a < 2p . We first exhibit λ(j) ⊢p′ ap such that |λ(j)−
p′ | = 2j, for
each j ∈ {1, 2, . . . , a − 1}:

14

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

- Let λ(1) = (ap − 1, 1);
- For each fixed j ∈ {2, . . . , a − 1}, let λ(j) = (λ1 , λ2 , . . . , λ2j ) where
◦ λ1 = (a − j + 1)p − 2j + 1,
◦ λx = p + 2 − x for x ∈ {2, . . . , j}, and
◦ λy = 2j + 1 − y for y ∈ {j + 1, . . . , 2j}.
For convenience, we depict the p-abacus of λ(j) having first gap in position (0, 0):
−1
0
1
2
..
.
a−j +1

0
×
◦
◦
◦
..
.
×

1
×
×
◦
◦

2
×
◦
×
◦

3
×
×
◦
◦

···
···
···
···
···

2j − 2
×
◦
×
◦

2j − 1
×
×
◦
◦

2j
×
◦
◦
◦

···
···
···
···
···

◦

◦

◦

···

◦

◦

◦

···

p−1
×
◦
◦
◦
..
.
◦

−
By Theorem 2.7, we have λ(j) ⊢p′ ap, and by Lemma 2.5, we have |λ(j)−
p′ | = |λ(j) | = 2j.
Hence {2, 4, . . . , 2a − 2} ⊆ Eap .
Next we exhibit β(j) ⊢p′ ap such that |β(j)−
p′ | = 2j − 1 for each j ∈ {1, 2, . . . , a}:

- Let β(1) = ((a − 1)p + 1, 1p−1 );
- Let β(a) = (2a − 1, 2a − 2, . . . , a + 1, ap−2a+2 , a − 1, . . . , 2, 1);
- For each fixed j ∈ {2, . . . , a − 1}, let β(j) = (β1 , . . . , βp ) where
◦ β1 = (a − j)p + 1,
◦ βx = 2j + 2 − x for x ∈ {2, . . . , j},
◦ βy = j for y ∈ {j + 1, . . . , p − j + 1}, and
◦ βz = p + 1 − z for z ∈ {p − j + 2, . . . , p}.
For convenience, we depict the p-abacus of β(j) having first gap in position (0, 0):
−1
0
1
2
..
.
a−j +1

0
×
◦
◦
◦
..
.
×

1
×
×
◦
◦

2
×
◦
×
◦

3
×
×
◦
◦

···
···
···
···
···

2j − 2
×
◦
×
◦

2j − 1
×
×
◦
◦

2j
×
×
◦
◦

···
···
···
···
···

◦

◦

◦

···

◦

◦

◦

···

p−1
×
×
◦
◦
..
.
◦

Again by Theorem 2.7 we have β(j) ⊢p′ ap. By Lemma 2.5, if j 6= a then |β(j)− | = 2j and
−
−
|β(j)− \ β(j)−
p′ | = 1, while if j = a then |β(j)p′ | = |β(j) | = 2a − 1. In both cases we have
|β(j)−
p′ | = 2j − 1, giving {1, 3, . . . , 2a − 1} ⊆ Eap . Thus Eap = {1, 2, . . . , 2a} as claimed.

(ii) Suppose now that k ≥ 2. We first construct a partition λ(j) ⊢p′ apk such that |λ(j)−
p′ | =
k−1
2a − j, for all j ∈ {1, 2, . . . , a − 1}. Let r = p
− a > 0 and let

p−1
λ(j) := ηa−1 , . . . , ηj , θj , . . . , θ1 , a, (a − 1) , . . . , (j + 1)p−1 , j p−2 , (j − 1)p−1 , . . . , 1p−1 ,

where θt = a + pr + t(p − 1) and ηt = θt + (p − 2), for any t ∈ {1, . . . , a − 1}. As usual, it is
useful to look at λ(j) on James’ abacus. We describe and depict below a p-abacus Aj of λ(j):
- The first gap is in position (1, 1);
- Rows 1 ≤ x ≤ j have a gap only in position (x, 1);
- Rows j + 1 ≤ x ≤ a − 1 have a gap only in position (x, 0);
- Row a has a bead only in position (a, 1);
- Rows a + 1 to a + r are all empty;
- Rows a + r + 1 ≤ x ≤ a + r + j have a bead only in position (x, 1);

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

15

- Rows a + r + j + 1 ≤ x ≤ 2a + r have a bead only in position (x, 0);
- There is a gap in position (x, y) for all x > 2a + r.
1
..
.
j
j+1
..
.
a−1
a
a+1
..
.
a+r
a+r+1
..
.
a+r+j
a+r+j+1
..
.
2a + r

0
×
..
.
×
◦
..
.
◦
◦
◦
..
.
◦
◦
..
.
◦
×
..
.
×

1
◦

2
×

···
···

◦
×

×
×

···
···

×
×
◦

×
◦
◦

···
···
···

◦
×

◦
◦

···
···

×
◦

◦
◦

···
···

◦

◦

···

p−1
×
..
.
×
×
..
.
×
◦
◦
..
.
◦
◦
..
.
◦
◦
..
.
◦

Since j is fixed, we will denote λ(j) by λ and Aj by A from now on. Arguing as in the
proof of Proposition 5.3, we deduce that λ ⊢p′ apk . Moreover, it is clear that |λ− | = 2a. Let
x ∈ {1, . . . j} and let c be the bead lying in position (x, 2) of A. Let µx be the partition of
apk − 1 corresponding to the p-abacus A←c . Then Cp (µx ) = (p, 1p−1 ). Therefore µx is not a
p′ -partition, by Theorem 2.8. It follows that |λ−
p′ | ≤ 2a − j.
We will now show that all of the other 2a− j removable beads in A correspond to p′ -partitions
of apk − 1. Let x ∈ {j + 1, j + 2, . . . , a} and let c be the bead in position (x, 1) of A. Let µx be
the partition of apk − 1 corresponding to the p-abacus A←c . Then Cp (µx ) = (p − 1) ⊢p′ p − 1
and Qp (µx ) = (µ0 , µ1 , ∅, . . . , ∅), where


µ0 = (pk−1 − 1)a−j , x − j − 1 and µ1 = (r + j + 1)j , (j + 1)a−x , j x−j−1 .

By Theorem 2.7, we have that µ0 ⊢p′ |µ0 | and µ1 ⊢p′ |µ1 |, where
|µ0 | = (a − j − 1)pk−1 + (p − 1)
and

k−2
X
i=1

pi + [(p − 1) − (a − x)]

|µ1 | = jpk−1 + (a − x).
This implies µx ⊢p′ apk − 1, by Theorem 2.8.
Now let c be the bead in position (a + r + x, 1) for some x ∈ {1, . . . , j}, and let µx be the
partition corresponding to the p-abacus A←c . Arguing as before, we deduce from Theorem 2.8
that µx ⊢p′ apk − 1.
Finally, let c be the bead in position (a + r + x, 0) for some x ∈ {j + 1, . . . , a} and let µx be the
partition corresponding to A←c . First, we observe that Cp (µx ) = (p − 2, 1) ⊢p′ p − 1. Moreover,
Qp (µx ) = (µ0 , µ1 , ∅, . . . , ∅, µp−1 ), where


µ0 = (pk−1 + 1)a−x , (pk−1 )x−j−1 , µ1 = (r + j)j , j a−j , and µp−1 = (r + x − 1).

16

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

Again, we use Theorem 2.8 to deduce that µx ⊢p′ apk − 1. Thus |λ−
p′ | = 2a − j, as desired, and
so {a + 1, a + 2, . . . , 2a − 1} ⊆ Eapk .

Finally, we construct a partition β(j) ⊢p′ apk such that |β(j)−
p′ | = a−j, for all j ∈ {0, 1, . . . , a−
j
1}. Let B be the p-abacus configuration obtained from the p-abacus Aj described above by
removing the bead in position (a, 1) so that row a is now empty. Let β(j) be the partition of
apk corresponding to the p-abacus B j . Again, since j is fixed we will now denote B j by B and
β(j) by β.
It is clear that β ⊢p′ apk and that |β − | = 2a − j − 1. Moreover, if c is one of the a − 1
removable beads lying on runner 1 of B and µ is the partition of apk − 1 corresponding to the
p-abacus B ←c , then Cp (µ) = (p, 1p−1 ) and therefore µ is not a p′ -partition, by Theorem 2.8.
Hence |βp−′ | ≤ a − j. Arguing as before, the partition corresponding to the p-abacus B ←c for any
removable bead c lying on runner 0 of B is a p′ -partition of apk − 1. Hence |βp−′ | = a − j, and so
{1, 2, . . . , a} ⊆ Eapk . Thus Eapk = {1, 2, . . . , 2a} as claimed.


5.2. Part II. In this second part of Section 5, we fix k = 1 and a ∈ N such that
The main aim in Part II is to prove the following fact.
Proposition 5.5. Let a ∈ N be such that

p
2

p
2

< a < p.

< a < p. Then br(ap) = p − 1 + 2⌊ 2a−(p−1)
⌋.
6

The proof of Proposition 5.5 is split into a series of technical lemmas. We start by fixing some
notation which will be kept throughout Part II.
Notation 5.6. Let a ∈ N be such that p2 < a < p. We let x := a − p−1
2 , and we write x = 3q + δ
x
⌋.
for some q ∈ N0 and δ ∈ {0, 1, 2}. In particular we have q = ⌊ 3 ⌋ = ⌊ 2a−(p−1)
6
Definition 5.7. Denote by A∅ the p-abacus configuration for the empty partition ∅, such that
A∅ has first gap in position (0, 0). We then define Z(a) to be the set of p-abaci B such that
w(B) = a and B ↑ = A∅ . It is clear by Theorem 2.7 that Z(a) is naturally in bijection with
Irrp′ (Sap ).
Lemma 5.8. Let λ ⊢p′ ap and let B ∈ Z(a) be the p-abacus corresponding to λ. Then
|λ−
p′ |

=

p−1
X

Rem(Bi )

and

br(ap) = max

i=1

B∈Z(a)

p−1
X

Rem(Bi ).

i=1

Proof. The statement follows directly from Lemma 2.5 and Theorem 2.7.
Lemma 5.9. For a ∈ N such that

p
2



< a < p, we have br(ap) ≥ p − 1 + 2q.

Proof. We exhibit a partition β ⊢p′ ap such that |βp−′ | = p − 1 + 2q. If δ = 0 then let β be the
following partition of ap:
(p + 2q, p + 2q − 1, . . . , p + q + 1, p + q − 1, . . . , q + 1, q p−2q+1 , q − 1, . . . , 2, 1),

while if δ 6= 0 then let β be the following partition of ap:


p(δ + 1) + 2, p + 2q + 1, p + 2q, . . . , p + q + 3, p + q − 1, . . . , q + 1, q p−2q+1 , q − 1, . . . , 1 .

We describe and depict below a p-abacus Bβ ∈ Z(a) of β:
- For j ∈ {0, 2, . . . , p − 3, p − 1}, runner j has beads in positions (x, j), for all x ≤ −1;
- Runner 1 has beads in positions (0, 1), (1 + δ, 1) and (y, 1) for all y ≤ −3;
- For j ∈ {3, 5, . . . , 2q − 1}, runner j has beads in positions (0, j), (1, j) and (y, j) for all y ≤ −3;
- For j ∈ {2q + 1, 2q + 3, . . . , p − 2} runner j has beads in positions (0, j) and (y, j) for all ≤ −2.

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

−3
−2
−1
Bβ : 0
1
2
..
.
1+δ

0
×
×
×
◦
◦
◦
..
.
◦

17

1
×
◦
◦
×
◦
◦

2
×
×
×
◦
◦
◦

3
×
◦
◦
×
×
◦

4
×
×
×
◦
◦
◦

···
···
···
···
···
···
···

2q − 2
×
×
×
◦
◦
◦

2q − 1
×
◦
◦
×
×
◦

2q
×
×
×
◦
◦
◦

2q + 1
×
×
◦
×
◦
◦

2q + 2
×
×
×
◦
◦
◦

···
···
···
···
···
···
···

p−3
×
×
×
◦
◦
◦

p−2
×
×
◦
×
◦
◦

×

◦

◦

◦

···

◦

◦

◦

◦

◦

···

◦

◦

p−1
×
×
×
◦
◦
◦
..
.
◦

We observe from the above abacus configuration that Cp (β) = ∅, and hence by Theorem 2.7
we have that β ⊢p′ ap. Moreover by Lemma 5.8, we have β − = βp−′ . Hence br(ap) ≥ |βp−′ | =
p − 1 + 2q.


Thus it remains to show that for all λ ⊢p′ ap, we have |λ−
p′ | ≤ p − 1 + 2q. In order to do this
we introduce a new combinatorial object.

Definition 5.10. Let T∅ be the 2-abacus configuration for the empty partition ∅ having first
gap in position (0, 0). Let U (0) , U (1) . . . , U (p−1) be 2-abaci such that (U (i) )↑ = T∅ for all i ∈
{0, 1, . . . , p − 1}. If w(U (0) ) + w(U (1) ) + · · · + w(U (p−1) ) = w ∈ N0 then we call the sequence
U = (U (0) , U (1) , . . . , U (p−1) ) a doubled p-abacus of weight w (we write w(U ) = w in this case).
Moreover we denote by D(w) the set of doubled p-abaci
of weight w.

Finally, given any w ∈ N0 we let M (w) = max ρ(U ) | U ∈ D(w) , where for any U ∈ D(w)
we define ρ(U ) as
p−1
X
(i)
ρ(U ) =
Rem(U1 ).
i=1

As usual, we denoted by

(i)
U0

(and

(i)
U1 )

the left (and right) runner of the 2-abacus U (i) .

Remark 5.11. Let λ ⊢p′ ap and let B ∈ Z(a) correspond to λ. For i ∈ {1, . . . , p − 1}, let
U (i) = (Bi−1 , Bi ), and let U (0) = (Bp−1 , B0 ). Then U := (U (0) , U (1) , . . . , U (p−1) ) ∈ D(2a) and
ρ(U ) = |λ−
p′ |, by Lemma 5.8. With this in mind we define D(Z(a)) to be the subset of D(2a)
(i)

(i−1)

for all i ∈ {0, 1, . . . , p − 1}
of sequences U := (U (0) , U (1) , . . . , U (p−1) ) such that U0 = U1
(here two runners are equal if they coincide as 1-abaci; that is, they have beads in exactly the
same rows). Clearly the set D(Z(a)) is naturally in bijection with Z(a), via the construction
described above.
Lemma 5.12. Let a and x be as in Notation 5.6. Then br(ap) ≤ M (2a) = p − 1 + ⌊ 2x
3 ⌋.

Proof. From Remark 5.11 it is immediate that br(ap) ≤ M (2a), so it remains to prove M (2a) =
p − 1 + ⌊ 2x
3 ⌋.
Let U = (U (0) , U (1) , . . . , U (p−1) ) ∈ D(2a) be such that ρ(U ) = M (2a). Let wi = w(U (i) ).
Clearly w1 + w2 + · · · wp−1 ≤ 2a. Moreover, arguing as in the proof of Lemma 3.10 we can
(i)
(i)
assume that w(U1 ) = wi and w(U0 ) = 0 for all i ∈ {1, . . . , p − 1}. From the maximality of
ρ(U ) we deduce using Lemma 3.10 (in the case λ = ∅) that
√
(i)
Rem(U1 ) = ⌊ wi ⌋
and hence

)
( p−1
X p
⌊ bi ⌋ b1 + · · · + bp−1 ≤ 2a and bi ∈ N0 ∀ 1 ≤ i ≤ p − 1 .
M (2a) = max
i=1

18

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

P
P √
Let b = (b1 , . . . , bp−1 ) be such that bi ∈ N0 for all i, i bi ≤ 2a and i ⌊ bi ⌋ = M (2a); we will
call any (p − 1)-tuple satisfying these conditions maximal.
If there exists i such that bi ≥ 9, then
P
there exists j such that bj ≤ 1. This follows since
bi ≤ 2a < 2p. Replacing bi by b′i = bi − 4
and bj by b′j = bj + 4 in b we obtain a new maximal sequence b′ . Hence we may assume without
loss of generality that our maximal sequence b has bi ≤ 8 for all i ∈ {1, . . . , p − 1}.
Now if there exists i such that bi = 0 then there exists j such that bj ≥ 2, because 2a > p.
In this case, replacing bi by b′i = 1 and b′j = bj − 1 in b we obtain a new maximal sequence b′ .
Hence we may further assume that b has bi ≥ 1 for all i ∈ {1, . . . , p − 1}. The observations above
show that without loss of generality we may assume
p
p
p
p
⌊ b1 ⌋ = · · · = ⌊ bt ⌋ = 2, ⌊ bt+1 ⌋ = · · · = ⌊ bp−1 ⌋ = 1,
for some t ∈ {0, . . . , p − 1}.
In particular, bi ∈ {4,
P. . . , 8} for i ∈ {1, . . . , t} and bj ∈ {1, 2, 3} for j ∈ {t + 1, . . . , p − 1}.
Thus 4t + (p − 1 − t) ≤ bi ≤ 2a, which gives t ≤ ⌊ 2x
3 ⌋ since t is an integer. This in turn implies
2x
that M (2a) = 2t + (p − 1 − t) ≤ p − 1 + ⌊ 3 ⌋.
Finally, equality holds because we can construct U ∈ D(2a) such that w(U (1) ) = · · · =
w(U (t) ) = 4, w(U (t+1) ) = · · · = w(U (p−1) ) = 1 and w(U (0) ) = 2a − 3t − (p − 1), where t = ⌊ 2x
3 ⌋,
(j)

(j)

with Rem(U1 ) = 2 for j ∈ {1, . . . , t} and Rem(U1 ) = 1 for j ∈ {t + 1, . . . , p − 1}.



Lemmas 5.9 and 5.12 show that p−1+2⌊ x3 ⌋ ≤ br(ap) ≤ p−1+⌊ 2x
3 ⌋. In particular if δ 6= 2 then
2x
2δ
x
we have that ⌊ 3 ⌋ = 2q + ⌊ 3 ⌋ = 2q = 2⌊ 3 ⌋. In this case we have br(ap) = M (2a) = p − 1 + 2q.
To deal with the remaining case of δ = 2 where p − 1 + 2q ≤ br(ap) ≤ M (2a) = p − 1 + 2q + 1,
we have the following lemma.
Lemma 5.13. Let a ∈ N be as in Notation 5.6 and suppose that δ = 2. Then br(ap) ≤ M (2a)−1.
Proof. From Remark 5.11 it is enough to show that if U ∈ D(2a) and ρ(U ) = M (2a), then
U∈
/ D(Z(a)). To do this we will show that if ρ(U ) = M (2a) then there exists i ∈ {0, 1, . . . , p−1},
(i)
(i−1)
such that U0 6= U1
.
For i ∈ {0, 1, . . . , p − 1}, let bi = w(U (i) ). Arguing as in the proof of Lemma 5.12 we
√
P
see that ρ(U ) = p−1
i=1 ⌊ bi ⌋. Moreover, given any composition w = (w1 , . . . , wp−1 ) such that
w1 + · · · + wp−1 ≤ 2a there exists V ∈ D(2a) such that w(V i ) = wi for all i ∈ {1, . . . , p − 1},
P
√
w(V 0 ) = 2a − (w1 + · · · + wp−1 ) and such that ρ(V ) = p−1
i=1 ⌊ wi ⌋.
Let b = (b1 , . . . , bp−1 ) and suppose that bi ≥ 9, for some i ∈ {1, . . . p − 1}.
- If there exists j such that bj = 0, then replacing (bi , bj ) by (b′i , b′j ) := (bi − 4, 4) in b we
P
√
obtain a new composition b′ such that p−1
i=1 ⌊ wi ⌋ > ρ(U ). This clearly contradicts the
maximality of ρ(U ).
- If bi ≥ 10, then there exists j 6= l such that bj = bl = 1 since a < p. But then we may
replace (bi , bj , bl ) by (bi − 6, 4, 4) in b to obtain a similar contradiction as before.
- If there exists i′ 6= i such that bi′ ≥ 9, then as above we deduce that bi′ = 9. In particular,
2a ≥ 18 so p > 3. Since a < p, there exist distinct j, j ′ , j ′′ such that bj = bj ′ = bj ′′ = 1.
But then we may replace (9, 9, 1, 1, 1) by (5, 4, 4, 4, 4) in b to obtain a contradiction.
The above observations show that if bi = 9 for somepi ∈ {1, . . . , p − 1} then there exists t ∈
{0, 1, . . . , p − 2} such that b has t parts satisfying ⌊ bj ⌋ = 2 and p − 2 − t parts satisfying
p
⌊ bj ⌋ = 1. Hence M (2a) = 3 + 2t + (p − 2 − t) = p − 1 + ⌊ 2x
3 ⌋ = p − 1 + 2q + 1, so t = 2q − 1.

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

19

But this implies that
2a ≥

p−1
X

m=1

bm ≥ 9 + 4t + (p − 2 − t) = p − 1 + 6q + 5.

√
Therefore we have 6q + 5 ≤ 2a − (p − 1) = 2x = 6q + 4, a contradiction. Thus, ⌊ bi ⌋ ∈ {0, 1, 2}
for each i ∈ {1, . . . , p − 1}.
√
So suppose there are t values of i for which ⌊ bi ⌋ = 2, s values for which it is 1, and p−1−s−t
values for which it is 0. Then
p + 2q = M (2a) = 2t + s ≤ p − 1 + t,
√
so t ≥ 2q + 1. In particular t ≥ 1, so there exists i with ⌊ bi ⌋ = 2. If there exists j 6= l such
that bj = bl = 0, then we may replace (bi , bj , bl ) by (bi − 2, 1, 1) in b to obtain a contradiction to
the maximality of ρ(U ). So there is at most one bj = 0 and thus s + t ∈ {p − 2, p − 1}.
If s + t = p − 2, then p + 2q = M (2a) = 2t + s implies t = 2q + 2, and so
6q + 4 − b0 = 2x − b0 =

p−1
X

m=1

bm − (p − 1) ≥ 4t + s − (p − 1) = 6q + 5,

which is a contradiction. Thus s + t = p − 1 and t = 2q + 1. Since
6q + 4 − b0 =

p−1
X

m=1

bm − (p − 1) ≥ 4t + s − (p − 1) = 6q + 3,

one of the following must hold:
(i) |{i : bi = 4}| = t, |{i : bi = 1}| = s and b0 = 1; or
(ii) |{i : bi = 4}| = t − 1, |{i : bi = 5}| = 1, |{i : bi = 1}| = s and b0 = 0; or
(iii) |{i : bi = 4}| = t, |{i : bi = 2}| = 1, |{i : bi = 1}| = s − 1 and b0 = 0.
Now, suppose for a contradiction that U ∈ D(Z(a)). Then we have that the bead configura(i−1)
(i)
tions on U1
and U0 are equal for all j; call this property (⋆). The key in the following will
be that t = |{i : bi ≥ 4}| = 2q + 1 is odd.
(i)
(i)
In case (i), let i ∈ {1, . . . , p − 1} be such that bi = 4. Then (w(U0 ), w(U1 )) = (j, 4 − j)
for some 0 ≤ j ≤ 4. If j = 2 then (⋆) would imply bi+1 ≥ 2, and hence bi+1 = 4. Moreover it
(i+1)
(i+1)
(y)
also forces w(U0
) = w(U1
) = 2. We can iterate this argument to deduce that w(U0 ) =
(y)
w(U1 ) = 2 for all y ∈ {0, 1, . . . , p − 1}, which gives a contradiction. Thus j ∈ {0, 1, 3, 4}.
(i)
(i+1)
If j = 0, then w(U1 ) = 4, so (⋆) implies that w(U0
) = 4 and hence bi+1 = 4 also.
(i+1)
Similarly if j = 1, then w(U0
) = 3 and hence bi+1 = 4. On the other hand, if j = 3 or j = 4
then similarly we deduce that bi−1 = 4. These observations imply that t is an even natural
number (because if j ∈ {0, 1} then we may pair off i and i + 1 where bi = bi+1 = 4, and if
j ∈ {3, 4} then we may pair off i and i − 1 where bi = bi−1 = 4). This gives a contradiction, and
/ D(Z(a)), as desired. The analyses of cases (ii) and (iii) are similar.

so U ∈

Thus when δ = 2 we also have that br(ap) = p − 1 + 2⌊ x3 ⌋, by Lemmas 5.9, Lemma 5.12
and 5.13. This proves Proposition 5.5.
Proof of Theorem B. This follows directly from Propositions 5.1, 5.3 and 5.5.
We devote the final part of this section to the description of the set Eap for any
Proposition 5.14. Let a ∈ N be such that

p
2


p
2

< a < p.

< a < p. Then Eap = {1, 2, . . . , br(ap)}.

20

EUGENIO GIANNELLI, STACEY LAW, AND STUART MARTIN

Proof. Let β ⊢p′ ap with p-abacus configuration B := Bβ be as defined in Lemma 5.9. In
particular we proved that |βp−′ | = br(ap) = p − 1 + 2q, with notation as in Notation 5.6.
Denote by b the bead in position (1 + δ, 1) of B. For i ∈ {1, 2, . . . , p−1
2 } let ci be the bead
in position (0, p − 2i) of B and let B(i) be the p-abacus configuration obtained from B by
sliding b down to position (1 + δ + i, 1) and by sliding cj up to position (−1, p − 2j) for all
j ∈ {1, . . . , i}. Let µ(i) ⊢ ap be the partition corresponding to the p-abacus configuration B(i).
−
From Theorem 2.7 we have that µ(i) ⊢p′ ap and |µ(i)−
p′ | = |βp′ | − 2i. It follows that
{2q, 2q + 2, · · · , br(ap) − 2, br(ap)} ⊆ Eap .

Now let A := B( p−1
2 ). For i ∈ {1, 2, . . . , q − 1} let A(i) be the p-abacus configuration obtained
p−1
from A by sliding down bead b from position (1 + δ + p−1
2 , 1) to position (1 + δ + 2 + 3i, 1)
↑
and by replacing runner A2j+1 with A2j+1 for all j ∈ {1, . . . , i}. (For convenience, this step is
depicted below.)
−2
−1
0
1

2j
×
×
◦
◦

2j + 1
◦
×
◦
×

2j + 2
×
×
◦
◦

−→

−2
−1
0
1

2j
×
×
◦
◦

2j + 1
×
×
◦
◦

2j + 2
×
×
◦
◦

Let ν(i) ⊢ ap be the partition corresponding to the p-abacus configuration A(i). Since
w(A2i+1 ) = 3 for all i ∈ {1, 2, . . . , q − 1}, it follows from Theorem 2.7 that ν(i) ⊢p′ ap
p−1 −
and |ν(i)−
p′ | = |µ( 2 )p′ | − 2i. Thus {2, 4, 6, · · · , 2q − 2} ⊆ Eap , and so it remains to show
{1, 3, . . . , br(ap) − 1} ⊆ Eap .

First suppose q ≥ 1. Consider the p-abacus configuration C obtained from B by sliding down
the bead in position (−1, 0) to position (0, 0) and by sliding up the bead in position (0, 1) to
position (−1, 1).
Let γ be the partition corresponding to C. It is easy to see that γ ⊢p′ ap and that |γp−′ | =
br(ap) − 1. We can now repeat the strategy used above to see that {3, 5, . . . , br(ap) − 1} ⊆ Eap .
Of course, 1 ∈ Eap by considering the trivial partition (ap) ⊢p′ ap.
If q = 0 we begin with the p-abacus configuration C ′ obtained from B by swapping runners
0 and 1, instead of C. The same argument then shows {1, 3, . . . , br(ap) − 1} ⊆ Eap .

We conclude by observing that Propositions 5.1, 5.4 and 5.14 together prove Theorem 3.13.
Acknowledgments. We thank Jason Long for suggesting Definition 5.10 and for many useful
conversations on this topic.
References
[1] A. Ayyer, A. Prasad, and S. Spallone, Odd partitions in Young’s lattice. Sémin. Lothar. Comb. 75
(2016), Article B75g.
[2] C. Bessenrodt, E. Giannelli, and J. Olsson,
Restriction of odd degree characters of Sn .
arXiv:1705.08655 [math.RT]
[3] E. Giannelli, A. Kleshchev, G. Navarro and P. H. Tiep, Restriction of odd degree characters and
natural correspondences. Int. Math. Res. Not. (2016) no. 00, 1–30.
[4] M. Isaacs, G. Navarro, J. Olsson and P.H. Tiep, Characters restriction and multiplicities in symmetric
groups. J. Algebra 478 (2017), 271282.
[5] G. James, The representation theory of the symmetric groups, Lecture Notes in Mathematics, vol. 682,
Springer, Berlin, 1978.
[6] G. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, Mass., 1981.

ON THE p′ -SUBGRAPH OF THE YOUNG GRAPH

21

[7] A. Kleshchev, Linear and projective representations of symmetric groups, Cambridge Tracts in Mathematics, 163. Cambridge University Press, Cambridge, 2005.
[8] I. G. Macdonald, On the degrees of the irreducible representations of symmetric groups, Bull. London
Math. Soc. 3 1971 189192.
[9] A. Okounkov and A. Vershik A new approach to representation theory of symmetric groups, Selecta
Math. (N.S.) 2 (1996), 581-605.
[10] J. Olsson, Combinatorics and Representations of Finite Groups, Vorlesungen aus dem Facherbeich
Mathematik der Universitat Essen, Heft 20, 1994.
(E. Giannelli) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WA, UK
E-mail address: eg513@cam.ac.uk
(S. Law) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WA, UK
E-mail address: swcl2@cam.ac.uk
(S. Martin) Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WA, UK
E-mail address: sm137@cam.ac.uk

