Combinatoire dans des stabilisations du modèle du tas de ...Lemodèledutasdesable Tasdesable[Bak,Tang,Wiesenfeld87] éboulement gauche Uneconﬁgurationestladonnéedunombredegrainsparsommet

Combinatoire dans des stabilisations du modèle du tas desable sur la grille Z2

Soutenance de thèse

Henri Derycke

encadré par Yvan Le Borgneaprès avis de Sylvie Corteel et Gilles Schaeffer

le 10 décembre 2018

Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]

éboulementgauche

Une configuration est la donnée du nombre de grains par sommet.

Un sommet est instable s’il a plus de grains que de voisins, et stable sinon.L’ordre des éboulements ne change pas le résultat.Stabilisation : tant qu’il existe un sommet instable, l’ébouler

Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29


éboulement

éboulementgauche

Une configuration est la donnée du nombre de grains par sommet.Un sommet est instable s’il a plus de grains que de voisins, et stable sinon.

L’ordre des éboulements ne change pas le résultat.Stabilisation : tant qu’il existe un sommet instable, l’ébouler



éboulement

éboulementgauche





éboulement

éboulementgauche





éboulement

éboulementgauche

éboulementdroit





éboulement

éboulementgauche

éboulementdroit





éboulement

éboulementgauche

éboulementdroit

Une configuration est la donnée du nombre de grains par sommet.Un sommet est instable s’il a plus de grains que de voisins, et stable sinon.L’ordre des éboulements ne change pas le résultat.

Stabilisation : tant qu’il existe un sommet instable, l’ébouler



éboulement

éboulementgauche

éboulementdroit

Une configuration est la donnée du nombre de grains par sommet.Un sommet est instable s’il a plus de grains que de voisins, et stable sinon.L’ordre des éboulements ne change pas le résultat.Stabilisation : tant qu’il existe un sommet instable, l’ébouler



4

0

1

1

1

0

2

1

1

2

1

0

0

2

1

3

1

0

1

2

1

1

2

0

3

1

1

0

2

0

éboulement

éboulementgauche

éboulementdroit

Une configuration est la donnée du nombre de grains par sommet.Un sommet est instable s’il a plus de grains que de voisins, et stable sinon.L’ordre des éboulements ne change pas le résultat.Stabilisation : tant qu’il existe un sommet instable, l’ébouler


Le modèle du tas de sable La pile de sable

n

I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]I Convergence en densité [Pegden, Smart 12]



n

Source : Page personnelle de W.Pegden, n = 213




n





n


I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]

I Convergence en densité [Pegden, Smart 12]



n


I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]

I Convergence en densité [Pegden, Smart 12]



n





Couleurs :

0123

n = 106

Comportement avec moins de structureMotif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]



Couleurs :

0123

n = 106




Couleurs :

0123

Comportement avec moins de structure

Motif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]



Couleurs :

0123

n = 106




Couleurs :

0123





Couleurs :

0123




Mes travaux de thèse

Ch.II

I Approximation du comportement parplusieurs simplifications

I Hiérarchie de problème dont certains fontintervenir des permutations

I Résultat de positivité de polynômesénumérant des permutations.

Ch.IV&V

I Zone périodique ⇒ Configuration périodiqueI Parallèle avec les propriétés des graphes finis

Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III

I Construction explicite d’un automatereconnaissant des configurations récurrentes

I Contrôle de sa taille



Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





Ch.II




Ch.IV&V


Z

H1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0 Ch.III





1 Le modèle du tas de sable

2 La récurrence connue dans les graphes finis

3 Récurrentes périodiques sur Z2

4 Le cas de la bande biinfinie

5 Contributions et ouvertures


La récurrence connue dans les graphes finis


2 La récurrence connue dans les graphes finisPuitsLes configurations récurrentesCritère de Dhar





La récurrence connue dans les graphes finis Puits

Comment peut on stabiliser la configuration suivante ?

2

3

2

2

3

2

9

2

0

1

2

1

Stabilisation

On choisit un sommet dont on interdit l’éboulement lors de la stabilisation

Ce puits garantit la terminaison de la stabilisation




2

3

2

2

3

2

9

2

0

1

2

1

Stabilisation






2

3

2

2

3

2

9

2

0

1

2

1

Stabilisation




La récurrence connue dans les graphes finis Les configurations récurrentes

Critère de DharUne configuration stable est récurrente si l’éboulement du puits suivi d’unestabilisation la laisse invariante. Le cas échéant, chaque sommet s’ébouleexactement une fois.

2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P

Théorème [Dhar 90]

Les configurations récurrentes forment un groupe abélien pour la loi sommesuivie de la stabilisation




2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

P

0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

PX 0

0

1

3

2P

0

1

2

0

1

P






2

0

1

2

1

P

0

2

1

3

2P

0

1

0

1

4

P

1

1

1

1

2

P

1

1

2

02

P

2

0

1

2

1

P

2

0

1

0

1

PX 0

0

1

3

2P

0

1

2

0

1

P




La récurrence connue dans les graphes finis Critère de Dhar


Bijections entre les arbres couvrants et les configurations récurrentes(Dhar/Majumdar 92, Cori/Le Borgne 03 (CLB), Bernardi 06).

P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P

Marquer les arêtes incidentes au puits comme pendantes.Tant qu’il existe au moins une arête pendante

Prendre la plus proche du puitsTransférer le ou les grains en attente dessusSi le sommet devient instable, l’ébouler et marquerses arêtes non traitées comme pendantes.

Parcours sommet-arête :

I Pour chaque sommet, le nombre de ses arêtes incidentes qui le suiventcomptent son nombre de grains.

I Les arêtes précédant un sommet décrivent un arbre couvrant.





P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P ••



Parcours sommet-arête :







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P •



Parcours sommet-arête : e1,

e2,

v2,

e3,

e5,

v4,

e6,

v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P



Parcours sommet-arête : e1, e2,

v2,

e3,

e5,

v4,

e6,

v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P ••



Parcours sommet-arête : e1, e2, v2,

e3,

e5,

v4,

e6,

v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P•



Parcours sommet-arête : e1, e2, v2, e3,

e5,

v4,

e6,

v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P



Parcours sommet-arête : e1, e2, v2, e3, e5,

v4,

e6,

v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P ••



Parcours sommet-arête : e1, e2, v2, e3, e5, v4,

e6,

v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P•



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6,

v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P•

• •



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3,

e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P•

•



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4,

v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P•

•



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1,

e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P•



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7,

v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P•

•



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5,

e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P •



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8,

v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P ••



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6,

e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6, e9







P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P










P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P










P

v2

v1

v4

v3

v6

v5

e1

e2e3

e4

e5

e6

e7

e8

e9P



Parcours sommet-arête : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6,

e9




Récurrentes périodiques sur Z2


2 La récurrence connue dans les graphesfinis


