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

Les JCB 2012 ont eu lieu du mercredi 1er au vendredi 3 février 2012, 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.

• Michele d'Adderio Graph colorings, flows and arithmetic Tutte polynomial
  Résumé

  We introduce the notions of arithmetic colorings and arithmetic flows over a graph with labelled edges, which generalize the notions of colorings and flows over a graph. We show that the corresponding arithmetic chromatic polynomial and arithmetic flow polynomial are given by suitable specializations of the associated arithmetic Tutte polynomial, generalizing classical results of Tutte.
• Frédérique Bassino Énumération asymtotique des automates minimaux
  Résumé

  Travail en collaboration avec Julien David (LIPN, Université Paris 13) et Andrea Sportiello (Université de Milan).

  Les automates finis déterministes peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet à lettres et dont deux sous-ensembles de sommets ou états sont distingués (l’état initial et l’ensemble des états terminaux respectivement). Suite aux travaux de Korshunov (1978), et aux simplifications de Bassino-Nicaud (2007) et Lebenszrayn (2010), on sait énumérer asymptotiquement les automates accessibles, déterministes et complets à états sur un alphabet à lettres. Nicaud (1999) a montré qu’asymptotiquement la moitié d’entre eux sont minimaux quand l’alphabet est unaire. On déterminera cette proportion, dans le cas où , pour la distribution uniforme sur les possibles structures de transitions et la distribution binomiale de paramètre quelconque sur les états terminaux (le cas uniforme correspondant à ). Plus précisément, on obtient qu’une fraction des automates sont minimaux où est une fonction, déterminée explicitement, dans laquelle intervient la solution d’une équation transcendante.

• Nicolas Borie Calcul des anneaux d’invariants de groupes de permutations par évaluation.
  Résumé

  Nous proposerons une approche alternative aux bases de Gröbner pour le calcul des invariants secondaires des groupes de permutations, par évaluation en des points choisis de manière appropriée. Cette méthode permet de tirer parti des symétries du problème pour confiner les calculs dans un quotient de petite dimension, et ainsi d’obtenir un meilleur contrôle de la complexité algorithmique, en particulier pour les groupes de grande taille. L’étude théorique est illustrée par de nombreux bancs d’essais utilisant une implantation fine des algorithmes. Un prérequis important est la génération efficace de vecteurs d’entiers modulo l’action d’un groupe de permutation, dont l’algorithmique sera exposé dans les préliminaires de cet exposé.
• Mireille Bousquet-Mélou Le modèle de Potts sur les cartes planaires
  Résumé

  Toute carte planaire peut être (bien) coloriée avec 4 couleurs. Mais de combien de façons peut-on, en moyenne, bien colorier une carte à arêtes ? De combien de façons peut-on la colorier si on autorise un nombre fixé d’arêtes monochromes, c’est-à-dire dont les deux extrémités sont de la même couleur ? Quid si on dispose de couleurs, plutôt que 4 ?

  Pour tenter de répondre à ces questions, on s’intéresse à la série génératrice de familles de cartes planaires, pondérées par leur polynôme chromatique, ou plus généralement par leur polynôme de Tutte. En termes plus physiques, ces problèmes reviennent à étudier le modèle de Potts sur des cartes planaires aléatoires.

  L’étude de ces séries génératrices se prête bien à une approche récursive, à la Tutte, justement. Lequel Tutte a obtenu, au terme de 10 ans d’efforts et autant d’articles, le seul résultat sur le sujet connu à ce jour : la série génératrice des triangulations (bien) coloriées avec couleurs est différentiellement algébrique : elle satisfait une équation différentielle non linéaire.

• Jean Paul Bultel Propriétés combinatoires de l’algèbre de Faà di Bruno non commutative
  Résumé

  L’algèbre de Faà di Bruno est l’algèbre de Hopf des fonctions polynomiales sur le groupe des difféomorphismes formels de la droite tangents à l’identité. Le calcul de son antipode est équivalent à la formule d’inversion de Lagrange, qui donne l’inverse (au sens de la composition) de n’importe quelle série formelle inversible à une variable à coefficients dans une algèbre commutative. Les séries formelles à une variable à coefficients dans une algèbre non commutative peuvent également être composées (par substitution de la variable), mais la loi correspondante n’est pas associative, et ne forme donc pas un groupe. Cependant, l’analogue de l’algèbre de Faà di Bruno existe quand même dans ce contexte. Le principal résultat que l’on donne ici est une nouvelle interprétation combinatoire de l’inversion de Lagrange non commutative, ou, plus précisément, de la formule de Brouder-Frabetti-Krattenthaler pour l’antipode de l’algèbre de Faà di Bruno non commutative.
• Philippe Chassaing Automate cellulaire probabiliste et chemins coalescents
  Résumé

  On exhibera un Automate Cellulaire Probabiliste (PCA) sur , non-ergodique alors qu’il a une unique mesure invariante. Cela clos par la négative une ancienne conjecture selon laquelle l’unicité de la mesure invariante implique l’ergodicité pour les PCA. Lors de l’étude du PCA, apparaissent nombres de Catalan et “vicious walkers”.
• Hayat Cheballah Autour des ASMs et des TSSCPPs
  Résumé

  On s’intéresse ici à construire une bijection entre deux familles d’objets combinatoires : les ASMs et les TSSCPPs ou, selon Zeilberger, entre les triangles Gog et les triangles Magog.

  Jusqu’à présent, seule une bijection entre les trapèzes à une ligne était connue, et l’étape suivante, celle des trapèzes à deux lignes, semblait inaccessible. Nous proposons de résoudre ce problème grâce à l’utilisation d’un outil fondamental en combinatoire, l’involution de Schützenberger. Cette construction laisse entrevoir la possibilité d’une solution complète du problème, en traitant les trapèzes à nombre arbitraire de lignes.

• Jean Fromentin Sur le Frobenius des semi-groupes numériques
  Résumé

  Un semi-groupe numérique est une sous-partie des entiers stable par addition tel que soit fini. Tout semi-groupe numérique peut être décrit à l’aide d’un ensemble fini de générateurs. Il est alors naturel d’essayer d’obtenir des propriétés attachées aux semi-groupes à partir d’un tel système de générateurs. Un problème typique est le problème dit de “Frobenius” ou de “rendu de monnaie” qui consiste à trouver le plus grand entier de où est un semi-groupe numérique donné par générateurs. Le but de l’exposé est de présenter les difficultés posées par ce problème de Frobenius ainsi que quelques résultats obtenus : algorithmes de résolution, semi-groupes particuliers, complexité, …
• Samuele Giraudo Construction d’opérades combinatoires à partir de monoïdes et application aux algèbres de Hopf combinatoires
  Résumé

  L’objectif de cet exposé est d’introduire une construction qui, sur la donnée d’un monoïde, produit une opérade ensembliste. Nous appliquons cette construction sur divers monoïdes et obtenons de nouvelles opérades basées sur des objets combinatoires familiers comme des arbres plans enracinés, des chemins de Dyck généralisés, des animaux dirigés, etc. Nous retrouvons également des opérades déjà connues comme l’opérade diassociative de Loday, l’opérade commutative associative et l’opérade magmatique. En utilisant un procédé qui associe à une opérade ensembliste une algèbre de Hopf, nous construisons, à partir de l’une des opérades obtenues, une algèbre de Hopf sur les forêts d’arbres plans, similaire à l’algèbre de Hopf de Connes-Kreimer.
• Bodo Lass Démonstration de la conjecture de Dumont
  Résumé

  Dominique Dumont a conjecturé une identité merveilleuse qui généralise, notamment, les résultats classiques de Lagrange, Gauss, Jacobi et Kronecker sur les décompositions de tout entier en deux, trois et quatre carrés. Nous donnons une preuve combinatoire de la conjecture de Dumont.
