COMBINATORICS ON BIGRASSMANNIAN PERMUTATIONSAND ESSENTIAL SETSMASATO KOBAYASHI

Contents
1. Symmetric groups
Introduction
Sn as a Coxeter group
Bigrassmannian permutations?
Bigrassmannian statistics
Signed bigrassmannian statistics
2. Essential sets
Essential sets and Baxter permutations
dual essential sets
ranked diagrams
Two interpretations
3. Alternating sign matrices
Hisotry: ASM conjecture
Byproducts
Open problems
References

22
3
4
5
6
7
7
8
10
11
12
12
13
14
15oooooooooo

4321 OO

OOO
OOO
OO

3421 OO

4231

2134 OO

13244312

OOO
OOO
oOOO oooo
OOO
OOO
oooOOO
oooOOOOO
oooOOOO
Ooooooo
3241?
2431 TTTT
3412
4213?
4132?
?
?
??
ÄÄÄ
Ä
TTTT Ä??
??
ÄÄÄ
ÄÄ??
TÄ
Ä
Ä
Ä
??
??
ÄÄ
Ä TTTTT
Ä
ÄÄ?
ÄÄ
Ä
Ä
Ä
TTÄ
Ä
Ä
Ä
Ä
3214? TTTT
2341
3142 TTTT
2413
4123?
1432
jjj?? TTT ÄÄ?
TTTT ÄÄ??jjjjj ÄÄÄÄÄTÄTT??
ÄÄÄÄTTTTTTjjjj ?? ÄÄÄ? ÄÄÄ TTTTTTTTÄÄÄÄ
jjjj
3124 OO
2314 OO
1342
2143 OO
1423
oOOO oooo
OOO oooo
OOO
oooOOOoOO
oOO
oooooO
ooO
OO
OO
OO
ooooooooooooooooooo

OOO
OOO
OO

1234oooooooooo1243

Date: October 26, 2013.
Key words and phrases. Alternating sign matrices, Baxter permutations, Bigrassmannian permutations, Bruhat order, Coxeter groups, Essential sets, Permutation Statistics.
Osaka Combinatorics Seminar, Osaka City University.
12

MASATO KOBAYASHI

Permutations(Coxeter) groupnon-lattice
Bruhat order
graded by ` L L

Alternating sign matrices

MacNeille completion

LL

L

L

LLLLppp

pp

ppp

/pp

non-grouplatticeEhresmann order
graded by βbigrassmannian = join-irreducible
Figure 1. Structures of two classes of matrices
1. Symmetric groups
Introduction. Symmetric groups

Permutation statistics:
Coxeter length

major index

MacMahon:
Xq `(w) =w∈Sn

Mahonian, Eulerian,.

— Sn as a Coxeter group —3

Sn as a Coxeter group.

•••···Notation.
W =

S=T =

