Journées de combinatoire de Bordeaux 2010 (JCB 2010)

Les JCB 2010 ont eu lieu du mercredi 27 au vendredi 29 janvier 2010, sur le thème de la combinatoire énumérative et algébrique. Les exposés ont eu lieu dans l’amphithéâtre du LaBRI (Bâtiment A30) à l’Université de Bordeaux.

Orateurs et résumés

Accéder aux résumés au format pdf.

• Michel Bauer SLE et au delà : Le point de vue d’un physicien
  Résumé

  Les courbes aléatoires intéressent depuis longtemps physiciens et mathématiciens. Les premiers sont intéressés par les interfaces séparant deux phases dans certains systèmes physiques à deux dimensions. Les mathématiciens se concentrent souvent sur des objets purement géométriques comme les marches auto-évitantes.

  Au tournant du millénaire Oded Schramm a défini de nouveaux processus stochastiques qui décrivent la limite continue de ces courbes aléatoires sous une hypothèse d’invariance conforme. Ces processus de croissance SLE (pour Schramm-Loewner Equation) ont complètement révolutionné notre compréhension des interfaces bidimensionnelles.

  Après avoir montré des exemples de systèmes discrets dont la limite continue est décrite par SLE, tant en physique qu’en mathématique, je présenterai l’équation de Schramm-Loewner et je dirai quelques mots de ses applications à des calculs explicites.

  Depuis peu, on étudie aussi les courbes aléatoires non-critiques, où une échelle de longueur est présente. Ce cas est bien plus difficile à aborder, mais se trouve à nouveau à la croisée des intérêts de physiciens et des mathématiciens. On dispose de quelques résultats non triviaux que je décrirai brièvement.

  Je conclurai sur quelques problèmes ouverts.

• Nicolas Bédaride Mots infinis et billard dual
  Résumé

  Pour étudier un système dynamique, on peut se donner une décomposition cellulaire de l’espace des phases, et coder les trajectoires via cette décomposition cellulaire. Si la décomposition a de bonnes propriétés, alors la dynamique revient à étudier un sous-shift. Dans cet exposé nous présenterons le cas du billard dual. On considère un polygone convexe du plan, les droites supportant les arêtes du polygone déterminent une partition du plan en secteurs angulaires. Ces secteurs ont pour sommets les sommets du polygone. La transformation est alors définie à l’extérieur du polygone, comme étant localement une symétrie centrale par rapport au sommet du polygone. Nous étudierons plus en détails les polygones réguliers. Dans ce cas, la dynamique symbolique est bien comprise.
• Adrien Boussicault Combinatoire des fractions rationnelles de Greene
  Résumé

  À chaque mot $w$, on associe la fonction rationnelle $\psi_\sigma := \prod (x_{\sigma(i)} - x_{\sigma(i+1)})^{-1}$. Le but de cet exposé est d’étudier la somme $\Psi_P$ des fonctions $\psi_w$ sur les extensions linéaires des posets. En particulier, nous décrivons différentes transformations sur les graphes associés aux posets qui se traduisent par des opérations élémentaires sur ces fonctions. Enfin, nous caractérisons de manière combinatoire le numérateur et le dénominateur de $\Psi_P$.
• Frédéric Chapoton Arbres binaires, arbres non-croisés, quadrangulations
  Résumé

  Les triangulations des polygones réguliers sont des objets très classiques, comptés par les nombres de Catalan. On peut aussi voir les triangulations comme des arbres binaires plans, par une bijection standard. On présentera une injection naturelle de cet ensemble dans l’ensemble des arbres-non croisés dans un polygone régulier plus petit. Il existe une dualité naturelle sur l’ensemble de arbres non-croisés. On montrera que les orbites pour cette involution sont naturellement en bijection avec les quadrangulations d’un polygone régulier de taille double. Du point de vue combinatoire, ce sont des constructions simples et classiques. Leur intérêt réside dans les aspects plus algébriques sous-jacents : algèbre dendriforme, treillis de Tamari, modules basculants, suites exceptionnelles, etc.
• Robert Cori Permutations indécomposables, hypercartes et sous-groupes d’index fini du groupe libre
  Résumé

  Je présenterai plusieurs bijections entre les permutations indécomposables et les hypercartes pointées. Ces bijections permettent d’énumérer les hypercartes auto-réciproques ou auto-duales. Les hypercartes peuvent être considérées aussi comme cartes biparties ce qui permet de représenter ces bijections de manière plus visuelle.

  Une construction très simple permet de passer des hypercartes aux sous groupes d’index fini du groupe libre a deux générateurs.

  Plusieurs questions ouvertes seront proposées.

