Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2018-03-09  09:30-10:30
TitreAutomate reconnaissant dans le modèle du tas de sable les configurations récurrentes gauches sur une bande de hauteur H.  
RésuméLe modèle du tas de sable se définit bien pour tout graphe fini. Jarai et Lyons ont approximé le comportement sur la bande bi-infinie de hauteur $H$ dans $mathbb{Z}^2$ par une suite de rectangles de hauteur $H$ de plus en plus large. Cela les conduit notamment à la notion de configuration récurrente éboulable de la gauche. On s'intéresse alors à des automates reconnaissant colonne par colonne ces configurations. Jarai et Lyons en donnent un automate explicite pour la hauteur $H=2$ et ont montré qu'il existe un automate pour tout $H$ avec au plus $(2^H)^{2^H}$ états. Dans sa thèse, Gamlin conjecture, en s'appuyant sur des simplifications, qu'on peut réduire le nombre d'états en $alpha^H$. En s'appuyant sur une bijection entre les récurrentes et les arbres couvrants et sur une étude combinatoire, je proposerai une borne probablement grossière sur le nombre d'états, en $alpha^{Hlog H}$. Les algorithmes liés à ces bornes permettent de produire les automates pour la hauteur $H=3$ et $H=4$. Dans cette construction, l'automate contient au moins $eta^{H}$ états car on isole un sous-ensemble de ces états en bijection avec les permutations séparables (celles évitant les motifs 3142 et 2413). Ce travail en cours est aussi en lien et motivé par l'analyse également en cours de simulations impliquant le modèle du tas de sable. 
Lieu076 
OrateurHenri Derycke 



Aucun document lié à cet événement.

Retour
Retour à l'index