Placement du puitsCritère de Dhar affaibliBijectionComptageGroupe des récurrentes bipériodiques




Récurrentes périodiques sur Z2 Placement du puits

Zone périodique traversée par des éboulements laissée presque invariante ⇒récurrence ?

Heuristique : localement, l’éboulement du puits se comporte commel’éboulement d’un demi plan










































Récurrentes périodiques sur Z2 Critère de Dhar affaibli

Définition (Critère de Dhar affaibli [D., Le Borgne 2018])

Une configuration est récurrente dans une direction ~s ∈ Q2 (non nulle) sil’éboulement forcé de tout demi-plan orthogonal à ~s entraine l’éboulementpar stabilisation de tous les autres sommets.

Direction ~s du puits

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2






2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4





+1


2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

1 3

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4

0 4



Théorème [D., Le Borgne 2018]

Le critère se calcule en temps fini sur les configurations bipériodiques, bornéen fonction de la taille de la période et de la direction ~s.

ligne debalayage

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

I Périodicité du comportement du critère orthogonalement au puitsI Ultimement périodique ensuite et ne dépend pas de la position du demi

plan de départ





ligne debalayage

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage

Zone gelée

Zone detravail32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage

Zone gelée

Zone detravail

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage

Zone gelée

Zone detravail

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage

Zone gelée

Zone detravail

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

3 0


plan de départ





ligne debalayage

Zone detravail

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0


plan de départ





ligne debalayage

Zone detravail

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

I Périodicité du comportement du critère orthogonalement au puits

I Ultimement périodique ensuite et ne dépend pas de la position du demiplan de départ





ligne debalayage

Zone detravail

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0

32

3 2

3

33

133

3

3 3

0

3

1

1

1 1

0

1

3

1

1 0


plan de départ



ligne de balayage


Récurrentes périodiques sur Z2 Bijection

Forêt couvrante du tore enracinéesur des cycles non contractiles et depente (4,−3)

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

Forêt périodique enracinée dans le demi-plan

Forêt couvrante du tore de pente(1, 0) non compatible avec une direc-tion verticale


Les configurations bipériodiques récurrentes dans une direction du puits ~ssont en bijection avec les forêts bipériodiques dont les branches infinies vontvers le puits.




3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1








3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1








3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

Forêt bipériodique de chemins infinis vers le puits







3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1








3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1








3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1

3

0

3

0

3

3

1

3

1

3

3

1






Récurrentes périodiques sur Z2 Comptage

3

0

3

0

3

3

1

3

1

3

3

1

Formule déterminantale de [Kenyon 17]

Raffinement par pente des chemins infinis

k · j k · i0 1 2 3 4

0 31300528 541732 1528 11 31300528 5427200 31232 42 541732 31232 63 1528 44 1

Table – Nombre de forêts enracinées sur k cycles non contractiles de pente (i , j)sur le tore T4,4

Calcul jusqu’à W ,H ≤ 9Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 17 / 29

Récurrentes périodiques sur Z2 Groupe des récurrentes bipériodiques

Difficulté : puits à l’infini ⇒ comment stabiliser ?

3 3

2 3

3 3

1 3

6 6

3 6+ =

3 3

0 3∼

Puits

+1 −1

Donne une définition de groupe mais :éléments du groupe 6= configurations récurrentes dans une direction




3 3

2 3

3 3

1 3

6 6

3 6+ =

3 3

0 3∼

Puits

+1 −1





3 3

2 3

3 3

1 3

6 6

3 6+ =

3 3

0 3∼

Puits

+1 0 −1





3 3

2 3

3 3

1 3

6 6

3 6+ =

3 3

0 3∼

PuitsOpérateurd’arrachage

−10000





3 3

2 3

3 3

1 3

6 6

3 6+ =

3 3

0 3∼

Puits

Opérateurd’arrachagepériodique

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1





3 3

2 3

3 3

1 3

6 6

3 6+ =

3 3

0 3∼

Puits

Opérateurd’arrachagepériodique

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1

−1



Le cas de la bande biinfinie


2 La récurrence connue dans les graphesfinis


4 Le cas de la bande biinfinieRécurrenceDécomposition du parcourssommet-arêteCaractérisation des décompositionsAutomate


H = 3

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0


Le cas de la bande biinfinie Récurrence

Puits placé à l’infini à gaucheΛ∞,H

H = 3

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0

0

3

2

W

ΛW+1,H

P

2

1

0

2

1

2

2

3

1

2

3

2

0

0

0

[Járai, Lyons 07]I Mesure sur les facteurs des

configurations récurrentesI Description par un automate (existence)

21

2|2|11|2|2

12

22

20

02

22

Proposition [D. 2018]

Les facteurs finis des configurations récurrentes à gauche de la bande ΛH

sont les facteurs des configurations récurrentes des graphes finis(ΛW ,H)W>0.




H = 3

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0

0

3

2

W

ΛW+1,H

P

2

1

0

2

1

2

2

3

1

2

3

2

0

0

0



21

2|2|11|2|2

12

22

20

02

22







H = 3

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0

0

3

2

W

ΛW+1,H

P

2

1

0

2

1

2

2

3

1

2

3

2

0

0

0



21

2|2|11|2|2

12

22

20

02

22





Le cas de la bande biinfinie Décomposition du parcours sommet-arête

Arête x

Sommet yS

1

2

4

9

10

12

15 19

2325 28

30

353739

41

43

45

49

51

52

54

58

61

65

66

67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64

• Décomposition1 1

2 2

4 4

9 9

10 10

12 12

15 15 19 19

23 2325 25 28 28

30 30

35 3537 3739 39

41 41

43 43

45 45

49 49

51 51

52 52

54 54

58 58

61 61

65 65

66 66

67 67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64

• Standardisation(→ alphabet fini)

1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

• Extraction de laconfiguration

131

030

131

231

232

231

201

232

CLB

CLB



Arête x

Sommet yS

1

2

4

9

10

12

15 19

2325 28

30

353739

41

43

45

49

51

52

54

58

61

65

66

67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64


2 2

4 4

9 9

10 10

12 12

15 15 19 19

23 2325 25 28 28

30 30

35 3537 3739 39

41 41

43 43

45 45

49 49

51 51

52 52

54 54

58 58

61 61

65 65

66 66

67 67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64


1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7


131

030

131

231

232

231

201

232

CLB

CLB



Arête x

Sommet yS

1

2

4

9

10

12

15 19

2325 28

30

353739

41

43

45

49

51

52

54

58

61

65

66

67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64


2 2

4 4

9 9

10 10

12 12

15 15 19 19

23 2325 25 28 28

30 30

35 3537 3739 39

41 41

43 43

45 45

49 49

51 51

52 52

54 54

58 58

61 61

65 65

66 66

67 67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64


1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7


131

030

131

231

232

231

201

