moteur de recherche

Séminaire Algo - Robert Cori
Séminaire Algo - Robert Cori
7-mars-2017 14:30
Il y a: 111 days





Robert Cori

Le rang des configurations sur un graphe : questions combinatoires et algorithmiques

Salle de séminaire (4B05R) - Bâtiment Copernic

Résumé : Une configuration sur un graphe est obtenue par l'attribution de valeurs entières à tous ses sommets. Ces valeurs peuvent aussi être négatives. Un éboulement sur un sommet consiste à  augmenter de 1 la valeur de la  configuration  pour  chacun de ses voisins et à diminuer d'autant la valeur sur le sommet. Le modèle du tas de sable et le jeu du "chip-firing" étudient les suites  d'opérations d'éboulement.

Une première question considérée ici consiste à déterminer pour une configuration donnée s'il existe une suite d'éboulements qui permette d'atteindre une configuration n'ayant aucun sommet de valeur négative. Une telle configuration est dite L-effective. On peut obtenir un algorithme qui décide de cette question en un nombre d'opérations fonction  polynomiale du nombre de la taille des données.Le rang d'une configuration L-effective  introduit par Baker et Norine en 2007 est en quelque sorte une distance entre cette configuration et l'ensemble de celles qui ne sont pas L-effectives. Sa détermination a été démontrée être un problème NP-complet. Toutefois ce rang vérifie de belles propriétés algébriques, il donne lieu lorsqu'on s'intéresse à certaines familles particulières de graphes à des rencontre avec des objets combinatoires remarquables.








<- retour: