R-S correspondence for the Hyper-octahedral group of type Bn - A different approach
In this paper we develop a Robinson Schensted algorithm for the hyperoctahedral group of type Bn on partitions of ( 1 2 r(r + 1) + 2n) whose 2−core is δr, r ≥ 0 where δr is the partition with parts (r, r−1, . . . , 0). We derive some combinatorial properties associated with this correspondenc...
Gespeichert in:
| Datum: | 2007 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2007
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/157345 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | R-S correspondence for the Hyper-octahedral group of type Bn - A different approach / M. Parvathi, B. Sivakumar, A. Tamilselvi // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 1. — С. 86–107. — Бібліогр.: 15 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157345 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1573452019-06-21T01:30:06Z R-S correspondence for the Hyper-octahedral group of type Bn - A different approach Parvathi, M. Sivakumar, B. Tamilselvi, A. In this paper we develop a Robinson Schensted algorithm for the hyperoctahedral group of type Bn on partitions of ( 1 2 r(r + 1) + 2n) whose 2−core is δr, r ≥ 0 where δr is the partition with parts (r, r−1, . . . , 0). We derive some combinatorial properties associated with this correspondence. 2007 Article R-S correspondence for the Hyper-octahedral group of type Bn - A different approach / M. Parvathi, B. Sivakumar, A. Tamilselvi // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 1. — С. 86–107. — Бібліогр.: 15 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 05E10, 20C30 http://dspace.nbuv.gov.ua/handle/123456789/157345 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper we develop a Robinson Schensted
algorithm for the hyperoctahedral group of type Bn on partitions
of (
1
2
r(r + 1) + 2n) whose 2−core is δr, r ≥ 0 where δr is the
partition with parts (r, r−1, . . . , 0). We derive some combinatorial
properties associated with this correspondence. |
| format |
Article |
| author |
Parvathi, M. Sivakumar, B. Tamilselvi, A. |
| spellingShingle |
Parvathi, M. Sivakumar, B. Tamilselvi, A. R-S correspondence for the Hyper-octahedral group of type Bn - A different approach Algebra and Discrete Mathematics |
| author_facet |
Parvathi, M. Sivakumar, B. Tamilselvi, A. |
| author_sort |
Parvathi, M. |
| title |
R-S correspondence for the Hyper-octahedral group of type Bn - A different approach |
| title_short |
R-S correspondence for the Hyper-octahedral group of type Bn - A different approach |
| title_full |
R-S correspondence for the Hyper-octahedral group of type Bn - A different approach |
| title_fullStr |
R-S correspondence for the Hyper-octahedral group of type Bn - A different approach |
| title_full_unstemmed |
R-S correspondence for the Hyper-octahedral group of type Bn - A different approach |
| title_sort |
r-s correspondence for the hyper-octahedral group of type bn - a different approach |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2007 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157345 |
| citation_txt |
R-S correspondence for the Hyper-octahedral group of type Bn - A different approach / M. Parvathi, B. Sivakumar, A. Tamilselvi // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 1. — С. 86–107. — Бібліогр.: 15 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT parvathim rscorrespondenceforthehyperoctahedralgroupoftypebnadifferentapproach AT sivakumarb rscorrespondenceforthehyperoctahedralgroupoftypebnadifferentapproach AT tamilselvia rscorrespondenceforthehyperoctahedralgroupoftypebnadifferentapproach |
| first_indexed |
2025-07-14T09:47:25Z |
| last_indexed |
2025-07-14T09:47:25Z |
| _version_ |
1837615227388035072 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2007). pp. 86 – 107
c© Journal “Algebra and Discrete Mathematics”
R-S correspondence for the Hyper-octahedral
group of type Bn — A different approach
M. Parvathi, B. Sivakumar1 and A. Tamilselvi
Communicated by R. Wisbauer
Abstract. In this paper we develop a Robinson Schensted
algorithm for the hyperoctahedral group of type Bn on partitions
of ( 1
2
r(r + 1) + 2n) whose 2−core is δr, r ≥ 0 where δr is the
partition with parts (r, r−1, . . . , 0). We derive some combinatorial
properties associated with this correspondence.
1. Introduction
The group algebra of the hyperoctahedral group S̃n is a subalgebra of the
signed Brauer algebra. In the process of constructing a cellular basis for
the signed Brauer algebra [18,19], we constructed a R-S correspondence
for the hyperoctahedral group. We distinguish between a positive image
and a negative image of the signed permutation by a positive domino
(
* *
)
and a negative domino
(
*
*
)
respectively. The process of
insertion described is independent of the core of the partition into which
the dominoes are inserted. The positive dominoes are inserted along
rows and negative dominoes inserted along columns. We give a different
approach for the R-S correspondence by following closely the procedure
of insertion and placement of the dominoes as that in the case of the
symmetric group.
The irreducible modules of the hyper-octahedral group of type Bn
S̃n are indexed by partitions of 2n + 1 whose 2−core is one [12]. There
1The author was supported by CSIR-SRF while working on the paper.
2000 Mathematics Subject Classification: 05E10, 20C30.
Key words and phrases: Robinson Schensted correspondence, Hyperoctahedral
group of type Bn, Domino tableau.
M. Parvathi, B. Sivakumar, A. Tamilselvi 87
is a natural bijection between partitions of 2n + 1 whose 2−core is one
and partitions of (1
2r(r + 1) + 2n) whose 2−core is δr, r ≥ 0 where δr
is the partition with parts (r, r − 1, . . . , 0). In this paper we develop
the Robinson-Schensted algorithm for the hyper-octahedral group which
gives a correspondence between elements of the hyper-octahedral group
and pairs of standard tableaux of shape λ, as λ varies over partitions of
(1
2r(r + 1) + 2n), whose 2−core is δr, r ≥ 0. The insertion process is
independent of the core. We study the growth and local rules for the
R-S correspondence. We also study the Knuth relation for the hyper-
octahedral group of type Bn as in the case of the symmetric group.
2. Preliminaries
2.1. R-S Correspondence for the Hyper-octahedral group of
type Bn
In a 1982 paper Barbasch and Vogan [1] describe an insertion algorithm
which identifies the hyperoctahedral permutations with domino tableau.
They define this insertion using left-right insertion of a word and its
negative, followed by a jeu de taquin that pairs up i and -i.
Subsequently Garfinkle [5] defined this insertion directly, both
through a bumping algorithm and recursively in a manner similar to
that used by Fomin [4]. Van Leeuwen [15] also describes this algorithm
by translating Garfinkle’s recursive definition into Fomin’s language of
shapes. He provides the first proof that the Garfinkle algorithm is the
same as the Barbasch Vogan algorithm. He also defines insertion in the
presence of a non empty 2-core.
Shimozono and White [14] described a semistandard generalization of
Barbasch Vogan’s domino insertion relating domino insertion to Haiman’s
mixed insertion.
The domino insertion given in this paper is such that it corresponds
to the left cells of the modified Lusztig basis given in [6] . The algorithm
is based on R-S correspondence for the symmetric group without splitting
the diagram. We differ from the domino insertion given by Shimozono
and White [14] in the sense that their construction involves splitting
the tableau into two parts and successively attaching the dominos in a
recursive manner to get the final shape while we use a process successive
sliding of the dominos without splitting the tableau till the final shape is
arrived at.
Definition 2.1.1. [9]. For an integer n ≥ 2, the hyper-octahedral group
88 R-S correspondence
of type Bn, denoted by S̃n is defined to be subgroup of S2n such that
S̃n = {θ ∈ S2n|θ(i) + θ(−i) = 0,∀i, 1 ≤ i ≤ n}.
Definition 2.1.2. [3]. A sequence of non-negative integers λ = (λ1, λ2, . . .)
is called a partition of n, which is denoted by λ ⊢ n, if
1. λi ≥ λi+1, for every i ≥ 1
2.
∞∑
i=1
λi = n
The λi are called the parts of λ.
Definition 2.1.3. [3]. Suppose λ = (λ1, λ2, . . . , λl) ⊢ n. The Young
diagram of λ is an array of n dots having l left justified rows with row i
containing λi dots for 1 ≤ i ≤ l.
Example:
[λ] :=
∗ ∗ · · · ∗ λ1 nodes
∗ ∗ · · ∗ λ2 nodes
· · ·
· · ·
· · ·
∗ ∗ · · · ∗ λr nodes
Definition 2.1.4.[[8], §2]. Let α be a partition of n, denoted by α ⊢ n.
Then the (i, j)-hook of α, denoted by Hα
i,j which is defined to be a Γ-
shaped subset of diagram α which consists of the (i, j)-node called the
corner of the hook and all the nodes to the right of it in the same row
together with all the nodes lower down and in the same column as the
corner.
The number hij of nodes of Hα
ij i.e.,
hij = αi − j + α′
j − i + 1
where α′
j = number of nodes in the jth column of α, is called the length of
Hα
i,j , where α = [α1, · · ·αk]. A hook of length q is called a q-hook. Then
H[α] = (hij) is called the hook graph of α.
Definition 2.1.5.[[8], §2]. A hook of length two will be called a 2-hook.
Definition 2.1.6.[13]. We shall call the (i, j) node of λ, as r-node if and
only if j − i ≡ r(mod2).
M. Parvathi, B. Sivakumar, A. Tamilselvi 89
Definition 2.1.7.[13]. A node (i, j) is said to be a (2, r) node if hij = 2m
and the residue of node (i, λi) in λ is r. i.e. λi − i ≡ r(mod2).
Theorem 2.1.8.[13]. If we delete all the elements in the hook graph
H[λ] not divisible by 2, then the remaining elements,
hij = hr
ij(2), (r = 0, 1)
can be divided into disjoint sets whose (2, r) nodes constitute the diagram
[λ]r2, (r = 0, 1) with hook graph (hr
ij). The λ is written as (λ1, λ2) where
the nodes in λ1 correspond to (2, 0) nodes and the nodes in λ2 correspond
to (2, 1) nodes.
Definition 2.1.9.[[8], §2]. Let [λ] ⊢ n. An (i, j)-node of [λ] is said to be
a rim node if there does not exist any (i + 1, j + 1)-node of [λ].
Definition 2.1.10.[[8], §2]. A 2-hook comprising of rim nodes is called
a rim 2-hook.
Definition 2.1.11.[[8], §2]. Diagrams [λ] which do not contain any 2-
hook are called 2-cores.
Definition 2.1.12.[8] Each 2× 1 and 1× 2 rectangular boxes consisting
of two nodes is called as a domino.
Definition 2.1.13.[8] Let λ, µ be partitions of n. Then the dominance
order D is defined as λ D µ if
j∑
i=1
λi ≥
j∑
i=1
µi, ∀j.
Definition 2.1.14.[8] Let (λ, µ) and (α, β) be bipartitions of n where
λ ⊢ l, µ ⊢ m, l + m = n and α ⊢ r, β ⊢ s, r + s = n. Then we write
(λ, µ) D (α, β) if
j∑
i=1
λi ≥
j∑
i=1
αi, ∀j and |λ|+
j∑
i=1
µi ≥ |α|+
j∑
i=1
βi, ∀j
Definition 2.1.15. [[2],§3.7.] Let S′
n = Sn ∪ {t1, t2, . . . , tn}. Then
the extended left descent set of w ∈ S̃n is defined by L′(w) := {u ∈
S′
n|l(uw) < l(w)} = {u ∈ S′
n|uw < w}.
Let x, y ∈ S̃n and s ∈
∑
n = Sn − {t}, then we define
x
s
−→L y
def
⇐⇒ y = sx, l(y) > l(x) and L′(x) * L′(y),
90 R-S correspondence
and we write x
s
←→L y if x
s
−→L y or y
s
−→L x.
Finally, we write x←→L y if there exists a sequence x = x1, x2, . . . , xk =
y and si ∈
∑
n such that xi
s
←→L xi+1 for all i.
3. R-S correspondence for the Hyperoctahedral group of
type Bn - a different approach
We define a R-S correspondence for the hyperoctahedral group of type
Bn on partitions of (1
2r(r + 1) + 2n) whose 2-core is δr( where δr is the
partition (r, r − 1, r − 2, ..., 2, 1, 0))
Definition 3.1.1. A domino in which both the nodes are filled with
same number from the set A = {1, 2, · · ·n} is defined as a tablet. i.e.,
x x ,
x
x
, x ∈ A.
Notation 3.1.2. A partition λ of (1
2r(r + 1) + 2n) whose 2−core is
δr, r ≥ 0 where δr is the partition with parts (r, r − 1, . . . , 0) is denoted
by λ ⊢a (1
2r(r + 1) + 2n).
Definition 3.1.3. Given λ ⊢a (1
2r(r + 1) + 2n), by a Young tableau we
mean the Young diagram of λ filled with tablets containing integers
A = {1, 2, · · ·n}.
Definition 3.1.4. Let λ ⊢a (1
2r(r + 1) + 2n). Let λ = λ, λ1, . . . , λr = δr
be a sequence of partitions obtained by successive removal of rim 2-hooks.
The reverse of such a sequence of partitions is called a path of λ.
Definition 3.1.5. A tableau is said to be standard if the entries are
increasing along a path of λ.
Example λ =
∗ ∗ ∗ ∗
∗ ∗
Then λ0 = Φ, λ1 = ∗ ∗ , λ2 = ∗ ∗ ∗ ∗ , λ3 =
∗ ∗ ∗ ∗
∗ ∗
= λ.
A standard tableau of shape corresponding to the above path
(λ0, λ1, λ2, λ3, ) is obtained as given below
Φ, 1 1 , 1 1 2 2 ,
1 1 2 2
3 3
M. Parvathi, B. Sivakumar, A. Tamilselvi 91
Another standard tableau of the same shape λ =
∗ ∗ ∗ ∗
∗ ∗
corre-
sponding to the path
λ0 = Φ, λ1 =
∗
∗
, λ2 =
∗ ∗
∗ ∗
, λ3 =
∗ ∗ ∗ ∗
∗ ∗
= λ.
is obtained as follows
λ0 = Φ, λ1 =
1
1
, λ2 =
1 2
1 2
, λ3 =
1 2 3 3
1 2
= λ.
3.1.6. Theorem.[R-S correspondence] The map π
R−S
←→ (P, Q) is a bi-
jection between elements of S̃n and pairs of standard tableaux of the
same shape λ ⊢a (1
2r(r + 1) + 2n), where λ varies over partitions of
(1
2r(r + 1) + 2n) whose 2-core is δr, r ≥ 0.
Proof. We construct the bijection denoted by π
R−S
←→ (P, Q) where π ∈
S̃n and P, Q are λ−tableaux, λ ⊢a (1
2r(r + 1) + 2n) as follows. We first
describe the map that, given a permutation, produces a pair of tableaux.
”π
R−S
−→ (P, Q)” Suppose that π is given in two-line notation as
π =
(
1 2 . . . n
x1 x2 . . . xn
)
where xi ∈ {−n,−n + 1, . . . ,−1, 1, . . . , n− 1, n}.
We construct a sequence of tableaux pairs
(P0, Q0), (P1, Q1), . . . , (Pn, Qn) = (P, Q),
where P0, Q0 are the tableau of shape δr whose entries are 0’s and
x1, x2, . . . , xn are inserted into the P ’s as tablets and the correspond-
ing 1, 2, . . . , n are placed in the Q’s as tablets so that shPk = shQk for
all k. The operations of insertion and placement will now be described.We
define the insertion process inductively. Let P be a partial tableau whose
2-core is δr, i.e., an array with distinct entries which increase along a path
of λ . (So a partial tableau with 2-core δr will be standard if its elements
are precisely tablets of {1, 2, . . . , n}.)
Let x be an element not in P . To insert x into P, we proceed as
follows:
If x is positive then the horizontal tablet αx = x x is to be inserted
into P along the cells (i, j) and (i, j + 1). The (i, j + 1)th cell of αx is
92 R-S correspondence
called the head node of αx and the (i, j)th cell of αx is called the tail
node of αx.
If x is negative then x := |x| and the vertical tablet βx =
x
x
is to
be inserted into P along the cells (i, j) and (i + 1, j). The (i, j)th cell of
βx is called the head node of βx and the (i + 1, j)th cell of βx is called
the tail node of βx.
If x is positive then,
A Set Row i := 1, head node of αx := x and tail node of αx := x.
B If head node of αx is less than some element of Row i then,
Let y be the smallest element of Row i
greater than x which is in the cell (i, j).
y i
j
(2 cases arise,
(BI) tablet containing y is horizontal
i.e., αy.
y y i
j
(BII) tablet containing y is vertical
i.e., βy.)
y
y i
j
case BI If the tablet containing y is αy. (i.e.head node of αy is in
the cell (i, j + 1) and the tail node of αy is in the cell (i, j))
then, replace tablet αy by tablet αx.
Set tablet αx := tablet αy, Row i := i + 1 and go to B.
case BII If the tablet containing y is βy. (i.e. head node of βy is
in the cell (i, j) and the tail node of βy is in the cell (i + 1, j))
then
Let z be the element in the cell (i, j + 1). y
y z i
j
(3 cases arise,
(BIIa) tablet containing z is horizontal i.e., αz. y
y z z i
j
(BIIb) tablet containing z is vertical i.e., βz. y
y z
z
i
j
(BIIc) z is empty.
y
y i
j
M. Parvathi, B. Sivakumar, A. Tamilselvi 93
case BIIa If the tablet containing z is αz (i.e., head node of
αz is in the cell (i, j + 2) and tail node of αz is in the cell
(i, j + 1)) then replace head node of βy and tail node of
αz by the tablet αx.
Set x1 := the element in the cell
(i + 1, j + 1) and
x2 := the element in the cell
(i + 1, j + 2).
y
y z z
x1x2
i
j
Place head node of βy and tail node of αz in the cells
(i + 1, j + 1) and (i + 1, j + 2) respectively.
z: ( 3 cases arise,
(BIIa1) x1 is empty.
(BIIa2) x1 = x2.
(BIIa3) x1 6= x2.)
case BIIa1 If x1 is empty then stop.
case BIIa2 If x1 = x2 then
Set tablet αx := tablet αx1
, Row i := i + 2 and go to
B.
case BIIa3 If x1 6= x2 then
(2 cases arise,
(BIIa3i) the element in the cell (i+1, j +3) = x2, i.e.,
αx2
(BIIa3ii) the element in the cell (i + 2, j + 2) = x2,
i.e., βx2
)
case BIIa3i If the element in the cell (i+1, j +3) =
x2 then
Set y1 := the element in the cell (i + 2, j + 2) and
y2 := the element in the cell (i + 2, j + 3)
replace the element in the cell (i + 2, j + 2) and
(i + 2, j + 3) by
head node of βx1
and tail node of αx2
respectively.
Set x1 := y1, x2 := y2, Row i = i + 1, Column
j = j + 1 and go to z.
case BIIa3ii If the element in the cell (i + 2, j + 2)
= x2 then
Set tablet βx := tablet βx2
,
replace the elements in the cell (i+2, j +2) by head
node of βx1
.
Set Column j := j + 3 and go to B′. (B′ is the
case as in B by replacing row by column, column by
94 R-S correspondence
row, positive tablet by negative tablet and negative
tablet by positive tablet.)
case BIIb If the tablet containing z is βz (i.e., head node of
βz is in the cell (i, j + 1) and tail node of βz is in the cell
(i + 1, j + 1)) then
replace head nodes of βy and βz by the tablet αx and tail
node of βz by head node of βy.
Set tablet βx := tablet βz, Column j := j+3 and go to B
′
(B′ is the case as in B by replacing row by column, column
by row, positive tablet by negative tablet and negative
tablet by positive tablet.)
case BIIc If z is empty then
replace head node of βy by tail node of αx, place head
node ofαx and head node of βy in the cell (i, j + 1) and
(i + 1, j + 1) respectively and stop.
C Now head node of αx is greater than every element of Row i so place
the tablet αx at the end of the Row i and stop.
If x is negative then, replace row by column, column by row, positive
tablet by negative tablet and negative tablet by positive tablet in the
positive case.
Placement of the tablet of an element in a tableau is even easier than
insertion. Suppose that Q is a partial tableau of shape µ and if k is
greater than every element of Q, then place the tablet of k in Q along
the cells where the insertion in P terminates.
To build the sequence of tableaux pairs from the permutation
π =
1 2 · · · n
x1 x2 · · · xn
start with a pair (P0, Q0) of tableaux of shape δr whose entries are 0’s.
Assuming that (Pk−1, Qk−1) has been constructed, define (Pk, Qk) by
Pk = ixk
(Pk−1),
Qk = place tablet of k into Qk−1 where the insertion in P terminates.
Note that the definition of Qk ensures that shPk = shQk for all k. The
P tableau is called the insertion tableau and the Q tableau is called the
recording tableau.
To show that we have a bijection, we construct an inverse correspon-
dence.
′′P, Q)
S−R
−→ π′′. We begin by defining (Pn, Qn) = (P, Q). We proceed
M. Parvathi, B. Sivakumar, A. Tamilselvi 95
inductively, assuming that (Pk, Qk) has been constructed, we will find xk
(the kth element of π) and (Pk−1, Qk−1). To avoid double subscripting in
what follows, we use Pi,j to stand for the (i, j) entry of Pk.
Find the cells containing the tablet of k in Qk.
2 cases arise,
† The cells containing tablet of k in Qk are (i, j − 1) and (i, j)
‡ The cells containing tablet of k in Qk are (i− 1, j) and (i, j)
case † If the cells containing tablet of k in Qk are (i, j − 1) and (i, j),
since this is the largest element whose tablet appears in Qk, Pi,j−1, Pi,j
must have been the last element to be placed in the construction of Pk.
We can now use the following procedure to delete Pi,j−1, Pi,j from P .
For convenience, we assume the existence of an empty zeroth row above
the first row of Pk and empty zeroth column to the left of the first column
of Pk.
Set x1 := Pi,j−1, x2 := Pi,j and erase Pi,j−1, Pi,j .
(2 cases arise,
(A) x1 = x2
(B) x1 6= x2)
case A If x1 = x2 then
case AI Set head node of αx := x2, tail node of αx := x1 and Row
i := (i− 1)th row of Pk.
case AII If Row i is not the zeroth row of Pk then
Let y be the largest element of Row i smaller than x which is
in the cell (i, l)
(2 cases arise,
(AIIa) the tablet containing y is αy
(AIIb) the tablet containing y is βy)
case AIIa If the tablet containing y is αy then
replace tablet αy by tablet αx and
Set tablet αx := tablet αy, Row i := i − 1 and
goto AII
case AIIb If the tablet containing y is βy then
Let z be the element in the cell (i, l − 1) and replace tail
node of βy and z by tablet αx.
Set x1 := z and x2 := tail node of βy and go to B.
case AIII Now the tablet αx has been removed from the first row,
so
Set πk := x.
96 R-S correspondence
case B If x1 6= x2 then
(2 cases arise,
(B1) the tablet containing x1 is βx1
(B2) the tablet containing x1 is αx1
)
case BI If the tablet containing x1 is βx1
then
replace head node of βx1
by tail node of βx2
.
Set tablet βx := tablet βx1
and
Column j := j − 2 and go to A′II. (A′II is
the case as in AII by replacing row by column, column by
row, positive tablet by negative tablet and negative tablet by
positive tablet.)
case B2 If the tablet containing x1 is αx1
then
replace the elements in the cell (i− 1, j − 2) and (i− 1, j − 1)
by head node of αx1
and tail node of βx2
respectively.
Set x1 := the element in the cell (i− 1, j − 2)
x2 := the element in the cell (i− 1, j − 1) and
if x1 = x2 then Row i := i− 1 and go to A
else Column j = j − 1 go to B.
Case ‡ follows as in case † by replacing row by column, column by
row, positive tablet by negative tablet and negative tablet by positive
tablet.
It is easy to see that Pj−1 is Pj after the deletion process just described
is complete and Qj−1 is Qj with the tablet of j erased. Continuing in
this way, we eventually recover all the elements of π in reverse order.
This completes the proof of the theorem.
Now we consider an example of the complete algorithm. Boldface
numbers are used for the elements of the lower line of π and hence also
for the elements of the Pk.
Example:
Let
π =
(
1 2 3 4 5
−4 2 5 1 −3
)
.
i *
M. Parvathi, B. Sivakumar, A. Tamilselvi 97
Then the tableau whose 2-core is empty is constructed by the algo-
rithm are
Pk = φ, 4,
4
2 2 ,
4 4
2 2 5 5 ,
4 4
1 1 5 5 ,
2 2
4 4
1 1 5 5
2 2
3 4
3 4
= P
Qk = φ , 1 ,
1
1 2 ,
1 2
1 2 3 3 ,
1 2
1 2 3 3 ,
1 2
4 4
1 2 3 3
1 2
4 4
5 5
= Q
So the permutation
(
1 2 3 4 5
−4 2 5 1 −3
)
gives the pair of tableaux
1 1 5 5 1 2 3 3
2 2 , 1 2
3 4 4 4
3 4 5 5
For the same permutation, the tableau whose 2-core is (4, 3, 2, 1, 0) is
constructed by the algorithm are
Pk = 0 0 0 0 ,
0 0 0
0 0
0
0 0 0 0 ,
0 0 0
0 0
0
4
4
0 0 0 0 2 2 ,
0 0 0
0 0
0
4
4
0 0 0 0 2 2 5 5 ,
0 0 0
0 0
0
4
4
0 0 0 0 1 1 5 5 ,
0 0 0 2 2
0 0
0
4
4
0 0 0 0 1 1 5 5
0 0 0 2 2
0 0
0 4
3 4
3
= P
Qk = 0 0 0 0 ,
0 0 0
0 0
0
0 0 0 0 ,
0 0 0
0 0
0
1
1
0 0 0 0 2 2 ,
0 0 0
0 0
0
1
1
0 0 0 0 2 2 3 3 ,
0 0 0
0 0
0
1
1
0 0 0 0 2 2 3 3 ,
0 0 0 4 4
0 0
0
1
1
0 0 0 0 2 2 3 3
0 0 0 4 4
0 0
0 5
1 5
1
= Q
So the pair of tableaux associated with the signed permutation
(
1 2 3 4 5
−4 2 5 1 −3
)
98 R-S correspondence
is given by
0 0 0 0 1 1 5 5 0 0 0 0 2 2 3 3
0 0 0 2 2 0 0 0 4 4
0 0 0 0
0 4 0 5
3 4 1 5
3 1
4. Combinatorial properties of the R-S Correspondence
Proposition 4.1.1. Let π ∈ S̃n such that π = x1x2 . . . xn. Then
P (π−) = P t and Q(π−) = Qt where π− = (−x1)(−x2) . . . (−xn) and
P t is the conjugate of the P -tableau.
Proof. The insertion of positive elements is done along the rows and the
insertion of negative elements along the columns. The process of insertion
of positive and negative dominoes gets interchanged for π− as compared
to that of π. Hence P (π−) = P t and Q(π−) = Qt.
4.2. Growth and Local rules
We define the growth and local rules for the RS algorithm developed in
previous section following that for the symmetric group.
Definition 4.2.1. We define a partial order ≤ on the set of partitions of
(1
2r(r + 1) + 2n) whose 2−core is δr, r ≥ n− 1 as, λ ≤ µ if λ is obtained
from µ by successive removal of rim 2-hooks.
Definition 4.2.2. Let λ, µ be partitions of (1
2r(r+1)+2n) whose 2−core
is δr, r ≥ n− 1. The smallest partition containing both λ and µ is said
to be the join of λ and µ, denoted by λ ∪ µ.
Definition 4.2.3. Let λ, µ be partitions of (1
2r(r+1)+2n) whose 2−core
is δr, r ≥ n− 1. The largest partition which is contained in both λ and
µ is said to be the meet of λ and µ, denoted by λ ∩ µ.
The RS-insertion algorithm is defined in a fashion very similar to that
for the symmetric group. The growth and local rules also follows closely
as that for the symmetric group.
Let Y be the lattice of partitions of (1
2r(r + 1) + 2n) whose 2−core is
δr, r ≥ n− 1.
Let Cn be the n-chain. i.e. 1−2−3−· · ·−n lattice in set {1, 2, . . . , n}.
M. Parvathi, B. Sivakumar, A. Tamilselvi 99
We will represent the elements of Cn×Cn as vertices (i, j), 0 ≤ i, j ≤ n
and covering relations as lines. The squares thus formed will be cordi-
nated with square (i, j) being the one whose north east vertex is (i, j).
Let π = x1x2 . . . xn be the second line notation of the permutation
π ∈ S̃n. The element xi is represented by a domino if xi > 0 and
by the domino if xi < 0 in the square (i, |xi|).
We now define the growth gπ : Cn × Cn → Y that will depend on π.
We start by letting
gπ(i, j) = ∅ if i = 0, j = 0.
Consider the square with coordinates (i, j) labeled as in diagram
λ
ν
s
µ
ρ
Note :
• s can be empty
• s can be
• s can be
Suppose by induction on i+j that we have defined gπ(i−1, j−1), gπ(i, j−
1) and gπ(i − 1, j) which we denote by λ, µ and ν respectively, we then
define gπ(i, j), denoted by ρ using the following local rules.
4.2.4. Local Rules
LR1 If µ 6= ν then ρ = µ ∪ ν.
LR2 If λ < µ = ν. Two cases arise.
1. If µ is obtained fromλ by adding a positive domino to
λi for some i, then, ρ is obtained from µ by adding a positive
domino to µi+1.
2. If µ is obtained fromλ by adding a negative domino to λ′
j
for some j, then, ρ is obtained from µ by adding a negative
domino to µ′
j+1.
100 R-S correspondence
LR3 If λ = µ = ν, then let
ρ =
λ , if the box does
not contain a domino
λ with added to first row λ1 , if appears in box
λ with added to first column λ′
1, if appears in box
Lemma 4.2.5. Let π ∈ S̃n then P (π−1) = Q(π).
Proof. This is a consequence of the fact that growth diagram and local
rules are symmetric.
4.3. Relation between the sets of bipartitions of n and parti-
tions of 2n whose 2-core is δr
In this section, we give a bijection between the set of bipartitions of n
and that of single partitions of 2n whose 2-core is δr, r ≥ n− 1, which is
dominance order preserving.
Definition 4.3.1. Let ρ be a partition of (1
2r(r +1)+2n) whose 2−core
is δr, r ≥ n− 1. We define a map
η : ρ 7→ (λ, µ), λ ⊢ l, µ ⊢ m, l + m = n
such that if r is even
λi =
1
2
(ρi − (n− i))
µi =
∑
j
µ′
j≥i
1 where µ′
j =
1
2
(ρ′j − (n− j))
if r is odd
λi =
1
2
(ρi − (n− i) + 1)
µi =
∑
j
µ′
j≥i
1 where µ′
j =
1
2
(ρ′j − (n− j) + 1)
Lemma 4.3.2. Let ρ, ν be partitions of (1
2r(r + 1) + 2n) whose 2−core
is δr, r ≥ n− 1 (r = n− 1, if n is odd and r = n, if n is even) such that
ρ = (λ, µ) and ν = (α, β). Then ρ D ν ⇔ (λ, µ) D (α, β).
M. Parvathi, B. Sivakumar, A. Tamilselvi 101
Proof. When r is even (r-odd follows similarly), let ρ D ν. i.e.
j∑
i=1
ρi ≥
j∑
i=1
νi, ∀j.
λi =
1
2
(ρi − (n− i))
j∑
i=1
λi =
1
2
j∑
i=1
(ρi − (n− i)) ≥
1
2
j∑
i=1
(νi − (n− i)) =
j∑
i=1
αi
To show |λ|+
j∑
i=1
µi ≥ |α|+
j∑
i=1
βi, ∀j.
Since ρ D ν ⇔ ν ′ D ρ′, we have
j∑
i=1
ρi ≥
j∑
i=1
νi ⇔
j∑
i=1
ρ′i ≤
j∑
i=1
ν ′
i.
By an argument similar to the one in the first part we have,
1
2
j∑
i=1
(ρ′i − (n− i)) ≤
1
2
j∑
i=1
(ν ′
i − (n− i)), ∀j
j∑
i=1
µ′
i ≤
j∑
i=1
β′
i, ∀j
j∑
i=1
µi ≥
j∑
i=1
βi, ∀j since β′ D µ′ ⇔ µ D β
|α|+
j∑
i=1
µi ≥ |α|+
j∑
i=1
βi, ∀j
|λ|+
j∑
i=1
µi ≥ |α|+
j∑
i=1
βi, ∀j, since |λ| ≥ |α|
Since the map η defined above is a bijection, the other part follows. Hence
the proof.
Lemma 4.3.3. Let ρ be a partition of (1
2r(r + 1) + 2n) whose 2-core is
δr. Then ρ can be associated to a pair of partitions as in Definition 2.1.8.,
but when associated to a pair of partitions through the map η we have,
every domino in row i of ρ corresponds to a node of λi and every domino
in column j of ρ corresponds to a node of µ′
j .
Proof. The proof follows by observing that every ρi is of the form j +2k
for some 0 ≤ k ≤ n, where the head node of a positive domino is in the
cell (i, j) and hence ρi− i ≡ j− i (mod2). Similarly for a negative domino
102 R-S correspondence
with tail node in the cell (i, j), the lemma follows from the fact that every
ρ′j is of the form i+2k for some 0 ≤ k ≤ n and hence ρ′j−j ≡ j−i (mod2).
Remark 4.3.4. In [2], Bonaffé and Iancu constructed a generalised R-S
correspondence for the set of bipartitions of n. Any xi is inserted along
the rows of partitions depending on being greater than or less than zero.
i.e. the negative and positive in the permutation are inserted separately,
which gives the tableaux ((P (+), P (−)), (Q(+), Q(−))) which follows the
insertion procedure for the symmetric group.
We define a procedure of insertion of positive domino of xi > 0,∀i
along the rows using dominoes and negative domino xj < 0,∀j along the
columns using dominoes, which gives the pair of tableaux (P, Q). By
lemma 4.3.3, we may split P = (P (0), P (1)), Q = (Q(0), Q(1)) where for
i = 0, 1
P (i) = tableau formed by the tablets whose head nodes are in
ith–residue of P
Q(i) = tableau formed by the tablets whose head nodes are in
ith–residue of Q
If δr is such that r is even then since positive values are inserted along
the rows in both P (0), P (+), and Q is recording tableau we have
P (0) = P (+), Q(0) = Q(+)
and since negative values are inserted along the rows in P (−) and along
the columns in P (1), and Q is recording tableau we have
P (1) = (P (−))t, Q(1) = (Q(−))t.
If δr is such that r is odd then since positive values are inserted along
the rows in both P (1), P (+), and Q is recording tableau we have
P (1) = P (+), Q(1) = Q(+)
and since negative values are inserted along the rows in P (−) and along
the columns in P (0), and Q is recording tableau we have
P (0) = (P (−))t, Q(0) = (Q(−))t.
The dominance ordering for the indexing set of the cellular basis hap-
pens naturally in our insertion process, whereas for the Bonnafé and Iancu
[2] insertion process, one has to take the following:
(λ1, λ2) D (µ1, µ
t
2)
M. Parvathi, B. Sivakumar, A. Tamilselvi 103
Proposition 4.3.5. Let w ∈ S̃n. The R-S correspondence gives a pair of
standard tableaux w ←→ (P (w), Q(w)). For any x, y ∈ S̃n, P (x) = P (y)
if and only if x ←→L y, where P (x), P (y) are the tableaux of shape
λ ⊢a 2n + |δr|, r ≥ n− 1.
Proof. As in [[2] Prop.3.8.], we define admissible transformations in S̃n.
Let x ∈ S̃n be represented as
x =
(
1 2 . . . i i + 1 . . . n
ε1p1 ε2p2 . . . εipi εi+1pi+1 . . . εnpn
)
εj ∈ {1,−1}, pj ∈ {1, 2, . . . , n}, pi 6= pj for i 6= j. The proof of the
proposition is similar to the proof given in [2]. Since we give insertion in
a single tableau, the proof closely follows that of the symmetric group.
Interchanging εipi and εi+1pi+1 is an admissible transformation if
(a) 2 ≤ i ≤ n − 1, εi−1 = εi = εi+1 and pi−1 lies between pi and pi+1,
denoted by x
a
∼ si+1x
(b) 1 ≤ i ≤ n − 2, εi = εi+1 = εi+2 and pi+2 lies between pi and pi+1,
denoted by x
b
∼ si+1x
(c) εi = −εi+1, denoted by x
c
∼ si+1x.
The group theoretical description of these admissible transformation
is given by xsi < x if and only if x(i+1) < x(i) (εi = εi+1 or εi = −εi+1).
The following cases arise
1. Each of (a) and (b) have two cases
(a+) εi−1 = εi = εi+1 = 1
(a−) εi−1 = εi = εi+1 = −1
Similarly,
(b+) εi = εi+1 = εi+2 = 1
(b−) εi = εi+1 = εi+2 = −1
In the case of the symmetric group
(a) type transformation corresponds to Knuth relation of first kind and
(b) type transformation corresponds to Knuth relation of second kind.
Proof in case (a+) We prove as in the case of symmetric group.
x = p1 . . . pi−1pipi+1 . . . pn
y = p1 . . . pi−1pi+1pi . . . pn.
104 R-S correspondence
Since all elements inserted before pi−2 are same, it suffices to prove that
for any partial tableau inserting pi−1, pi, pi+1 and pi−1, pi+1, pi in the
respective order yield the same tableau. (We are in the positive case and
all dominoes inserted are along the first row)
If we denote by Ipi
(P ) the tableau rewriting from inserting pi in P ,
we have to prove
Ipi−1
Ipi
Ipi+1
(P ) = Ipi−1
Ipi+1
Ipi
(P ) (1)
The proof is same as in the case of symmetric group, we give it here for
the sake of completion. We prove this claim by induction on the number
of rows in P . For P = δr, both sides of (1) yields the same tableau.
× × · · · × pi pi pi−1 pi−1
× × · · · pi+1 pi+1
× · · · ×
× × ×
× ×
×
Now assume that P has r rows. Suppose the tablet pi−1 pi−1
enters in the first row along kth and (k + 1)th column by replacing
p′i−1 p′i−1 , we examine both sides of (1). Assume pi pi is inserted
next. Since pi < pi−1, pi pi replaces some p′i p′i from columns
j, j + 1 with j < k. Also p′i < p′i−1. This follows from Lemma 4.3.3.
Similarly pi+1 > pi that pi+1 pi+1 replaces some element
p′i+1 p′i+1 from column l, l + 1 with l > k and p′i+1 > p′i. Consid-
ering the right hand side of (1), we get that pi+1 pi+1 and pi pi
if inserted in this respective order, replace same elements p′i+1 p′i+1
and p′i p′i from same column l, l + 1 and j, j + 1.
Therefore the first rows of two tableaux obtained are same. Moreover
the rest of tableau is obtained by inserting p′i−1, p
′
i, p
′
i+1 and p′i−1, p
′
i+1, p
′
i
in a tableau of a strictly smaller number of rows in this respective order.
Since the same order p′i < p′i−1 < p′i+1 still holds we appeal to induction
to asset that the rest of the tableau are also the same.
Proof in case (a−) is obtained by replacing rows by columns in proof of
(a+). The argument is the same since positive dominoes insertion along
the rows is replaced by negative dominoes insertions along columns.
Since (b) part corresponds to the Knuth relation of second kind, a
similar argument like that of (a) works. This completes the first half of
the proof.
Since by lemma 4.1.3, the dominoes in the 0-residue and 1-residue
classes split we can get the word associated to a tableau as in the case
M. Parvathi, B. Sivakumar, A. Tamilselvi 105
of the symmetric group. Given a tableau P , we can associate a pair of
elements (wp, w
†
p) called the row word pair of P .
wp = w0
pw
1
p and w†
p = w1
pw
0
p
where w0
p is the row word associated to the 0-residue and w1
p is the row
word associated to the 1-residue.
We will show that π
a+
∼ πP . ( Note that in the case of a−, π
a−
∼
π
†
P .) Since Knuth relations are transitive the converse of the theorem
will follow. We induct on n. The base case is trivial for n = 1, π = πP .
Now, assume that x is the last element of π, i.e, π is written in one line
notation as π = . . . x if x > 0.
On π = π′x, where π′ is a sequence of n− 1 elements. Therefore, by
induction we have π′ a+
∼ π′
P where P ′ = P (π′). Thus it suffices to prove
that πP ′x
a+
∼ πP .
Let R1, . . . , Rl, C1, . . . , Cm be the rows and columns of P ′. Assume
that R1 = p1 · · · pk. If the domino x enters P ′ in the column j, j +1, then
p1 < . . . < pj−1 < x < pj < . . . < pk.
Therefore, we have the following Knuth operation
π′
P x = Cl · · ·C1Rl · · ·R2p1 · · · pkx
a+
∼ Cl · · ·C1Rl · · ·R2p1 · · · pk−1xpk
...
a+
∼ Cl · · ·C1Rl · · ·R2p1 · · · pj−1pjxpj+1 · · · pk
b+
∼ Cl · · ·C1Rl · · ·R2p1 · · · pjpj−1xpj+1 · · · pk
...
b+
∼ Cl · · ·C1Rl · · ·R2pjp1 · · · pj−1xpj+1 · · · pk
Therefore the Knuth relations generate exactly the first row of P (π).
Also the element replaced by x from the first row comes at the end of R2.
The above sequence of operations can be repeated for each row to get
the same tableau. The other case is done by replacing row by column.
Since the (c) type of transformations do not change the relative ordering
of elements within the residues the P -tableau remain the same.
Remark 4.3.6. The partitions of 2n whose 2-core is δr gives rise to
an alternative description of the indexing set of the cellular basis in the
sense of Graham and Lehrer [7] in the asymptotic case in type Bn the
Kazhdan-Lusztig basis {Cw|w ∈ Hn} given in [6].
106 R-S correspondence
Note 4.3.7. The signed Brauer algebra was introduced in 1997 by Par-
vathi and Kamaraj [10]. These algebras contain Brauer algebras and the
group algebra of the hyperoctahedral group of type Bn, as subalgebras.
The study of the signed Brauer algebras has assumed importance since
the realization of these algebras as homomorphic image of centralizer of
certain closed subgroup Ot(n) of orthogonal group [11]. We are on the
process of constructing a cellular basis for the signed Brauer algebras
using the cellular basis of the hyperoctahedral group of type Bn.
Acknowledgement
We would like to express our sincere thanks to the referee for his com-
ments and suggestions for the improvement of the paper.
References
[1] D.Barbasch, D.Vogan Primitive ideals and orbital integrals on complex classical
groups, Math.Ann., 259 (1982), 153-199.
[2] C.Bonnafé and L.Iancu Left cells in type Bn with unequal parameters, preprint,
2003; available at arXiv: math.RT/0302037.
[3] Bruce E.Sagan The symmetric group, second edition, Springer 1991.
[4] S.Fomin Schensted algorithms for dual graded graphs, J.Alg.Combin. 4 (1995),
5-45.
[5] D.Garfinkle On the classification of Primitive ideals for complex classical Lie
algebras II, Compositio Math., 81 (1992), 307-336.
[6] M.Geck Relative Kazhdan-Lusztig cells, preprint(2005), available at
http://www.arXiv.org/math.RT/0504216.
[7] Graham and Lehrer Cellular algebra, Invent. Math., 123 (1996), 1-34.
[8] G.James and A.Kerber The Representation theory of the symmetric group, Ency-
clopedia of mathematics and its applications, Addison Wesley publishing company
1981.
[9] C.Musili Representations of finite groups, Hindustan book agency.
[10] M.Parvathi and M.Kamaraj Signed Brauer Algebras, Comm. in Algebra, 26(3)
(1998), 839-855.
[11] M.Parvathi and C.Selvaraj Signed Brauer Algebras as centralizer Algebras,
Comm. in Algebra 27(12) (1999), 5985-5998.
[12] M.Parvathi and C.E.Shanthi Representation of Hecke algebra of type Bn, Comm.
in Algebra 27(11) (1999), 5203-5234.
[13] G.De.B.Robinson Representation theory of symmetric group, Edinburg University
press, 1961.
[14] M.Shimozono And D.E.White Color to spin ribbon Schensted algorithms, Discrete
Math., 246(2002), 295-316.
[15] M.A.A.Van Leeuwen The Robinson Schensted and Shutzenberger algorithms an
elementary approach, Electronic J. Combin., 3 (1996).
M. Parvathi, B. Sivakumar, A. Tamilselvi 107
Contact information
M. Parvathi,
B. Sivakumar,
A. Tamilselvi
Ramanujan Institute for Advanced study
in mathematics, University of Madras,
Chennai-600 005, India
E-Mail: sparvathi.riasm@gmail.com,
b.sivakumar@hotmail.com,
tamilselvi.riasm@gmail.com
Received by the editors: 23.04.2007
and in final form 25.05.2007.
|