• Régine Marchand Modèles de compétition entre espèces
  Résumé

  Le modèle de percolation de premier passage a été introduit par Hammersley et Welsh pour modéliser un matériau poreux. Sur le réseau , on associe aux arêtes une collection de v.a. i.i.d. positives représentant, pour chaque arête, le temps que met le fluide à la traverser : ceci permet de munir le graphe d’une distance aléatoire. On s’intéresse alors à l’ensemble des points qui peuvent être mouillés avant l’instant quand on met une source de fluide à l’origine au temps 0 : il s’agit aussi de la boule de rayon pour la distance aléatoire sur le graphe. Nous essaierons de faire un panorama des résultats classiques ainsi que des questions ouvertes sur ce modèle :

  • Quel est le comportement asymptotique de quand tend vers ?
  • Quelles sont les fluctuations de ?
  • Dans quelle mesure la croissance de dépend-elle de la loi du temps de passage d’une arête ?

  Ce modèle de croissance peut aussi être utilisé pour représenter le développement d’une espèce, et on peut le généraliser pour modéliser la compétition de plusieurs espèces pour la conquête d’un territoire. On s’intéresse alors à la possibilité de coexistence.

  • Dans quels cas la coexistence est-elle possible ?
  • Combien d’espèces peut-on faire coexister, et comment ce nombre est-il relié aux propriétés de la croissance d’une seule espèce ?
• Kilian Raschel Marches dans un quart de plan : quelques avancées récentes
  Résumé

  Dans cet exposé nous présenterons quelques avancées récentes concernant la théorie des marches confinées dans un quart de plan, théorie dont l’objet principal d’étude est la série comptant le nombre de chemins avec point de départ, point d’arrivée et longueur fixés. Nous nous intéresserons notamment à l’holonomie de ces modèles, au travers de propriétés fines de la série de comptage. Nous proposerons également une nouvelle approche, dite par compensation, qui permet de répondre à de nombreuses questions.
• Gilles Schaeffer Une preuve bijective de la formule d’Hurwitz pour le nombre de factorisations minimales transitives d’une permutation en transpositions.
  Résumé

  En 1891, Hurwitz donne une jolie formule multiplicative pour dénombrer certains revêtements ramifiés de la sphère par elle-même, qui en termes combinatoires correspondent aux -uplets de transpositions engendrant un sous-groupe transitif de et dont le produit est une permutation à cycles de longueurs fixées par une partition .

  Cette formule admet plusieurs preuves, mais jusqu’ici aucune d’entre elle n’en donnait une interprétation combinatoire. Nous montrons qu’il faut l’interpréter comme dénombrant certains arbres étiquetés (variantes des arbres de Cayley), et qu’il est alors possible de la prouver bijectivement en passant par l’intermédiaire de cartes planaires croissantes.

  L’exposé s’appuie sur des travaux menés avec Enrica Duchi et Dominique Poulalhon, dans le cadre du projet ExploreMaps.

• Andrea Sportiello A refined Razumov-Stroganov correspondence
  Résumé

  We introduce and prove a one-parameter refinement of the Razumov-Stroganov correspondence. On the ‘FPL side’, fully-packed loop configurations are refined according both to the link pattern and to the unique straight-line tile at the bottom row (if it is at column , we get a weight ). On the ‘DLM side’, the ground state of Hamiltonian of the Dense Loop Model is replaced by the ground state of the Scattering Matrix (and in fact ). Among other things, our analysis provides an alternate proof of the original Razumov-Stroganov correspondence, and the first proof of a conjecture formulated by Di Francesco in 2004.
• Hanane Tafat Bouzid Automates et grammaires algébriques : universalité de l’asymptotique et biodiversité des lois limites
  Résumé

  Pour n’importe quel langage , nous allons considérer la série génératrice bivariée

  où est le nombre de mots de longueur avec occurrences d’un motif préalablement fixé. À chaque grammaire engendrant , est associée un graphe de dépendance où chaque non terminal devient un sommet qui est relié aux non terminaux qui interviennent dans ses règles de production.

  En ce qui concerne les grammaires régulières (i.e. les automates), la série génératrice est rationnelle. Si le graphe de dépendance est fortement connexe, alors le comportement asymptotique des coefficients et la loi limite associée sont connus. Nous allons compléter ces résultats en donnant les lois limites atteignables lorsque le graphe de dépendance est non fortement connexe.

  En ce qui concerne les grammaires algébriques, la série génératrice est… algébrique. Si le graphe de dépendance est fortement connexe, alors le théorème de Drmota-Lalley-Woods fournit le comportement asymptotique des coefficients et la loi limite associée. Nous exhibons les comportements asymptotiques atteignables dans le cas d’un graphe de dépendance non fortement connexe.

  Nous présentons des applications à la génération aléatoire (via la méthode de Boltzmann) et à la bioinformatique (via un algorithme de programmation dynamique pour un problème de segmentation).