232

CLB

CLB



Arête x

Sommet yS

1

2

4

9

10

12

15 19

2325 28

30

353739

41

43

45

49

51

52

54

58

61

65

66

67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64


2 2

4 4

9 9

10 10

12 12

15 15 19 19

23 2325 25 28 28

30 30

35 3537 3739 39

41 41

43 43

45 45

49 49

51 51

52 52

54 54

58 58

61 61

65 65

66 66

67 67

5

7

13

14

17

18

21

27

32

33

46

47

53 56

59633

6

8

11 16 20

222426 29

31

34363840

42

44

48

50 55

57

6062

64


1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7


131

030

131

231

232

231

201

232

CLB

CLB


Le cas de la bande biinfinie Caractérisation des décompositions

1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2

v3

I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .

I Dernier ordre induit : . . . e6e7e8I Suite d’ordres induits compatibles deux à deux

ΛW ,H

P

0

0

0



1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2

v3I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .


ΛW ,H

P

0

0

0



1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2


I Dernier ordre induit : . . . e6e7e8

I Suite d’ordres induits compatibles deux à deux

ΛW ,H

P

0

0

0



1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2





1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2



Caractérisation des facteurs de taille 2Deux ordres induits sont consécutifs si etseulement siI les ordres des arêtes communes sont

identiquesI les arêtes communes (horizontales) ne sont

pas traitées après leur deux extrémités.

1 5

68

911

1

5 7

8

911

3

4

3

6

2

7

10

2

4

10

=

=

=

2

3

2

3

1 1

−→2

−→3

−→2

−→3

←−1←−1



1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2






1 5

68

911

1

5 7

8

911

3

4

3

6

2

7

10

2

4

10

=

=

=

2

3

2

3

1 1

−→2

−→3

−→2

−→3

←−1←−1



1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2






1 5

68

911

1

5 7

8

911

3

4

3

6

2

7

10

2

4

10

=

=

=

2

3

2

3

1 1

−→2

−→3

−→2

−→3

←−1←−1



1

2

4

9

10

11

1

2

4

7

8

10

1 5

68

911

1

5 7

8

911

1

3

8

9

10

11

1

3

5

9

10

11

1

3

4

6

7

8

1

5

8

9

10

11

5

7

5

6

3

4

3

6

5

6

6

7

5

10

3

63

6

8

3

9

11

2

7

10

2

4

10

2

4

7

2

4

8

2

9

11

2

4

7

e1

e2

e3

e6

e7

e8

e4

e5

v1

v2






1 5

68

911

1

5 7

8

911

3

4

3

6

2

7

10

2

4

10

=

=

=

2

3

2

3

1 1

−→2

−→3

−→2

−→3

←−1←−1


Le cas de la bande biinfinie Automate

Automate sur les ordres induitsI Alphabet des ordres induitsI États : les ordres induitsI Transitions : o o′−→ o ′ si oo ′ est un facteur correctI Un état initial et plusieurs finaux

Automate ]États ]AlphabetJárai/Lyons (2H)2

H(2H)2

H

induit (4H − 1)! (4H − 1)!

réduit 2HH! (4H − 1)!Conjecture Gamlin βH

1

5 7

8

911

3

6

4

10

2

−→2

−→3

−→3

←−1

←−2

←−1

Ordre réduit à droite



Automate sur les ordres induitsI Alphabet des ordres induitsI États : les ordres induitsI Transitions : o o′−→ o ′ si oo ′ est un facteur correctI Un état initial et plusieurs finaux


H(2H)2

H

induit (4H − 1)! (4H − 1)!

réduit 2HH! (4H − 1)!Conjecture Gamlin βH

1

5 7

8

911

3

6

4

10

2

−→2

−→3

−→3

←−1

←−2

←−1




Automate sur les ordres induitsI Alphabet des ordres induitsI États : les ordres réduits à droiteI Transitions : rg (o)

o−→ rd(o) pour tout ordre induit o

I Un unique état initial et final : de bas en haut←−1 ,←−2 , . . . ,

←−H


H(2H)2

H

induit (4H − 1)! (4H − 1)!réduit 2HH! (4H − 1)!

Conjecture Gamlin βH

1

5 7

8

911

3

6

4

10

2

−→2

−→3

−→3

←−1

←−2

←−1




Automate sur les ordres induitsI Alphabet des ordres induitsI États : les ordres réduits à droiteI Transitions : rg (o)

o−→ rd(o) pour tout ordre induit o

I Un état initial et final : de bas en haut←−1 ,←−2 , . . . ,

←−H


H(2H)2

H

induit (4H − 1)! (4H − 1)!réduit 2HH! (4H − 1)!Conjecture Gamlin βH

1

5 7

8

911

3

6

4

10

2

−→2

−→3

−→3

←−1

←−2

←−1




Pas de caractérisation combinatoire des ordres induits mais :

I Construction depuis les arbres couvrants

P


Tout ordre induit apparait dans la décomposition d’une configurationrécurrente de largeur 2H + 3.

I Sous ensemble d’ordres induits en bijection avec les permutationsséparables donc en αH

Projection de l’alphabet des ordres induits sur les colonnes de grains par labijection CLB.



Pas de caractérisation combinatoire des ordres induits mais :I Construction depuis les arbres couvrants

P








P








P








P







0212

8132

9

1|22|02|2

11

232

4

222

1|1|12|3|32|1|2

2|10|12|2

2|2|22|3|32|2|12

12

5

230

7

130

132

1|22|12|2

2322

22

0|0|03|3|22|1|2

0|11|02|2

2|2|1|1|1|2|2|22|3|3|2|3|2|1|32|2|2|2|1|1|2|1

112

1

211

1|2|23|3|20|0|0

122|21|00|1

3

202

030

212

032

2|00|22|2

2|13|32|2

222

2

122

2|23|32|1

222

230

6

221

10

212

2|20|22|0

032

2|2|12|3|32|2|2

212

2|1|22|3|31|1|1

2|20|12|1

031

2|23|32|1

222

230

221

2|21|22|0

232

222

231

212

2|22|01|2

232

222

231

2|22|11|2

032

2|01|22|2

2|13|32|2

222

122

032

1|01|22|2

2|2|1|22|3|3|32|2|2|1

122

221

230

2|21|21|0

212

132

232

231

131



0 2131

33

2230

70

2|23|33|31|2

64

2|23|32|10|2

9

2032

43

2330

46

2222

17

2322

50

2232

19

2321

22

2132

562|2|2|2|22|2|0|0|11|2|3|2|32|0|1|2|0

25

2122

58

2221

63

2231

2231

2|23|32|32|2

2|23|30|12|1

2032

2|23|32|31|1

2312

2232

2132

2|2|2|20|2|0|23|1|2|01|1|2|2

2|21|12|32|1

1

2222

37

2221

53

2212

2120