• Sylvie Corteel Tableaux escaliers et polynomes d’Askey Wilson
  Résumé

  Les tableaux escaliers sont des nouveaux objets combinatoires inventés par Corteel et Williams. Ils donnent une interprétation combinatoire de la distribution stationnaire du processus d’exclusion partiellement asymétrique. Ils permettent aussi de donner une formule combinatoire pour les moments des polynomes d’Askey-Wilson. Ceci est un travail en commun avec Lauren Williams et Dennis Stanton.
• Alexis Darrasse Approche combinatoire de l’analyse des k-arbres
  Résumé

  Les k-arbres forment une clases de graphes qui joue un rôle central en algorithmique des graphes, par leur lien avec la notion de “treewidth”. Dans cet exposé on présente une bijection, entre ces graphes et une famille simple d’arbres, et comment on utilise cette bijection pour étudier la distance entre sommets d’un k-arbre. Cette approche s’applique également aux sous-classes des k-arbres : k-arbres croissants, traingulations empilées et autres; on montre enfin comment l’étendre à une autre classe, les graphes cordaux croissants.
• Philippe Flajolet Compter avec AB-BA=1
  Résumé

  La physique quantique a révélé l’intérêt d’élucider les propriétés algébriques d’opérateurs $A$ et $B$ vérifiant la relation de commutation partielle $AB - BA = 1$. On montrera, suivant des travaux de Penson, Blasiak et al., que la réduction sous forme normle de polynômes en $A$ et $B$ est équivalente au dénombrement de certains diagrammes, lesquels sont des graphes étiquetés obéissant à des règles simples de monotonicité. On examinera alors comment interviennent dans ce contexte, nombres de structures classiques telles que les involutions, les arbres croissants, les permutations et partitions d’ensemble, ainsi que les chemins de Dyck valués. (Travail en commun avec Pawel Blasiak, Krakòw.)
• Guoniu Han Des nouveautés concernant les formules d’équerres pour les partitions et les arbres planaires
  Résumé

  La formule des équerres (“hook formula”) joue un rôle essentiel en Combinatoire Algébrique, Théorie des Représentations et Théorie des Partitions. Une nouvelle méthode, appelée technique de développement en longueur des équerres, permet de découvrir une famille des formules des équerres. Un cas particulier de ces formules a été obtenu par Nekrasov et Okounkov dans un contexte tout à fait différent. Dans le cas des arbres planaires on obtient une formule qui unifie plusieurs résultats classiques, y compris la formule de Postnikov. D’autres travaux récents liés à ce sujet par Stanley, Ono, Bessenrodt, Carde, Loubert, Potechin, Sanborn, Okada et Panova seront présentés.
• Matthieu Josuat-Vergès Nombres de Genocchi et tableaux alternatifs
  Résumé

  Dumont et Foata ont découvert en 1976 des polynômes symétriques en trois variables qui raffinent les nombres de Genocchi. Un problème toujours ouvert est de donner une interprétation combinatoire où la symétrie est apparente. Nous ne répondons pas à cette question, mais nous donnons une nouvelle interprétation de ces polynômes grâce aux tableaux alternatifs, objets apparus dans d’autres contextes (processus d’exclusion asymétrique…)
• Yvan Le Borgne Empilements pour une généralisation des chemins de Dyck
  Résumé

  Les chemins de Dyck peuvent s’interpréter comme l’historique de marches sur les entiers naturels formées de pas $+1$ ou $-1$, débutant et finissant en zéro. Plusieurs généralisations de ces chemins portant sur l’ensemble des pas autorisés ont été étudiées. Cet exposé abordera le cas des chemins formés de pas $+a$ et $-b$ où $a$ et $b$ sont des entiers naturels que l’on peut supposer premier entre eux. On se donne un sous-ensemble fini d’entiers naturels et on s’intéresse aux chemins ne passant que par ces entiers. On recherche alors de la structure sur la série génératrice nécessairement rationnelle associée à l’énumération selon le nombre de pas. Par exemple, Bousquet-Mélou a montré en 2006 que pour les sous-ensemble finis des segments initiaux $(0, 1, \dots, k)$, il existe une série rationelle bivariée $T_{a,b}(z, t)$ telle que la série génératrice en la variable $t$ pour l’ensemble ${0, \dots, k}$ soit le rapport des coefficients de $z^{k-1}$ et $z^k$ de la série bivariée. On étudiera seulement certains sous-ensembles finis d’entiers, un choix motivé par la relation avec un autre problème combinatoire.
