View
1
Download
0
Category
Preview:
Citation preview
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
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
é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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
é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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
é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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
é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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
é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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
é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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
é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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
Le modèle du tas de sable Tas de sable [Bak, Tang, Wiesenfeld 87]
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 2 / 29
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]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 3 / 29
Le modèle du tas de sable La pile de sable
n
Source : Page personnelle de W.Pegden, n = 213
I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]I Convergence en densité [Pegden, Smart 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 3 / 29
Le modèle du tas de sable La pile de sable
n
Source : Page personnelle de W.Pegden, n = 214
I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]I Convergence en densité [Pegden, Smart 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 3 / 29
Le modèle du tas de sable La pile de sable
n
Source : Page personnelle de W.Pegden, n = 218
I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]
I Convergence en densité [Pegden, Smart 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 3 / 29
Le modèle du tas de sable La pile de sable
n
Source : Page personnelle de W.Pegden, n = 220
I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]
I Convergence en densité [Pegden, Smart 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 3 / 29
Le modèle du tas de sable La pile de sable
n
Source : Page personnelle de W.Pegden, n = 230
I Structure fractale [Creutz, Bak, Tang 90, Ostojic 03, Dhar Sadhu 08]I Convergence en densité [Pegden, Smart 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 3 / 29
Le modèle du tas de sable La pile de sable
Couleurs :
0123
n = 106
Comportement avec moins de structureMotif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 4 / 29
Le modèle du tas de sable La pile de sable
Couleurs :
0123
n = 106
Comportement avec moins de structureMotif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 4 / 29
Le modèle du tas de sable La pile de sable
Couleurs :
0123
Comportement avec moins de structure
Motif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 4 / 29
Le modèle du tas de sable La pile de sable
Couleurs :
0123
n = 106
Comportement avec moins de structureMotif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 4 / 29
Le modèle du tas de sable La pile de sable
Couleurs :
0123
Comportement avec moins de structure
Motif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 4 / 29
Le modèle du tas de sable La pile de sable
Couleurs :
0123
Comportement avec moins de structure
Motif périodique [Ostojic 03, Dhar, Chandra, Sadhu 08, Caraciollo, Paoletti,Sportiello 12]
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 4 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 5 / 29
Le modèle du tas de sable La pile de sable
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 6 / 29
La récurrence connue dans les graphes finis
1 Le modèle du tas de sable
2 La récurrence connue dans les graphes finisPuitsLes configurations récurrentesCritère de Dhar
3 Récurrentes périodiques sur Z2
4 Le cas de la bande biinfinie
5 Contributions et ouvertures
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 7 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 8 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 8 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 8 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
PX 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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
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
PX 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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 9 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1,
e2,
v2,
e3,
e5,
v4,
e6,
v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2,
v2,
e3,
e5,
v4,
e6,
v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2,
e3,
e5,
v4,
e6,
v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3,
e5,
v4,
e6,
v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5,
v4,
e6,
v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4,
e6,
v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6,
v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3,
e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4,
v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1,
e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7,
v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5,
e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8,
v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6, e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6, e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6, e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
La récurrence connue dans les graphes finis Critère de Dhar
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.
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 : e1, e2, v2, e3, e5, v4, e6, v3, e4, v1, e7, v5, e8, v6,
e9
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 10 / 29
Récurrentes périodiques sur Z2
1 Le modèle du tas de sable
2 La récurrence connue dans les graphesfinis
3 Récurrentes périodiques sur Z2
Placement du puitsCritère de Dhar affaibliBijectionComptageGroupe des récurrentes bipériodiques
4 Le cas de la bande biinfinie
5 Contributions et ouvertures
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 11 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 12 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
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.
+1
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
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
0 4
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 13 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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 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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
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 puitsI Ultimement périodique ensuite et ne dépend pas de la position du demi
plan de départ
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
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
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 puitsI Ultimement périodique ensuite et ne dépend pas de la position du demi
plan de départ
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 14 / 29
Récurrentes périodiques sur Z2 Critère de Dhar affaibli
ligne de balayage
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 15 / 29
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
Théorème [D., Le Borgne 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 16 / 29
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
Théorème [D., Le Borgne 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 16 / 29
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
Théorème [D., Le Borgne 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 16 / 29
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 bipériodique de chemins infinis vers le puits
Forêt couvrante du tore de pente(1, 0) non compatible avec une direc-tion verticale
Théorème [D., Le Borgne 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 16 / 29
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 bipériodique de chemins infinis vers le puits
Forêt couvrante du tore de pente(1, 0) non compatible avec une direc-tion verticale
Théorème [D., Le Borgne 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 16 / 29
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 bipériodique de chemins infinis vers le puits
Forêt couvrante du tore de pente(1, 0) non compatible avec une direc-tion verticale
Théorème [D., Le Borgne 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 16 / 29
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 bipériodique de chemins infinis vers le puits
Forêt couvrante du tore de pente(1, 0) non compatible avec une direc-tion verticale
Théorème [D., Le Borgne 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 16 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 18 / 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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 18 / 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 0 −1
Donne une définition de groupe mais :éléments du groupe 6= configurations récurrentes dans une direction
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 18 / 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∼
PuitsOpérateurd’arrachage
−10000
Donne une définition de groupe mais :éléments du groupe 6= configurations récurrentes dans une direction
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 18 / 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
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
Donne une définition de groupe mais :éléments du groupe 6= configurations récurrentes dans une direction
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 18 / 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
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
Donne une définition de groupe mais :éléments du groupe 6= configurations récurrentes dans une direction
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 18 / 29
Le cas de la bande biinfinie
1 Le modèle du tas de sable
2 La récurrence connue dans les graphesfinis
3 Récurrentes périodiques sur Z2
4 Le cas de la bande biinfinieRécurrenceDécomposition du parcourssommet-arêteCaractérisation des décompositionsAutomate
5 Contributions et ouvertures
H = 3
1
2
2
2
1
0
2
1
2
2
3
1
2
1
2
2
3
0
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 19 / 29
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 20 / 29
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 20 / 29
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 20 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 21 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 21 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 21 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 21 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
v3I 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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
v3I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .
I Dernier ordre induit : . . . e6e7e8
I Suite d’ordres induits compatibles deux à deux
ΛW ,H
P
0
0
0
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
v3I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .
I Dernier ordre induit : . . . e6e7e8I Suite d’ordres induits compatibles deux à deux
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
v3I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .
I Dernier ordre induit : . . . e6e7e8I Suite d’ordres induits compatibles deux à deux
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
v3I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .
I Dernier ordre induit : . . . e6e7e8I Suite d’ordres induits compatibles deux à deux
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
v3I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .
I Dernier ordre induit : . . . e6e7e8I Suite d’ordres induits compatibles deux à deux
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
v3I Premier ordre induit : e1(v1?)e2(v2?)e3(v3?) . . .
I Dernier ordre induit : . . . e6e7e8I Suite d’ordres induits compatibles deux à deux
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 22 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 23 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 23 / 29
Le cas de la bande biinfinie Automate
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 23 / 29
Le cas de la bande biinfinie Automate
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 23 / 29
Le cas de la bande biinfinie Automate
Pas de caractérisation combinatoire des ordres induits mais :
I Construction depuis les arbres couvrants
P
Proposition [D. 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 24 / 29
Le cas de la bande biinfinie Automate
Pas de caractérisation combinatoire des ordres induits mais :I Construction depuis les arbres couvrants
P
Proposition [D. 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 24 / 29
Le cas de la bande biinfinie Automate
Pas de caractérisation combinatoire des ordres induits mais :I Construction depuis les arbres couvrants
P
Proposition [D. 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 24 / 29
Le cas de la bande biinfinie Automate
Pas de caractérisation combinatoire des ordres induits mais :I Construction depuis les arbres couvrants
P
Proposition [D. 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 24 / 29
Le cas de la bande biinfinie Automate
Pas de caractérisation combinatoire des ordres induits mais :I Construction depuis les arbres couvrants
P
Proposition [D. 2018]
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.
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 24 / 29
Le cas de la bande biinfinie Automate
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 25 / 29
Le cas de la bande biinfinie Automate
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 25 / 29
Contributions et ouvertures
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 26 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 27 / 29
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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
I Projet ENDEAR : simulation d’écoulement dans un canal avec obstacle
I Croisement bande et configurationsbipériodiques, vers des configurationsrécurrentes monopériodiques
H = 3
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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
I Projet ENDEAR : simulation d’écoulement dans un canal avec obstacle
I Croisement bande et configurationsbipériodiques, vers des configurationsrécurrentes monopériodiques
H =∞
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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
I Projet ENDEAR : simulation d’écoulement dans un canal avec obstacle
I Croisement bande et configurationsbipériodiques, vers des configurationsrécurrentes monopériodiques
H =∞
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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
I Projet ENDEAR : simulation d’écoulement dans un canal avec obstacle
I Croisement bande et configurationsbipériodiques, vers des configurationsrécurrentes monopériodiques
H =∞
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
Henri Derycke (LaBRI) Combinatoire et tas de sable 10 décembre 2018 28 / 29
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)
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)
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 ∈ Q
I But it may be negative and/or unstable !It may be stabilized without changing density of grains.
stab(∆h)
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)
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
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
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
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
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]
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]
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]
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 σ
1− q︸ ︷︷ ︸positif ?
+∑σ∈Spn
qstat σ − qinv σ
1− q︸ ︷︷ ︸positif ?
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 σ
1− q︸ ︷︷ ︸positif ?
+∑σ∈Spn
qstat σ − qinv σ
1− q︸ ︷︷ ︸positif ?
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.
Théorème [Dhar 90]
Les configurations récurrentes forment un groupe abélien pour la loi sommesuivie de la stabilisation
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.
Théorème [Dhar 90]
Les configurations récurrentes forment un groupe abélien pour la loi sommesuivie de la stabilisation
Recommended