1|1|2|1|2|2|1|2|2|2|2|2|2|2|2|1|1|2|2|1|13|2|2|2|2|1|3|3|1|2|2|3|3|1|2|3|2|3|3|3|32|3|3|3|3|3|3|3|2|2|2|3|2|3|1|3|2|1|2|2|11|1|2|2|1|1|1|2|2|1|2|1|2|2|2|2|2|2|1|2|2

2|1|1|2|2|23|3|3|2|2|30|0|1|0|1|11|1|0|1|0|0

2021

2|1|1|2|2|1|2|23|3|2|2|3|3|2|12|3|3|3|3|2|2|30|0|0|0|0|0|0|0

2111

2|2|12|3|31|1|11|1|1

2121

2|2|2|21|0|1|00|2|1|11|0|0|1

49

2|1|23|3|20|0|02|2|2

320|1|1|0|0|11|0|0|1|1|03|3|3|2|3|21|2|1|2|2|2

65

0|1|1|01|1|0|21|0|1|02|2|2|2

12

0|0|0|0|0|0|0|03|2|3|3|2|3|3|23|2|2|3|3|2|1|32|2|2|1|1|1|2|2

13

1|1|11|1|12|3|32|2|1

14

2|2|20|0|03|3|22|1|2

21

1212

7

1202

62

0212

4

0|11|03|30|0

73

1130

31

0|0|03|2|33|3|20|0|0

35

1112

66

0|03|31|00|1

72

0302

36

0311

27

2112

48

2|21|00|12|2

75

2030

2131

2|1|22|3|33|3|32|2|2

1|2|2|2|2|13|2|2|3|3|32|1|2|1|2|11|2|1|2|1|2

2032

2|2|12|3|33|3|31|1|1

2122

2|1|23|3|22|2|22|2|2

2132

2|2|2|20|1|0|13|2|2|11|1|2|2

0332

0331

0|03|31|22|1

0322

2230

2|23|33|31|2

2|23|30|22|0

2132

2330

2322

2232

2321

2|2|2|22|1|2|12|1|0|30|2|2|0

2|22|12|31|1

2231

23

2122

71

2212

47

2222

29

2312

2121

2|1|2|2|2|2|1|12|2|2|3|3|1|3|33|3|2|3|2|3|3|22|2|2|2|2|2|2|2

1|2|2|2|2|13|2|3|2|3|30|1|0|0|1|12|1|2|2|1|1

2022

1|1|2|2|1|2|2|23|2|2|3|3|1|2|32|3|2|3|3|3|3|21|1|1|1|1|1|1|1

2112

2|1|22|3|31|1|12|2|2

2122

2|2|2|21|1|0|00|1|1|22|1|2|1

1|00|13|32|2

0|0|03|2|33|3|22|2|2

1132

2032

0|11|03|31|1

1131

0|0|03|3|23|2|31|1|1

0|03|31|01|2

0312

2031

2131

2230

2|23|33|31|2

2|23|30|22|0

2032

2330

2222

2322

2232

2321

2132

2|2|2|2|22|2|0|0|10|2|3|2|32|0|1|2|0

2122

2221

2231

2312

41

2212

2130

2|2|2|1|1|22|3|3|3|3|23|3|3|3|3|32|2|1|1|2|1

1|2|1|2|2|23|3|3|2|3|20|0|2|0|2|22|2|0|2|0|0

2032

2|1|22|3|33|3|30|0|0

2|1|23|3|22|2|22|2|2

2132

1|2|23|3|22|2|21|1|1

2|2|2|21|0|0|12|1|3|00|2|0|2

2|20|13|21|1

2131

2022

2112

0|03|33|32|1

0330

2122

2|1|22|3|31|1|12|2|2

0|03|30|22|0

0322

16

0312

30

0321

2230

2|2|2|2|23|3|3|3|32|2|3|1|31|2|1|2|2

2|23|30|11|0

2032

2|23|32|30|0

2311

2232

2132

2|2|2|2|22|0|0|1|21|1|3|0|00|2|0|2|1

2130

2031

2231

2220

2302

2211

60

2221

2

2|22|21|22|2

2022

24

2122

52

2202

2112

68

2131

2130

2|2|2|1|1|22|3|3|3|3|23|3|3|3|3|32|2|1|1|2|1

2|1|2|2|2|12|3|3|3|2|31|2|1|2|2|12|0|2|0|0|2

2032

2|1|22|3|33|3|30|0|0

2122

2|1|23|3|22|2|22|2|2

2132

1|2|23|3|22|2|21|1|1

2|2|2|21|0|0|12|3|2|10|0|2|2

2|20|13|21|1

2131

0|03|33|32|1

0330

0|03|31|22|0

0322

0321

2230

2|23|33|31|2

2|23|30|22|0

2032

2330

2322

2232

2321

2132

2|2|2|20|0|1|21|3|0|22|0|2|0

2130

2|20|23|21|1

2231

2022

2|21|22|12|2

2112

52202

2222

2312

2131

2231

2332

2|23|32|11|2

2132

2331

2222

2322

2232

2|2|2|21|2|2|12|1|2|32|2|1|1

2231

2332

2|23|32|11|2

2032

2331

2222

2322

2232

2132

2|2|2|22|0|2|01|3|2|22|1|1|2

2|21|12|32|1

2230

2|23|33|31|2

2|23|32|10|2

2132

2330

2222

2322

2232

2321

2|2|2|21|2|2|12|1|2|32|2|0|0

2|22|12|31|1

2231

2230

2|2|2|2|23|3|3|3|32|2|3|1|31|2|1|2|2

2|23|30|11|0

2032

2|23|32|30|0

2311

2232

2132

2|2|2|22|0|0|21|3|2|00|0|2|1

2|21|12|32|0

2031

2231

2222

34

2202

2220

2302

2211

2|22|21|22|1

2131

2131

2230

2|2|2|2|23|3|3|3|32|2|3|1|31|2|1|2|2

2|23|30|11|0

2032

2|23|32|30|0

2311

2232

2132

2|2|2|2|22|0|0|2|11|3|2|0|30|1|2|1|0

2122

2231

2222

2202

2220

2302

2211

2|22|21|22|1

2230

2|2|23|3|32|3|32|1|2

2|23|32|10|1

2132

2330

2321

2232

2|2|2|21|2|2|12|1|2|32|1|0|0

2131

2231

2222

2212

2312

2221

2231

2|23|32|32|2

2|23|30|12|1

2132

2|23|32|31|1

2312

2232

2|2|2|21|2|2|12|1|0|32|1|2|1

2222

2221

2212

2130

2|1|1|2|2|2|2|2|1|2|12|2|3|2|3|3|3|1|3|2|33|3|3|2|3|3|2|3|3|3|22|2|1|2|2|1|2|2|2|1|2