• Jean Mairesse Autour des automates cellulaires probabilistes
  Résumé

  Un Automate Cellulaire Probabiliste (ACP) est une extension de la notion d’automate cellulaire : on conserve le meme espace d’états, ainsi que le caractère à la fois local et synchrone de la dynamique. La nouveauté est que chaque site réactualise sa valeur de facon aléatoire suivant une loi qui dépend d’un ensemble fini de sites voisins. Il existe plusieurs motivations pour s’intéresser aux ACP: il s’agit de l’analogue synchrone des modèles de “systemes de particules en interaction” des probabilistes; ils apparaissent dans des problèmes combinatoires de physique statistique (énumération des animaux dirigés); ils permettent d’étudier la robustesse aux erreurs des automates cellulaires traditionnels. Un ACP est une chaine de Markov dont on veut étudier le comportement a l’équilibre. On abordera plusieurs questions : unicité de la mesure stationnaire (ergodicité), existence de mesures stationnaires ayant une forme simple, échantillonage à la Propp-Wilson selon la mesure stationnaire.
• Philippe Nadeau Énumeration de configurations de boucles compactes dans un triangle
  Résumé

  Motivés par la conjecture de Razumov Stroganov, nous nous intéressons aux configurations de boucles compactes (abrégées en FPLs pour “Fully Packed Loops”) dans un triangle (TFPLs), introduites par Caselli et al. puis étudiées par Thapper. Nous montrons que pour les FPLs avec un couplage donné, il existe des relations de récurrence linéaires dont les coefficients sont calculés à partir des TFPLs. Nous donnons ensuite des contraintes et des résultats énumératifs pour certaines familles de TFPLs. En particulier, pour un certain choix de conditions au bord, le nombre de TFPLs est donné par les coefficients de Littlewood Richardson.
• Jean-Christophe Novelli Algèbres de Hopf et tableaux de permutations
  Résumé

  L’objectif de cet exposé est de montrer comment l’outil “algèbres de Hopf combinatoires” permet de s’intéresser à des questions hors du champ de la combinatoire algébrique, en apportant un éclairage nouveau. Dans le cas des tableaux de permutations, il s’agira de construire des analogues non-commutatifs des fonctions de Hall-Littlewood et d’en déduire une formule donnant une q-énumération des tableaux de permutation d’une forme donnée. Travail en commun avec J.-Y. Thibon et L. K. Williams.
• David Renault Comment déterminer la planarité d’un graphe de Cayley d’un groupe fuchsien ?
  Résumé

  Considérons les groupes fuchsiens, c’est-à-dire les groupes d’isométries discrets du plan hyperbolique. Chaque élément de cette famille de groupes infinis possède l’agréable propriété de pouvoir être représenté par un graphe de Cayley planaire localement fini. Mieux, ce graphe peut être représenté de manière entièrement combinatoire, que ce soit par une présentation particulière de ce groupe, ou par un objet nommé schéma d’étiquetage, une sorte d’automate décrivant les sommets, arêtes et faces du graphe plongé dans le plan.

  Une question naturelle, lorsque l’on se donne un groupe fuchsien, consiste à construire un graphe de Cayley planaire qui lui corresponde. Et la facilité, pour se donner un groupe fuchsien, consiste à le prendre comme un sous-groupe d’un autre groupe fuchsien. La question devient alors liée à un problème de combinatoire des groupes faisant partie des problèmes de Dehn, nommé le problème du mot généralisé (generalized word problem ou GWP).

  Originellement, si l’on se restreint simplement aux groupes engendrés par 2 générateurs, le théorème de Rosenberger donne une caractérisation de ces couples de générateurs qui engendrent un groupe fuchsien. Ce théorème est constructif (d’un point de vue mathématique), et J. Gilman a étudié cette construction et fournit un algorithme (au sens des machines BSS) pour résoudre le problème.

  Dans cet exposé, nous présentons une méthode pour construire des graphes de Cayley planaires des groupes fuchsiens avec un nombre quelconque de générateurs. Cette méthode est guidée à la fois par la représentation combinatoire du groupe et par son action sur le plan. Cette construction offre une piste pour obtenir un algorithme efficace de résolution du GWP pour les groupes fuchsiens.