`=

Inversion set
I(w) =
Def (height, weak order, Bruhat order).

•4

MASATO KOBAYASHI

Bigrassmannian permutations?
Def (bigrassmanninan permutations).

[Four-box construction]
123 · · · n →.

1 34567 2 8 ,,andQuestion.

Def (join-irreducibility).

Fact (MacNeille completion).

Fact (Lascoux-Schützenberger 1996). The following are equivalent:(1)(2)•OOOOO

Figure 2. MacNeille completionoOOooo• OOO

OOO
oOOO
oooooooo OOOOO
OOO
ooooo•oo•O

OOO
oOOO
ooooo•OOO
ooooo
OOOOoooooOOO
oo•OOO
oooOOO
oooOooOo•OOOO
ooo•OOO
ooOOOooooo•OooOoOOO•oooo−→•.

— Bigrassmannian statistics —5Bigrassmannian statistics.
Def (bigrassmannian statistic).
β(w) =Fact (Kobayashi 2011).
nX
1 X(w(i) − w(j)) =β(w) =(i − w(i))2 .
2i<ji=1w(i)>w(j)Example.

β(3412) =β(4321) =Def (signed bigrassmannian polynomials).
Bn (q) =2341 WWWWW
3412 WWWWW
4123
GG
GG
WWWWW ggggggggg w
WWWWW ggggggggg
GGG
www
W
W
gg
W
W
g
g
Gw
w
W
W
gg
W
W
gg
W
W
gg
G
GGw
w
W
Wgg
WwWWWW
WWWWW
ggg
ggGgGG
GG
www
ggg
g
WW
g
g
w
w
WW
g
g
W
W
g
g
Gw
w
W
W
g
g
W
W
g
g
WWWWW GWWWWW GG
ww ggggggg
ww ggggggg
WWWW
gg2314 GWWWWW
3124 G
1342 Gggg 1423
WWWWW
GG
GG
GG
ggggg wwwg
ww
WWWWW www
g
g
GG
GG
w
g
GG
GGgggg
WWwWw
GG
ww
ww
GG
ggggg GGG
GG
ww WWWWWWWW
ww
ww
g
g
Gw
w
w
g
g
GG
WWWWW Gwwww ggggggg
ww
WWg
2134

1324

1243

Figure 3. Bruhat order of bigrassmannian permutations

6

MASATO KOBAYASHI

Signed bigrassmannian statistics.
Def (q-analog of a matrix).

Proposition (determinantal expression).

Example.

1
 1
det  1
11111



1 q 1/2 q 4/2 q 9/2
1
 1/2 1 q 1/2 q 4/2 
1  = det  q q 4/2 q 1/2 1 q 1/2 
1 
1 qq 9/2 q 4/2 q 1/2 1

1
1
1
1

=(Open problem)•••
Table 1. signed bigrassmannian statistic over S4
1234
1243
1324
1342
1423
1432

sign+−−++
−

β0
1
1
334

2134
2143
2314
2341
2413
2431

sign−++−−+

β1236573124314232143241
3412
3421

sign+−−++−

β3547894123
4132
421342314312
4321

sign β−6+7+7−
9−
9+ 10

— Essential sets and Baxter permutations —2. Essential sets
Essential sets and Baxter permutations.
Def (colored diagram).

•◦• ◦Def (Rothe diagram, essential set).

∗∗
∗

∗

Def (Baxter permutations).

Fact (Eriksson-Linusson). For x ∈ Sn , the following are equivalent:(1) x is Baxter.
(2)

Corollary. bigrassmannian =⇒ Baxter.

78MASATO KOBAYASHI

dual essential sets.
Def (dual essential set).

Def (essential diagram).

Theorem (Kobayashi 2013). The following are equivalent:(1) x is Baxter.
(2)
Theorem (cluster-like structure, Kobayashi 2013). If y = xsi , y(i) > y(i + 1),
thenx··· ···

y◦→• ··· ···

◦ ··· ···→··· ···

•

···
• ···

◦

→

• ···
···

◦

···
◦ ···

•

→

◦ ······

•

→···
◦ ···

•

→···
• ···

◦

◦ ······• ······•◦

— Essential diagram —9Figure 4. Essential diagrams on S4•••••••¦¦¦¦¦¦¦¦¦¦¦¦◦◦◦••
Eµµµµµµµµµµ◦◦◦9999 ¦¦¦99 ¦¦9¦¦¦ 999¦99¦¦¦◦

◦

•

µ◦

µµ•

◦
Eµ◦

•

◦•◦

•

◦•
E

◦

EEµ◦

•

99
9999999999

◦

µ◦

◦

◦

•

µµµ◦

E99
99 ¦¦¦99 ¦¦¦9¦9¦¦ 999¦9¦¦¦¦¦¦¦¦¦¦¦¦¦¦◦,,,,,,,,,,•◦

E µµEµ EE•µµ•
999999999999•E◦

9999 ¦¦¦99 ¦¦¦9¦9¦¦ 999¦9¦¦99
99 ¦¦¦99 ¦¦9¦¦¦ 999¦99¦¦¦•◦µE µµEµ EE•◦999999999999•µµE•◦,, EEEEE,,µµEµE,,µEE,,µµ EEEµEE,,µEEµµ•••,,,,,,,,,,µµµµµµµµµµ•◦99999999
9999¦¦¦¦¦¦¦¦¦¦¦¦◦•,,,,,,,,,,•◦◦,,
yy µ,, yyyµ,,yyyµµµyµyy ,,,µµyy,µyµyy◦•◦µµµµµµµµµµ•◦◦◦¦¦¦¦¦¦¦¦¦¦¦¦•◦•••

10

MASATO KOBAYASHI

ranked diagrams.
Def (ranked diagram).
xe(i, j) =0 1 1g
231 = 0 1 2 .
1 2 3
Proposition. The following are equivalent:(1) x ≤ y(2) xe(i, j) ≥ ye(i, j) for all i, j.
Proposition (Essential conditions). Let x ∈ Sn and (i, j) ∈ [n − 1]2 . Then(1)
(2)
(3)
(4)

⇐⇒⇐⇒
⇐⇒
⇐⇒

j < x(i)i < x−1 (j)x(i + 1) ≤ j
x−1 (j + 1) ≤ ixe(i − 1, j) = xe(i, j).
xe(i, j − 1) = xe(i, j).
xe(i + 1, j) = xe(i, j) + 1.
xe(i, j + 1) = xe(i, j) + 1.

Theorem (Kobayashi). The following are equivalent:(1) x ≤ y(2) xe(i, j) ≥ ye(i, j) for all i, j ∈ Ess(x).
Def (Fulton diagram).

11Example. 1^3254 =
111122123312and 3^5241 =
3300
0000111112211.
230and 3^
5241|Ess(13254) =F (13254) =33

— Two interpretations —Two interpretations.
Coxeter group method:
Proposition (Deodohar).

Finite distributive lattice method:
Proposition (Lascoux-Schützenberger).

1112MASATO KOBAYASHI

3. Alternating sign matrices
0 1 0 1 −1 1 0 1 0
alternating sign matrices
OOO

/•O

/•o

•O o/•o•O/•o²/•/•o•o²²²2
1 3
1 2 3monotone triangles²²6 vertex model

Def (Alternating sign matrices).

Hisotry: ASM conjecture. Robbins-Rumsey (1983)|An | =(Zeilberger (1995)
Kuperberg (1996)

as127427436
21834810850216
911835460
12953427270031095744852375
12611311859677500..
.

— Alternating sign matrices: —Byproducts.
Def (Corner sum matrices, essential sets).

Def (bigrassmannian statistics).

Corollary (essnetial criterion for ASMs). The following are equivalent:

(1)

(2)

Proposition (cluster-like structure, Kobayashi).

13

14

MASATO KOBAYASHI

bigrassmannian permutations
Schur functions
distributive lattice
Young tableaux
SSS
ASM
jj
SSS
jjjj
SSSSjjj)²
jjj

6 vertex model
Fully packed loops

tj

total positivity
immanant
Essential sets
Baxter permutations
Pipe dreams
Schubert polynomials/mm6mmmmmm

Symmetric groups
Bruhat orderO

plane partitions
lattice path counting
oiSSS
SSSSSSS

associahedra, permutahedra,clusterdual Coxeter systems
Coxeter groups
root system

Open problems.
• ASM polytope• Cluster structure• type BC, D, aﬃne

• unsigned bigrassmannian statistic

— References —15References[1] D. Bressoud, Proofs and conﬁrmations, The story of the alternating sign matrix conjecture,
Cambridge University Press, Cambridge, 1999. xvi+274 pp.
[2] D. Bressoud, J. Propp, How the alternating sign matrix conjecture was solved, Notices
Amer. Math. Soc. 46 (1999), no. 6, 637-646.
[3] Fomin-Zelevinsky, Total positivity: tests and parametrizations, Math. Intelligencer 22(2000), no. 1, 23-33.
[4] Fomin-Zelevinsky, Cluster algebras I. Foundations, J. Amer. Math. Soc. 15 (2002), no. 2,497-529.
[5] K. Eriksson, S. Linusson, Combinatorics of Fulton’s essential set, Duke Math. J. 85 (1996),
no. 1, 61-76.
[6] W. Fulton, Flags, Schubert polynomials, degeneracy loci, and determinantal formulas, DukeMath. J. 65 (1992), no. 3, 381-420.
[7] M. Geck, S. Kim, Bases for the Bruhat-Chevalley order on all ﬁnite Coxeter groups, J.
Algebra 197 (1997), no. 1, 278-310.
[8] I. Gessel, G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in
Math. 58 (1985), no. 3, 300-321.
[9] M. Kobayashi, Enumeration of bigrassmannian permutations below a permutation in Bruhat
order, Order 28 (2011), no. 1, 131-137.
[10] M. Kobayashi, Bijection between bigrassmannian permutations maximal below a permutation and its essential set, Electron. J. Combin. 17 (2010), no. 1, Note 27, 8 pp.
[11] G. Kuperberg, Another proof of the alternating-sign matrix conjecture, Internat. Math. Res.
Notices 1996, no. 3, 139-150.
[12] A. Lascoux, M. P. Schützenberger, Treillis et bases des groupes de Coxeter. (French) [Latticesand bases of Coxeter groups] Electron. J. Combin. 3 (1996), no. 2, Research paper 27, 35
pp.
[13] W. Mills, D. Robbins, H. Rumsey, Jr, Alternating sign matrices and descending planepartitions. J. Combin. Theory Ser. A 34 (1983), no. 3, 340-359.
[14] N. Reading, Order dimension, strong Bruhat order and lattice properties for posets, Order
19 (2002), no. 1, 73-100.
[15] N. Reading, Clusters, Coxeter-sortable elements and noncrossing partitions. Trans. Amer.
Math. Soc. 359 (2007), no. 12, 5931-5958.
[16] D. Robbins, The story of 1,2,7,42,429,7436,..., Math. Intelligencer 13 (1991), no. 2, 12-19.
[17] D. Robbins, H. Rumsey Jr. Determinants and alternating sign matrices, Adv. in Math. 62(1986), no. 2, 169-184.
[18] A. Razumov, Y. Stroganov, Combinatorial nature of the ground-state vector of the O(1)loop model, in Theoret. and Math. Phys. 138 (2004), no. 3, 333-337.
[19] J. Striker, A unifying poset perspective on alternating sign matrices, plane partitions, Catalan objects, tournaments, and tableaux, Adv. in Appl. Math. 46 (2011), no. 1-4, 583-609.
[20] J. Striker, The alternating sign matrix polytope, Electron. J. Combin. 16 (2009), no. 1,
Research Paper 41, 15 pp.
[21] D. Zeilberger, Proof of the alternating sign matrix conjecture, Electron. J. Combin. 3 (1996),
no. 2, Research Paper 13, 84 pp.
Graduate School of Science and Engineering Department of Mathematics, Saitama
University, 255 Shimo-Okubo, Saitama 338-8570, Japan.
E-mail address: kobayashi@math.titech.ac.jp