2|1|2|2|2|12|3|3|2|3|31|2|2|2|1|11|0|0|0|1|1

2031

2|1|22|3|33|3|30|0|0

2121

1|2|23|3|22|2|21|1|1

2131

2|2|2|20|1|1|03|1|2|20|1|0|1

2|1|22|3|31|1|12|2|2

1|00|13|32|2

1|0|0|10|2|1|12|1|2|12|2|2|2

0|0|0|03|3|2|33|3|3|22|1|2|2

1132

2032

1222

1212

0222

0330

1122

0|03|31|21|0

0312

0321

2122

2|20|12|12|2

2230

2|23|33|31|2

2|23|30|22|0

2132

2330

2222

2322

2232

2321

2|2|2|21|2|2|12|2|0|32|0|2|0

2|22|12|31|1

2231

2312

2212

2230

2|2|2|2|23|3|3|3|32|2|3|1|31|2|1|2|2

2|23|30|11|0

2132

2|23|32|30|0

2311

2232

2|2|2|21|2|2|12|1|0|32|0|1|0

2131

2231

2222

2202

2220

2302

2211

2|22|21|22|1

2131

2230

2|2|2|2|23|3|3|3|32|2|3|1|31|2|1|2|2

2|23|30|11|0

2032

2|23|32|30|0

2311

2232

2132

2|2|2|2|2|20|0|1|2|2|11|3|0|0|1|32|1|2|1|0|0

2231

2220

2302

2211

2221

2|22|21|22|2

2022

2122

2202

2112

2231

2332

2|23|30|22|1

2132

2331

2322

2232

2|2|2|22|2|1|12|0|3|11|2|1|2

2122

2212

2222

2312

2231

2332

2|23|30|22|1

2032

2331

2322

2232

2132

2|2|2|21|0|2|00|3|2|12|1|1|2

2131

2022

2|21|22|12|2

2112

2202

2222

2312

2131

2230

2|2|23|3|32|3|32|1|2

2|23|32|10|1

2032

2330

2321

2232

2132

2|2|2|2|2|20|1|0|2|2|13|1|2|1|2|31|2|2|1|0|0

2231

2312

2221

2222

2212

2122

2231

2332

2|23|30|22|1

2032

2331

2222

2322

2232

2132

2|2|2|20|2|0|23|2|2|01|1|2|2

2|21|12|32|1

2312

2212

3

2|1|2|1|22|2|1|3|33|3|3|3|32|2|2|2|2

2222

1|00|13|32|2

1|0|1|2|03|3|0|2|10|1|2|0|22|2|2|2|2

39

2|11|22|22|2

44

2312

11

1122

0|03|23|32|2

1132

2032

45

2212

18

1322

67

0222

2322

2302

262022

28

1312

0322

2|2|23|3|32|3|32|1|2

2330

1|1|2|2|2|12|2|1|1|1|23|2|2|3|3|31|2|2|2|1|2

1|2|2|13|1|2|20|1|0|12|2|2|2

1|1|13|3|32|3|32|1|2

2|2|22|2|23|3|21|2|2

2312

2302

1312

1|22|13|30|0

2230

1330

2212

2332

1|22|13|32|2

2|2|1|11|2|3|22|1|1|22|2|2|2

1332

2232

2322

2312

1322

2222

2|1|2|1|22|2|1|3|33|3|3|3|32|2|2|2|2

2222

1|00|13|32|2

2|0|1|02|3|0|11|1|2|22|2|2|2

2|11|22|22|2

1122

0|03|23|32|2

1132

2032

1322

0222

2322

2312

2022

0322

42

1312

1|23|33|32|2

2|00|23|32|2

0|2|2|02|1|0|32|0|1|02|2|2|2

2312

0332

2232

0312

1322

2322

2302

0322

74

2132

40

1232

1|13|20|22|2

15

2202

20

2222

57

2112

59

2|21|22|12|2

10 1312

61

2022

1|23|33|32|2

2|00|23|32|2

2|0|0|22|2|3|01|2|1|22|2|2|2

0332

2232

1322

2322

2312

0322

2132

1232

1|13|21|22|2

2222

69

2122

2|2|2|2|2|2|2|22|2|3|3|3|3|2|33|2|3|3|2|1|3|22|2|2|1|2|2|1|1

2|23|30|11|0

2|2|22|3|33|2|30|0|0

2311

2302

1|2|2|2|1|11|0|0|0|1|12|3|3|2|3|32|1|2|2|1|2

2|1|2|11|2|0|10|0|1|12|2|2|2

1|1|1|1|1|1|1|13|2|2|3|3|2|3|32|3|3|3|3|2|2|11|1|2|2|1|2|2|2

2|2|21|1|12|3|32|2|1

2212

2202

1212

2|10|13|30|0

2130

1|1|12|3|33|3|20|0|0

2112

1|13|30|11|0

1302

1311

2|2|2|1|1|13|3|3|3|3|32|3|3|3|3|22|2|1|1|2|2

1|23|33|30|0

0|2|2|2|0|02|0|0|0|2|22|3|3|2|3|32|1|2|2|1|2

2|2|0|00|1|3|21|0|0|12|2|2|2

0|0|03|3|33|3|22|1|2

2|2|22|2|23|3|21|2|2

1312

2312

2302

0312

2|00|23|30|0

2230

0330

6

2130

2|2|21|1|12|3|32|2|1

1|1|12|2|23|3|21|2|2

1|13|20|12|2

2202

2212

2112

51

1230

2220

2|2|2|2|2|2|1|1|2|2|12|2|3|2|3|3|3|3|3|3|33|3|3|2|3|2|3|3|1|2|21|2|2|2|1|2|1|2|2|1|2

2|23|30|11|0

2121

2|2|1|22|3|3|33|2|3|30|0|0|0

2211

2311

2221

2|2|2|22|1|1|21|1|2|00|1|0|1

2302

0|1|1|0|1|02|1|1|2|1|22|2|3|3|3|32|2|2|1|1|2

0|1|1|03|2|1|20|0|1|12|2|2|2

0|0|03|3|33|3|22|1|2

1|1|12|2|23|3|21|2|2

2|2|21|1|12|3|32|2|1

1312

1302

0312

0|12|13|30|0

1230

0330

1212

2212

2|22|10|12|2

2130

2332

1|22|13|32|2

2|1|2|11|3|2|22|0|0|22|2|2|2

2312

1332

2232

2|12|31|12|2

2322

2302

1322

2222

2|1|2|1|22|2|1|3|33|3|3|3|32|2|2|2|2

2222

1|00|13|32|2

0|1|2|03|0|2|10|2|0|22|2|2|2

2|11|22|22|2

2312

1122

0|03|23|32|2

1132

2032

2|02|31|12|2

1322

0222

2322

2302

2022

0322

1302

1312

2|22|33|32|2

2222

2|10|13|32|2

