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


Date 2016-05-13  10:45-11:45
TitreSur le modèle du tas de sable dans un graphe biparti complet 
RésuméLe modèle du tas de sable étudié notamment par Dhar est un modèle de diffusion discret de grains sur les sommets d'un graphe. Ce modèle capture des notions classiques sur le graphe : les états dits récurrents sont en bijection avec les arbres couvrants, le nombre de grains sur ces états est relié à l'activité externe définie par Tutte... Même dans le cas de graphes fortement symétriques comme les graphes complets ou bipartis complets, cela conduits à des notions non-triviales. Par exemple, avec Dukes, nous avions observé que dans le cas d'un graphe complet, le paramètre bounce introduit par Haglund dans une description des q,t-Catalan peut s'interpréter dans la version parallèle du test de récurrence de Dhar pour un état du modèle. Une adaptation de cette remarque aux graphes bipartis complets nous avait conduit à la définition de q,t-Narayana. Rejoins par Aval, D'Adderio et Hicks nous avions prouvé que ces nombres étaient très proche de q,t-analogues également introduits par Haglund avec des motivations plus algébriques. L'objectif du jour sera le calcul du rang, un paramètre introduit par Baker et Norine en 2007 dans un analogue pour les graphes d'un théorème de Riemman-Roch. Ce paramètre est annoncé comme NP-complet sur les graphes. Avec Cori, nous avions proposé dans le cas des graphes complets un algorithme glouton de complexité arithmétique linéaire. Je présenterai son adaptation au cas des graphes bipartis complets que j'ai obtenu en collaboration avec D'Adderio.  
Lieu076 
OrateurYvan Le Borgne 



Aucun document lié à cet événement.

Retour
Retour à l'index