Permutations de Baxter & Orientations bipolaires planes

JCB 2009

Nicolas Bonichon, Mireille Bousquet-Mélou & Eric Fusy

Permutations

• Une permutation = (1)(2)…(n), est une bijection de [n] dans [n]

• Diagramme d'une permutation est l'ensemble des points (i, (i)).

• Montée : (a) < (a+1),

• descente, saillant-SG, saillant-SD, … = 5 3 4 9 7 8 10 6 1 2

Permutations de Baxter [Glen Baxter’64]

aa+1

la

la+1

dd+1

ld

ld+1

est une permutation de Baxter si :

1) pour chaque montée a la [(a), (a+1)[ t.q : les

rectangles (a+1, (a)) ; (n, la) et

(1,la+1);(a, (a+1)) soient vides.

2) pour chaque descente d ld [(d+1), (d)[ t.q. : les

rectangles (1, (d)) ; (d, ld) et

(d+1,ld+1)(n, (d+1)) soient vides.

2 chefs d’œuvre du 7ième art…

« Baxter permutations are a well known family of permutations that have been intensively studied over the past 30 years, appearing in various branches of mathematics such as analysis, algebraic «geometry and combinatorics »

Orientation bipolaire plane

Une orientation bipolaire plane est une carte planaire orientée :

• Acyclique • 1 seule source s et• 1 seul puits t • s et t sur la face externe.Prop 1 :

Prop 2 : Une carte M admet une orientation bipolaire ssi M+(s,t) est 2-connexe.

V: F:

Bord gauche

Bord droits

t

Orientation bipolaire plane

Une orientation bipolaire plane est une carte planaire orientée :

• Acyclique • 1 seule source s et• 1 seul puits t • s et t sur la face externe.Prop 1 :

Prop 2 : Une carte M admet une orientation bipolaire ssi M+(s,t) est 2-connexe.

V: F:

Orientation bipolaire plane : applications

Dessin de visibilitéDessins orthogonauxStructures transverses…

Enumération

• [Chung et al 79] [Mallows’79]

• Permutation

• Bijections • [Cori, Dulucq, Viennot,

Guibert, Gire] – Arbres jumeaux– Triplets de chemins de

grand Dyck

• [Rodney Baxter’01]• Bipolaires planes

• Bijections– [Fusy, Poulalhon,

Schaeffer’07] Triplets de chemins de grand Dyck

– [Fusy’07] Structures Transverses

– [Felsner, Fusy, Noy, Ordner’07] permutations.

[MBM’03]

m

jn

mn

in

m

jn

mm

in

m

n

nn

ij 1

1

1

1

1

2

1

1

1

)1(

Pas de bijection directePas de bijection simple et directe

Résultat principal

taille n k descentes

l montées i saillants sup gauche

i’ saillants inf droite j saillants sup droite

j’ saillants inf gauche

n arêtesk faces internesl+2 sommetsBord gauche de longueur iBord droit de longueur i’Puits de degré jSource de degré j’

Thm : Une bijection qui envoie les permutations de Baxter sur les bipolaires:

: Etape 1

+2

: Etape 2

Propriétés

Prop 1 : est une application des permutations de Baxter vers les orientations bipolaires

Lemme 1 : les sommets noirs sont de degré 2.

Lemme 2 : Le dessin est planaire.

Arbre de génération des Baxter

• Nœuds de l’arbres : permutations de Baxter.

• Bn -> Bn-1 : suppression de l’élément n.

Arbre de génération des Baxter

• Bn -> Bn-1 : suppression de l’élément n.

• Bn -> Bn+1 : ajout du n+1 – (a) avant le k-ème saillant sup.

gauche – (b) après le k-ème saillant sup

droit.

• Lemme : l’arbre de génération des Baxter est isomorphe à l’arbre :– (1,1)– (i,j) -> {(k, j+1) : 1 <= k <= i} U {(i+1,

k) : 1 <= k <= j}

• Rq : Ces paramètres correspondent aux nombres de saillants supérieurs gauches et droits.

Arbre de génération des Bipolaires

On -> On-1 Soit e=(t,v) l’arête la plus à droite du puits.

• (a) deg-(v) > 1

– Supprimer e

• (b) deg-(v) = 1

– Contracter e

Arbre de génération des Bipolaires

On -> On+1 :

• (a) Ajouter une arête vers le k-ème sommet du bord gauche.

• (b) « déléguer les k premières arêtes »

Lemme : l’arbre de génération des bipolaires est isomorphe à l’arbre :

(1,1)(i,j) -> {(t, j+1) : 1 <= t <= i} U {(i+1, t) : 1 <= t <= j}

est bien une bijection.

Arbres isomorphes une bijection .Par récurrence sur n on montre que

() =()

Symétrie selon la 1ère diagonale

Rotation de 90° et Dualité

Tx Ty

1

2

3

4

5

6

7

8

9

10

5

3

4

9

7

8

10

6

1

2

-1

Remarque

Liens étroits avec l’algorithme de dessin de [di Battista et al. 92]

Treillis des orientations bipolaires

• Thm [Ossona de Mendez 94] : l’ensembles des orientations bipolaires d’une carte a une structure de treillis distributif. La relation de couverture est la suivante :

LOP ROP

Corollaire : les cartes 2-connexes sont en bijection avec les bipolaires sans LOPLemme : les cartes séries-parallèles sont en bijection avec les bipolaires sans LOP ni ROP.

Orientationsbipolaires

Orientations Min

Cartes 2-connexes

Orientation Min&Max

Cartes séries-parallèles

Spécialisations de

Baxter Sn(2413,3142)Baxter Sn(2413)

[Dulucq Gire West 96] [Gire 93]

• Lemme : () contient un LOP contient 41352 () contient un ROP contient 25314

• Permutations de Baxter alternantes 2n (2n+1)– Enumérées par Cn.Cn

(Cn.Cn+1 )[Cori Dulucq Viennot’86] [Dulucq Guibert’98]

• Permutations de Baxter doublement alternantes 2n (2n+1)– Enumérées par Cn

[Guibert Linusson’00]

Perspectives

Travaux en cours

• Orientations mono-source– Involutions de Baxter– Liens avec les cartes

Eulériennes