2|1|1|22|1|3|01|2|1|22|2|2|2

2122

1|12|33|32|2

2132

1222

2322

2312

1322

2|1|2|1|22|2|1|3|33|3|3|3|32|2|2|2|2

1|00|13|32|2

2|2|1|0|00|1|0|3|11|0|2|0|22|2|2|2|2

1222

2312

1122

0|03|23|32|2

1132

2032

0312

1322

0222

2322

2302

0322

1302

2202

2112

8

2|21|22|22|2

55

2022

2212

1312

1|23|33|32|2

2|00|23|32|2

0|0|2|22|3|0|12|1|2|12|2|2|2

0332

2232

1322

2322

2312

0322

2132

1232

1|13|21|22|2

2212

2222

2122

2|1|22|3|33|3|32|2|2

2222

1|01|23|32|2

2|1|0|02|1|3|21|2|1|22|2|2|2

1222

0332

1232

2132

1322

2322

2312

2122

0322

1312

1|23|33|32|2

0|22|13|32|2

2|1|0|2|01|3|3|2|22|0|1|0|22|2|2|2|2

2312

0332

2232

2212

1322

2322

2302

1312

0322

1232

1222

2222

2|22|33|32|2

2222

2|10|13|32|2

2|1|2|12|1|0|30|2|2|02|2|2|2

2312

2122

1|12|33|32|2

2132

2|12|31|12|2

1222

2322

2302

1322

2332

2331

1|22|13|32|2

1332

2232

1|22|13|31|1

2231

1331

1|23|33|32|2

2|13|33|31|1

2|00|23|32|2

0332

2232

2|00|23|31|1

2231

0331

2131

2132

1232

1231

2|2|22|3|33|2|32|2|2

2|23|30|12|1

2|2|23|3|22|3|31|1|1

2312

2|10|13|32|2

1|1|13|3|22|3|32|2|2

2132

2|10|13|31|1

2131

1|1|13|2|32|3|31|1|1

1|13|30|12|1

1312

2231

2332

2|23|32|11|2

2032

2331

2322

2232

2132

2|2|2|20|2|0|13|2|2|11|1|2|2

2131

2122

2212

2222

2131

2230

2|23|33|31|2

2|23|30|22|0

2032

2330

2322

2232

2321

2132

2|2|2|2|20|1|0|2|11|0|3|2|32|2|1|0|0

2221

2231

2022

2|21|22|12|2

2112

2202

2222

2312

2332

2331

2|10|23|32|2

1332

2232

1|22|03|31|1

2231

1331

2131

2132

2|2|23|3|32|3|32|1|2

2330

1|2|2|2|1|12|0|0|0|2|23|3|3|2|2|31|1|2|2|2|2

1|2|2|13|1|0|20|0|1|12|2|2|2

1|1|13|3|32|3|32|1|2

2|2|22|2|23|3|21|2|2

2312

2302

1312

1|22|03|30|0

2230

1330

2130

2|2|21|1|12|3|32|2|1

2202

2212

2112

2|2|2|1|1|13|3|3|3|3|32|3|3|3|3|22|2|1|1|2|2

1|23|33|30|0

0|2|2|2|0|02|1|1|1|2|22|2|3|3|3|32|2|2|1|1|2

0|2|0|23|2|2|10|0|1|12|2|2|2

0|0|03|3|33|3|22|1|2

2|2|22|2|23|3|21|2|2

1312

2312

2302

0312

0|22|13|30|0

2230

0330

1|1|12|2|23|3|21|2|2

1|13|20|12|2

2212

1230

1|23|33|32|2

0|22|13|32|2

2|0|2|01|2|2|32|2|1|12|2|2|2

0332

2232

1322

2322

2312

0322

1232

1|13|21|22|2

2222

2332

2|10|23|32|2

1|2|1|23|0|2|11|2|2|12|2|2|2

1332

2232

2322

2312

1322

2132

2212

2222

2122

1|23|33|32|2

2|00|23|32|2

1|2|0|2|03|1|3|0|20|0|1|1|22|2|2|2|2

2312

0332

2232

1322

2322

2302

1312

0322

2132

1232

1222

2202

2222

2112

2|21|22|12|2

2022

2332

2|10|23|32|2

1|2|1|23|0|2|20|2|2|02|2|2|2

2312

1332

2232

2|12|31|12|2

2322

2302

1322

2132

2222

2122

2|1|2|1|22|2|1|3|33|3|3|3|32|2|2|2|2

1|00|13|32|2

1|2|2|0|0|13|1|0|1|3|00|0|1|2|1|22|2|2|2|2|2

1222

2312

1122

0|03|23|32|2

1132

2032

1322

0222

2322

2302

1312

0322

2202

2112

2|21|22|22|2

2022

2212

2|1|22|3|33|3|32|2|2

1|01|23|32|2

0|1|2|2|1|02|1|1|2|3|32|2|1|0|0|12|2|2|2|2|2

2312

1222

0332

1232

2132

1322

2322

2302

1312

0322

2212

2222

2122

2332

2|10|23|32|2

1|2|2|13|1|0|20|0|1|22|2|2|2

2312

1332

2232

1312

2322

2302

1322

2132

2202

2222

2112

2|21|22|12|2

2022

2131

2|1|22|3|33|3|32|2|2

1|1|2|2|2|23|3|3|2|2|32|0|0|2|0|21|2|2|1|2|1

2032

2|2|12|3|33|3|31|1|1

2|1|23|3|22|2|22|2|2

2132

2|2|2|21|1|0|00|2|3|12|1|1|2

2022

2112

0332

0331

2122

2|1|22|3|31|1|12|2|2

0|03|30|22|1

0322

0312

1|23|33|32|2

0|22|13|32|2

2|0|2|01|2|2|32|2|0|02|2|2|2

2312

0332

2232

2|02|31|12|2

1322

2322

2302

0322

1232

1|13|20|22|2

1312

2222

1|23|33|32|2

2|00|23|32|2

0|1|0|2|22|3|3|0|22|0|1|2|02|2|2|2|2

2312

0332

2232

2212

1322

2322

2302

1312

0322

2132

1232

1222

2222

2122

2332

2|10|23|32|2

2|1|2|12|3|0|21|1|2|22|2|2|2

1332

2232

2322

2312

1322

2132

2222

2122

2332

2|23|32|11|2

2331

2322

1332

1331

1|13|32|11|2

1322

2|2|2|22|3|3|33|3|2|32|1|2|2

2|23|32|10|1

2330

2321

2312

2|10|13|32|2

1|2|2|11|1|0|22|1|2|12|2|2|2

1|1|1|13|3|3|23|2|3|32|2|1|2

2132

2222

2212

1222

1330

2122

1|13|32|10|1

1312

1321

2|23|33|31|2

2|23|30|22|0

2330

2322

2321