Emploi du temps

Mercredi 27 janvier

Jeudi 28 janvier

Vendredi 29 janvier

Participants

• Marie Albenque (LIX CNRS, Ecole Polytechnique)
• Antoine Genetrini (PRISM, Versailles)
• Jean-Christophe Aval (LaBRI, Bordeaux)
• Axel Bacher (LaBRI, Bordeaux 1)
• Frédérique Bassino (LIPN, Paris XIII)
• Michel Bauer (CEA, Saclay)
• Cyril Banderier (LIPN, Université Paris XIII)
• Nicolas Bédaride (LATP, Université d’Aix-Marseille III)
• Bernard Bercu (IMB, Bordeaux 1)
• Jean Bétréma (LaBRI, Bordeaux)
• Nicolas Bonichon (LaBRI, Bordeaux)
• Mireille Bousquet-Mélou (LaBRI, Bordeaux)
• Adrien Boussicault (Institut Gaspard Monge, Paris-Est Marne la Vallée)
• Nicolas Broutin (Inria, Rocquencourt)
• Frédéric Chapoton (Institut Camille Jordan, Lyon 1)
• Brigitte Chauvin (LMV, Université de Versailles Saint-Quentin et INRIA Rocquencourt projet Algorithms)
• Hayat Cheballah (LIPN, Université Paris XIII)
• Robert Cori (LaBRI, Bordeaux)
• Sylvie Corteel (LRI, Orsay)
• Bruno Courcelle (IUF et LaBRI, Bordeaux)
• Alexis Darrasse (LIP6, Paris 6)
• Julien David (LIGM, Université Paris-Est)
• Paul Dorbec (LaBRI, Bordeaux 1)
• Vincent Delecroix (Institut de Mathématiques de Luminy, Marseille)
• Philippe Duchon (LaBRI, Bordeaux)
• Valentin Feray (LaBRI, Bordeaux)
• Thomas Fernique (LIF, Marseille)
• Philippe Flajolet (INRIA, Rocquencourt)
• Yoann Gelineau (Institut Camille Jordan, Lyon 1)
• Samuele Giraudo (IGM,Université de Marne-la-Vallée)
• Olivier Guibert (LaBRI, Bordeaux)
• Adrien Guignard (LaBRI, Bordeaux)
• Guoniu Han (IRMA, Strasbourg)
• Matthieu Josuat-Vergès (LRI, Orsay)
• Yann Jullian (LATP, Aix-Marseille III)
• Christian Lavault (LIPN, Villetaneuse)
• Alain Lascoux (IGM, Université de Marne-la-Vallée)
• Yvan Le Borgne (LaBRI, Bordeaux)
• Florent Le Gac (LaBRI, Bordeaux)
• Jérémie Lumbroso (INRIA, Rocquencourt)
• Jean Mairesse (LIAFA, Paris 7)
• Jean-François Marckert (LaBRI, Bordeaux)
• Michel Marcus (LaBRI, Bordeaux)
• Philippe Nadeau (Faculty of Mathematics of the University of Vienna)
• Jean-Christophe Novelli (Institut Gaspard Monge, Paris- Est Marne la Vallée)
• Jean Guy Penaud (LaBRI, Bordeaux)
• Adeline Pierrot (LIAFA, Paris Diderot - Paris 7)
• Laurent Poinsot (Université Paris-Nord XIII)
• Nicolas Pouyanne (LMV, Université Versailles Saint Quentin en Yvelines)
• David Renault (LaBRI, Bordeaux)
• Tarek Sellami (institut de mathématiques de Luminy)
• Andrea Sportiello (Milan university)
• Gautier Stauffer (INRIA-IMB, Bordeaux)
• Hanane Tafat (LIPN, université Paris XIII)
• Jean-Yves Thibon (IGM, Université Paris-Est Marne-la-Vallée)
• Alexandre Zvonkin (LaBRI, Bordeaux)

Organisateurs

• Jean-Christophe Aval
• Jean-François Marckert

Soutien financier

• Projet ANR MARS
• Projet ANR A3
• LaBRI
• Université Bordeaux 1