Emploi du temps

Mercredi 1 février

Jeudi 2 février

Vendredi 3 février

Participants

• Michele D’Adderio (Max-Planck-Institut für Mathematik Bonn)
• Marie Albenque (LIX, CNRS, Ecole Polytechnique)
• Jean-Christophe Aval (LaBRI, Bordeaux)
• Axel Bacher (LIX, Ecole Polytechnique)
• Cyril Banderier (LIPN, Université Paris XIII)
• Frédérique Bassino (LIPN, Paris XIII)
• Jean Bétréma (LaBRI, Bordeaux)
• Nicolas Bonichon (LaBRI, Bordeaux)
• Yvan Le Borgne (LaBRI, Bordeaux)
• Nicolas Borie (Laboratoire de Mathématiques, Orsay)
• Mireille Bousquet-Mélou (LaBRI, Bordeaux)
• Adrien Boussicault (LaBRI, Bordeaux)
• Jérémie Bouttier (CEA, Saclay)
• Mathilde Bouvel (LaBRI, Bordeaux)
• Nicolas Broutin (INRIA, Rocquencourt)
• Jean Paul Bultel (LaBRI, Bordeaux)
• Jérôme Casse (ENS, Paris)
• Guillaume Chapuy (LIAFA, Paris 7)
• Philippe Chassaing (IECN, Nancy)
• Brigitte Chauvin (LMV, Versailles)
• Hayat Cheballah (LIPN, Paris 13)
• Julien Clément (CNRS, Univ. Caen)
• Gwendal Collet (LIX, Ecole Polytechnique)
• Robert Cori (LaBRI, Bordeaux)
• Bruno Courcelle (IUF, LaBRI, Bordeaux)
• Julien Courtiel (LaBRI, Bordeaux)
• Sandrine Dasse-Hartaut (LIAFA, Paris 7)
• Enrica Duchi (LIAFA, Paris 7)
• Philippe Duchon (LaBRI, Bordeaux)
• Valentin Feray (LaBRI, Bordeaux)
• Luca Ferrari (Università di Bologna, Italie)
• Jean Fromentin (LMPA, Université du Littoral Côte d’Opale)
• Samuele Giraudo (IGM, Paris-Est)
• Olivier Guibert (LaBRI, Bordeaux)
• Matthieu Josuat-Vergès (Institut Gaspard Monge, Paris- Est Marne la Vallée)
• Frédéric Jouhet (Institut Camille Jordan, Université Lyon 1)
• Bodo Lass (Institut Camille Jordan, Université Lyon 1)
• Régine Marchand (IECN, Nancy)
• Jean-François Marckert (LaBRI, Bordeaux)
• Michel Marcus (LaBRI, Bordeaux)
• Rémi Maurice (LIGM Marne-la-Vallé)
• Pierre-Loïc Méliot (Institut für Mathematik - Universität Zürich)
• Basile Morcrette (Inria Rocquencourt, LIP6 UPMC)
• Philippe Nadeau (Institut Camille Jordan, Lyon)
• Jean-Christophe Novelli (LIGM Marne-la-Vallée)
• Adeline Pierrot (LIAFA, Paris 7)
• Viviane Pons (LIGM Marne-la-Vallée)
• Dominique Poulalhon (LIX, CNRS, École polytechnique)
• Louis-Francois Preville-Ratelle (Universite du Quebec a Montreal)
• Nicolas Pouyanne (LMV, Versailles)
• Kilian Raschel (LMPT, Tours)
• Yi Ren (LaBRI, Bordeaux)
• Marc Sage (LIGM, Marne-la-Vallée)
• Gilles Schaeffer (LIX, CNRS, Ecole Polytechnique)
• Thomas Selig (LaBRI, Bordeaux)
• Andrea Sportiello (Milan university)
• Hanane Tafat (LIPN, université Paris XIII)
• Omar Tout (LaBRI, Bordeaux)
• Mario Valencia-Pabon (LIPN, Paris XIII)
• Ekaterina Vassilieva (LIX, Ecole Polytechnique)
• Vincent Vong (LIGM, Marne-la-Vallée)
• Alexandre Zvonkine (LaBRI, Bordeaux)

Organisateurs

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

Soutien financier

• Projet ANR A3
• ANR PSYCO
• LaBRI