1|13|33|31|2

1330

2312

1|13|30|22|0

1322

1312

1321

1|23|33|32|2

2|13|33|31|1

0|22|13|32|2

0332

2232

2|01|23|31|1

2231

0331

1232

1231

2230

2|2|2|2|2|1|2|2|12|3|3|1|3|3|3|3|23|3|3|3|1|3|2|2|32|2|1|2|2|2|1|2|2

2|23|30|11|0

2031

2|23|32|30|0

2311

2231

2131

2|2|2|20|0|2|22|3|1|01|0|0|1

2|21|12|31|0

2221

2220

2302

2211

1222

1|00|13|32|2

1|1|0|00|2|3|12|0|0|22|2|2|2

1312

1122

0|03|23|32|2

1132

2032

1|02|31|12|2

0222

1322

1302

0322

2222

2|20|22|02|2

38

2122

54

2212

2230

2|2|2|1|22|3|3|3|33|3|2|3|32|1|2|2|2

2|23|32|10|1

2131

2330

2221

2321

2231

2|2|2|21|2|2|12|1|2|31|1|0|0

2312

1|01|23|32|2

0|1|0|12|1|3|22|2|1|12|2|2|2

0332

1232

2132

1322

1312

0322

1222

2222

2|21|22|12|2

2221

2|2|1|22|3|3|33|2|3|32|2|2|2

2|23|30|12|1

2122

2|2|1|23|3|3|22|3|3|31|1|1|1

2212

2312

2222

2|2|2|21|2|2|12|1|0|11|1|2|2

1|01|23|32|2

0332

1232

2132

1|01|23|31|1

1231

0331

2131

2332

2|23|30|22|1

2331

2322

1332

1331

2312

1|13|32|01|2

1322

1312

2|23|33|31|2

2|23|32|10|2

2330

2322

2321

1|13|33|31|2

1330

1|13|32|10|2

1322

1321

2332

1|22|13|32|2

1|2|1|23|2|2|10|0|2|12|2|2|2

2312

1332

2232

1312

2322

2302

1322

2222

2212

2122

2230

2|23|33|31|2

2|23|32|10|2

2032

2330

2222

2322

2232

2321

2132

2|2|2|22|0|0|21|3|2|22|0|2|0

2|21|12|32|0

2|20|23|21|1

2231

2131

2230

2|2|2|2|1|2|12|3|3|1|3|3|23|3|3|3|3|2|32|2|1|2|2|2|2

2|23|32|10|1

2031

2330

2221

2321

2231

2131

2|2|2|20|2|2|03|1|2|20|1|0|1

2|21|12|31|0

2312

1222

1|00|13|32|2

1|0|1|02|3|0|11|1|2|22|2|2|2

1122

0|03|23|32|2

1132

2032

0222

1322

1312

0322

2222

2|22|01|22|2

2122

2230

2|2|2|2|2|1|22|3|3|3|3|3|33|3|3|2|1|3|22|2|1|2|2|2|1

2|23|30|11|0

2131

2|23|32|30|0

2311

2231

2|2|2|22|1|2|11|2|0|30|1|1|0

2221

2220

2302

2211

1|01|23|32|2

1|1|0|01|2|3|22|0|0|22|2|2|2

1312

0332

1232

2132

1|02|31|12|2

1322

1302

0322

1222

2222

2|21|22|02|2

2212

2231

2332

2|23|30|22|1

2132

2331

2222

2322

2232

2|2|2|21|2|2|12|2|0|32|1|2|1

2312

2212


Contributions et ouvertures


2 La récurrence connue dans les graphes finis





Contributions et ouvertures Contributions

Journées Montoises 2018 (avec Y. Le Borgne)

I Une définition de récurrence sur la grille infinie Z2

I Description de motifs par des forêts bipériodiquessans arbre fini

I Construction de groupes finis sur les configurationsbipériodiques

ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3

0I Construction explicite d’un automate reconnaissant

des configurations récurrentes à gaucheI Bornes entre αH et βH logH états

GASCom 2018I Extension du travail de MasterI Positivité de polynômes énumérant des

permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations







ICGT 2018

1

2

2

2

1

0

2

1

2

2

3

1

2

1

2

2

3




permutations


Ouvertures

I Caractérisation des ordres induits

I Lien avec les permutations séparablesI Description possible par des couples de forêts et partitions non croisées

I Projet ENDEAR : simulation d’écoulement dans un canal avec obstacle

I Croisement bande et configurationsbipériodiques, vers des configurationsrécurrentes monopériodiques

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

I Extension du critère affaibli pour obtenir toutes les forêts bipériodiqueset application au polynôme de Tutte (soumis à FPSAC 2019)

I Groupe des bipériodiques et relation avec les récurrentes


Ouvertures

I Caractérisation des ordres induitsI Lien avec les permutations séparables

I Description possible par des couples de forêts et partitions non croisées



C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5




Ouvertures

I Caractérisation des ordres induitsI Lien avec les permutations séparablesI Description possible par des couples de forêts et partitions non croisées



C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5




Ouvertures




C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5




Ouvertures




H = 3

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5




Ouvertures




H =∞

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5




Ouvertures




H =∞

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5




Ouvertures




H =∞

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5

C0 C1 C2 C3 C4 C5




Merci pour votre attention

Formes quadratiques et motifs périodiques[Levine, Pegden, Smart 12,17] Description des motifs par des formesquadratiques.

Figure – Chaque zone bleue peut être décrite par une forme quadratique.[arxiv :1708.09432]

Quadratic forms for periodic zones [Levine, Pegden, Smart2012]

M(a, b, c) =

(c + a bb c − a

)The number of topples is :

h(x) =

⌈12xtM(a, b, c)x

⌉= (c + a)x2 + 2bxy + (c − a)y2

Then number of grains is

∆h(u) =∑v∼u

h(v)− h(u).

Sample forM(0.25, 0.875, 2.125)

I It’s periodic for a, b, c ∈ QI But it may be negative and/or unstable !

It may be stabilized without changing density of grains.

stab(∆h)


M(a, b, c) =

