L’Ansatz cellulaire (15)

XGVLaBRI, Bordeaux

22 Juin 2012LaBRI

Petite école de combinatoire

Chapitre 5 Compléments, perspectives

Physique

UD = DU + IdWeyl-Heisenberg

commutationsréécritures

objets combinatoires

planarisés

représentationpar opérateurs

placements de tourspermutations

tableaux alternatifs

bijections

Q-tableauxex: ASM, FPL

pavages, 8-vertex

automates planaires

paires Tableaux Youngpermutations

histoires de Laguerre

histoiresde fichiers

algèbre quadratique Q

polynômesorthogonaux

?

RSK

DE = qED + E + DPASEP

"normal ordering"

planarisation

"L’Ansatz cellulaire"

Heisenbergoperators

U, D

UD = DU + I

(recalling)

+

UD YD

U XU

Y

U

Y

X

XD D

Y YX

X

UD = qDU + I

UD

UD

UD

UD

UD

UD

UDY

UDY

UDY

UDY

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDY

X

UDI

Ipermutation as a complete Q- tableau

permutation as a Q- tableau

another Q-tableau:Rothe diagram of a permutation

representation with operators U and D

UD●

●

●

●

●

●

Young lattice

addingor deleting

a cell ina Ferrersdiagram

The Robinson-Schensted correspondence between permutations and pair of (standard) Young tableaux with the same shape

how to guess such representation ?

data structure

integrated cost

Françon, Flajolet, Vuillemin 1980, .....

data structure history«histoires de fichiers», Françon 1976

Primitive operations for “dictionnaries” data structure:

add or delete any elements, asking questions (with positive or negative answer)

number of choices for eachprimitive operations

this corresponds to the n!“restricted Laguerre histories”

this valuation corresponds to the (n+1)!“enlarged Laguerre histories”

dictionaryand the PASEP algebra

DE = ED + E +D

E

D

this corresponds to the n!“restricted Laguerre histories”

this valuation corresponds to the (n+1)!“enlarged Laguerre histories”

K

S

S = +

A

K

A

S

SJ A

S

416978352

1 1 2

1 3 241 3 241 352416 352

416 7 352416 78352

1

2

34

416978352

5

6 78

D = A + J

D= A+ J

E = S + K

prority queuesand the Weyl-Heisenberg algebra

UD = DU + I

priority queue

Polya urn

A S - S A = I

Hermite

demulplication of the equationsin a quadratic algebra

U

D

X

Y

U D= D U+ Y X

UD

U

D

Operators U and D

UD●

●

●

●

●

●

Young lattice

addingor deleting

a cell ina Ferrersdiagram

1 2 3

1

2

3

1

2

1 2

4 2 1 5 3

demultiplication

positions

another demultiplicationof the algebra UD=DU+Id

(recalling bijection Hermite histories --involutions without fixed points )

Rooks placement

Involution with fixed points in 2 colors

many demultiplicationsof the algebra UD=DU+Id

demultiplication of the PASEP algebra

alternating sign matrices (ASM)

Alternatingsign

matrices

ASM

alternating sign matrices (ex-) conjectureMills, Robbins, Rumsey (1982)

BA

B

A

AʼBʼB

A

Bʼ

Aʼ AʼBʼ

A

B

A

BAʼ

BʼA Aʼ

B

+

+

Bʼ

“planarisation” of the “rewriting rules”

BA

BA

BA

BA

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

The 8-vertex algebra(or XYZ - algebra)

(or Z - algebra)

(XY)Z-tableauxand

B.A.BA configurations(or XYZ- configurations)

(see PEC5, 21 Oct 2011)

BA

Aʼ

Bʼ

demultiplication forthe algebra related to

XYZ configurations and ASM

BA

Aʼ

Bʼ

BA

Aʼ

Bʼ

ASM

a new beginning ....

The (happy) end of

the petite école

first day summer 2012