(c + a bb c − a


h(x) =

⌈12xtM(a, b, c)x

⌉= (c + a)x2 + 2bxy + (c − a)y2


∆h(u) =∑v∼u

h(v)− h(u).

Sample forM(0.25, 0.875, 2.125)



stab(∆h)


M(a, b, c) =

(c + a bb c − a


h(x) =

⌈12xtM(a, b, c)x

⌉= (c + a)x2 + 2bxy + (c − a)y2


∆h(u) =∑v∼u

h(v)− h(u).

Sample forM(0.25, 0.875, 2.125)

I It’s periodic for a, b, c ∈ Q

I But it may be negative and/or unstable !It may be stabilized without changing density of grains.

stab(∆h)


M(a, b, c) =

(c + a bb c − a


h(x) =

⌈12xtM(a, b, c)x

⌉= (c + a)x2 + 2bxy + (c − a)y2


∆h(u) =∑v∼u

h(v)− h(u).

Sample forM(0.25, 0.875, 2.125)



stab(∆h)

Bounds on the number of induced orders

PropositionAny induced order appears as a letter on some recurrent configuration’sstandardized decomposition on [1,W ]× [1,H] for W = 2H + 1.

−→1

−→2

−→3−→4

−→5

−→6

−→7

−→8

←−1

I Order over the right horizontal edges :5, 4, 7, 8, 6, 1, 3, 2

I Binary trees ⇒ Separable permutations(avoiding pattern 2413 and 3142)

I Exponential lower bound on the number ofstates



−→1

−→2

−→3−→4

−→5

−→6

−→7

−→8

←−1






−→1

−→2

−→3−→4

−→5

−→6

−→7

−→8

←−1






−→1

−→2

−→3−→4

−→5

−→6

−→7

−→8

←−1




Towards the infinite ladder (Járai, Lyons 07)

Approximation of Z× [1,H] by square grid graphs rooted to the sink on theleft and right sides.

S

0

0

2

3

2

2

1

0

2

1

2

2

3

2

2

1

2

2

2

0

2

3

2

2

2

1

33

1

2

2

2

3

1

3

W

H

S

2

1

0

2

1

2

2

3

2

0

0

0

I vertices that topples from the left (green and yellow)I vertices that topples from the right (red and yellow)I other vertices (gray)

A left burnable configuration is a green/yellow configuration.Decomposition in left-burnable blocks..

Automaton on a super set of column alphabet ⇒ Parry measure ⇒ Uniformdistribution on left-burnable configurations of Z× [1,H]



S

0

0

2

3

2

2

1

0

2

1

2

2

3

2

2

1

2

2

2

0

2

3

2

2

2

1

33

1

2

2

2

3

1

3

W

H

S

2

1

0

2

1

2

2

3

2

0

0

0






S

0

0

2

3

2

2

1

0

2

1

2

2

3

2

2

1

2

2

2

0

2

3

2

2

2

1

33

1

2

2

2

3

1

3

W

H S

2

1

0

2

1

2

2

3

2

0

0

0




Un résultat sur la combinatoire des permutationsSoit Sn l’ensemble des permutations de {1 . . . n}, sn la permutationdécroissante (n, n − 1, . . . 1).

Théorème [D. 2018]

Pour tout n ∈ N, p ≺ sn et D sous ensemble de {1, . . . , n − 1}, la sommesuivante est un polynôme à coefficients entiers positifs.

∑σ∈Sp,Dn

qmaj σ − qinv σ

1− q

où Sp,Dn est l’ensemble des permutations de Sn qui contiennent la sous suitep dont l’ensemble des descentes de l’inverse est D.

Exemple : n = 5, p = (4 3 1) et D = {2, 3}, les permutations sont 43125,43152, 43512 et 45312, et la somme est q7 + q6 + 2q5 + 2q4 + q3.

∑σ∈Spn

qmaj σ − qinv σ

1− q︸︷︷︸positif ?

=∑σ∈Spn

qmaj σ − qstat σ


+∑σ∈Spn

qstat σ − qinv σ


Un résultat sur la combinatoire des permutationsSoit Sn l’ensemble des permutations de {1 . . . n}, sn la permutationdécroissante (n, n − 1, . . . 1).

Théorème [D. 2018]

Pour tout n ∈ N, p ≺ sn et D sous ensemble de {1, . . . , n − 1}, la sommesuivante est un polynôme à coefficients entiers positifs.

∑σ∈Sp,Dn

qmaj σ − qinv σ

1− q

où Sp,Dn est l’ensemble des permutations de Sn qui contiennent la sous suitep dont l’ensemble des descentes de l’inverse est D.

Exemple : n = 5, p = (4 3 1) et D = {2, 3}, les permutations sont 43125,43152, 43512 et 45312, et la somme est q7 + q6 + 2q5 + 2q4 + q3.∑

σ∈Spn

qmaj σ − qinv σ


=∑σ∈Spn

qmaj σ − qstat σ


+∑σ∈Spn

qstat σ − qinv σ


Soit W = (wi ,j)n×n une matrice triangulaire supérieure.

invW (σ) =∑

1≤i<j≤nwi ,jχ(σ(i) > σ(j))

est le nombre d’inversions de σ pondéré par W [Kadell 85].

Winv =

0 1 1 1 10 0 1 1 10 0 0 1 10 0 0 0 10 0 0 0 0

Wmaj =

0 1 0 0 00 0 2 0 00 0 0 3 00 0 0 0 40 0 0 0 0

Interpolation avec W 4,2 =

4

0 1 1 0 00 0 1 2 0 20 0 0 1 00 0 0 0 40 0 0 0 0

⇒

W n,1 = WinvW 2,1 = WmajW i ,1 = W i+1,i

Un polynôme à la Tutte pour les forêts bipériodiques

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

•••••

••

• •

••

•••• ••

e1

e2 Activité externe : nombre d’arêtesexternes minimales dans leurs cyclesinduitsExtension aux “cycles infinis” pour unordre donnée par une direction.Auto-dualité de la grille pour définirl’activité interne.

T~θ,W×H(q, t) := TZ2,<Eθ|FW×H×(F∗)W×H ,EW×H

(q, t).

Théorème (D., Le Borgne 2018)

Pour toutes directions rationnelles ~θ et ~θ′, T~θ,W×H(q, 1) = T~θ′,W×H(q, 1).

T~0,3×1(q, t) = q3t3 + 3q2 + 3qt + 3t2 + 3q + 3t + 1

T ~π/2,3×1(q, t) = q3t3 + 3q2t + 3qt2 + 3q + 3t + 4

Chaine de Markov sur les configurations stablesI Sommets : configurations stablesI Transitions : Ajout d’un grain à un sommet et stabiliser

P

0

0

0

P

0

1

0 P

1

0

0 P

2

0

0 P

1

1

0

P

2

1

0

Configurations récurrentes

Les configurations récurrentes sont celles qui forment l’unique composantefortement connexe dont on ne peut sortir.



Chaine de Markov sur les configurations stablesI Sommets : configurations stablesI Transitions : Ajout d’un grain à un sommet et stabiliser

P

0

0

0

P

0

1

0 P

1

0

0 P

2

0

0 P

1

1

0

P

2

1

0

Configurations récurrentes

Les configurations récurrentes sont celles qui forment l’unique composantefortement connexe dont on ne peut sortir.



Documents

Combinatoire dans des stabilisations du modèle du tas de ...Lemodèledutasdesable Tasdesable[Bak,Tang,Wiesenfeld87] éboulement gauche Uneconﬁgurationestladonnéedunombredegrainsparsommet