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

Les JCB 2009 ont eu lieu du mercredi 4 au vendredi 6 février 2009, 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.

• Marie Albenque Enumération de tresses et partitions non-croisées.
  Résumé

  Je montrerai dans cet exposé comment la théorie des empilements de Viennot peut être étendue à une large classe de monoides. Ceci permet notamment de ramener l’énumération des éléments du monoïde à celle d’un ensemble fini. J’expliquerai ensuite comment appliquer cette méthode à l’énumeration des monoïdes de tresses. Dans ce cas le calcul se ramène à l’énumération de partitions non-croisées, ce qui nous permet d’obtenir de manière explicite la serie génératrice des monoides duaux de tresses.
• Nicolas Bonichon Permutations de Baxter et orientations bipolaires
  Résumé

  Nous présenterons une bijection directe entre les permutations de Baxter de taille n et les orientations bipolaires planes à n arêtes. Cette bijection transporte plusieurs paramètres classiques des permutations de Baxter (nombre de montées, nombre de descentes, nombre de saillants supérieurs gauches, …) vers des paramètres tout aussi classiques des orientations bipolaires planes (nombre de faces internes, nombre de sommets, degré du puits …). De plus cette bijection produit des dessins polylines compacts pour les cartes considérées. Nous présenterons également 2 spécialisations de cette bijection.

  Travail réalisé en collaboration avec Mireille Bousquet-Mélou et Eric Fusy.

• Jérémie Bouttier Géodésiques dans les grandes quadrangulations aléatoires
  Résumé

  Je m’intéresserai aux propriétés métriques des quadrangulations planaires aléatoires, et plus particulièrement aux géodésiques (chemins de longueur minimale). Par des méthodes combinatoires, je calculerai le nombre moyen de géodésiques reliant deux points donnés, et d’autres quantités similaires. Je considérerai ensuite la limite d’échelle, correspondant à un espace métrique continu aléatoire. Nos résultats indiquent que deux points typiques sont reliés par une unique géodésique continue (limite de toutes les géodésiques discrètes), en accord avec les travaux récents de Miermont et de Le Gall. Il existe cependant quelques points exceptionnels d’où partent des géodésiques distinctes. Je m’intéresserai enfin à la surprenante propriété de “confluence” des géodésiques.
• Mathilde Bouvel Pin-permutations et structure dans les classes de permutations
  Résumé

  Les classes de permutations sont des ensembles de permutations fermés par le bas pour la relation de motif (ou sous-permutation). Toute classe peut être caractérisée par un ensemble (fini ou infini) de motifs interdits, appelé base de la classe. Une classe de permutations est souvent définie par sa base, mais peut aussi l’être par une propriété (par exemple graphique) des permutations de la classe. Sans forcément connaitre la base d’une classe, on peut se demander si cette classe a de bonnes propriétés en termes de structure, en particulier si on sait énumérer les permutations de cette classe, si sa série génératrice est rationnelle ou algébrique, si on a une caractérisation (par exemple récursive) des permutations de la classe…

  Albert et Atkinson ont donné des propriétés de la série génératrice d’une classe en fonction du nombre (fini ou infini) de permutations simples dans cette classe. Pour identifier si une classe contient un nombre fini de permutations simples, Brignall, Ruškuc et Vatter décrivent une procédure qui utilise les pin-permutations. Avant d’être un outil pour trouver des propriétés de structures dans d’autres classes, les pin-permutations forment elles-même une classe, définie par une propriété et non par sa base. On donne une caractérisation des pin-permutations à travers leurs arbres de décomposition, qui nous permet de trouver la série génératrice de cette classe. En particulier, cette série génératrice est rationnelle, prouvant une conjecture de Brignall, Ruškuc et Vatter. On étudie aussi la base de cette classe, et on prouve qu’elle est infinie.

• Julien Cassaigne Le mot de Fibonacci est-il toujours optimal ?
  Résumé

  Le mot infini de Fibonacci, f = abaababaabaababaababaabaababaabaababaa… est sans doute l’un des exemples les plus souvent cités dans la théorie des mots infinis. C’est l’archétype des mots sturmiens, et il est aussi point fixe d’une substitution très simple : $a \to ab$, $b \to a$.

  Dans de nombreuses situations, le mot de Fibonacci se révèle avoir des propriétés optimales, au sens qu’une certaine quantité définie sur tous les mots infinis est minimale (ou maximale) pour ce mot. Dans cet exposé, nous présentons plusieurs situations de ce type, et aussi d’autres situations où le mot de Fibonacci n’est pas optimal. Nous considérons trois classes de problèmes différentes, faisant intervenir les répétitions fractionnaires, la notion de récurrence, et les palindromes. Au passage, nous rencontrons plusieurs problèmes ouverts.

• Guillaume Chapuy Une bijection pour les cartes unicellulaires, et une nouvelle identité combinatoire
  Résumé

  En recollant deux à deux les arêtes d’un 2n-gone, on forme une surface topologique, sur laquelle la trace du 2n-gone de départ forme le dessin d’un graphe à n arêtes. Un tel objet est appelé une carte unicellulaire.

  On sait énumérer ces objets par des méthodes abstraites (intégrales de matrices ou méthodes algébriques), mais la simplicité des formules obtenues laisse croire à une interprétation combinatoire: c’est justement cette interprétation que je donnerai, via une construction directe des cartes unicellulaires de genre donné à partir des arbres de Catalan. Cela donne une nouvelle identité combinatoire, à plusieurs égards plus simple que les formules précédemment connues (Harer-Zagier ou Lehman-Walsh).

• Patrick Dehornoy Sur la distance de rotation entre deux arbres binaires
  Résumé

  Le problème est de construire des arbres binaires de taille n qui soient éloignés vis-a-vis de la distance de rotation, ce qui équivaut à construire des expressions parenthésées a n variables éloignées vis-à-vis du deplacement de parenthèses par associativité, ou encore des triangulations d’un n + 2-gone éloignées vis-à-vis de l’échange de diagonales. On présentera la magnifique solution de Sleator-Tarjan-Thurston basée sur la géometrie hyperbolique, qui est optimale mais valable seulement pour n grand (non effectif), ainsi qu’une solution combinatoire récente basée sur la notion de séparatrice dans les associaèdres, qui est (pour le moment) non optimale, mais valable pour tout n.
• Philippe Duchon Combinatoire des configurations de boucles compactes
  Résumé

  La conjecture de Razumov et Stroganov affirme qu’il existe un lien inattendu entre deux familles d’objets combinatoires bien distincts: la grande famille des objets comptés par les nombres de Catalan (ici sous la forme de couplages plans) d’une part, et les matrices à signes alternants d’autre part (sous la forme équivalente des “configurations de boucles compactes”).

  Ces dernières présentent des aspects combinatoires très riches, qui permettent entre autres de compter et d’engendrer aléatoirement des objets présentant des conditions de symétrie variées. Je présenterai un certain nombre de ces aspects, ainsi qu’une palette de nouvelles conjectures “à la Razumov-Stroganov”.

• Valentin Féray Une variante du théorème des mariages liée aux polynômes de Kerov
  Résumé

  Le théorème des mariages de Hall donne une condition nécessaire et suffisante pour l’existence d’un couplage total dans un graphe bipartite. Nous allons donner une condition similaire pour l’apparition de ce couplage après itération de transformations simples sur le graphe. Cette question provient de l’étude des polynômes de Kerov. Ceux-ci expriment les caractères irréductibles du groupe symétrique en fonction des cumulants libres de la partition (une suite d’entiers codant de manière pratique un diagramme de Young). Le résultat ci-dessus nous permettra de donner une interprétation combinatoire de leurs coefficients, qui comptent certaines permutations du groupe symétrique.
• Frédéric Jouhet Partitions d’entiers, q-séries et lemme de Bailey
  Résumé

  Une partition de l’entier n est une suite décroissante d’entiers positifs dont la somme vaut n. A partir de cette définition combinatoire, nous rappellerons quelques identités de séries hypergéométriques basiques (ou q-séries) que l’on peut interpréter en termes de fonctions génératrices de partitions d’entiers. Nous expliquerons ensuite comment obtenir facilement de telles identités de q-séries à partir du lemme de Bailey. Enfin, nous verrons comment appliquer le lemme de Bailey pour prouver des “conjectures des dénominateurs”, liées aux questions diophantiennes sur les valeurs de la fonction zêta aux entiers positifs (et leurs q-analogues).
• Olivier Mallet Autour des surpartitions et des identités de type Rogers-Ramanujan
  Résumé

  Une partition d’un entier positif est une façon d’écrire ce nombre comme une somme d’entiers strictement positifs où l’ordre des termes ne compte pas. Plusieurs généralisations des partitions ont été étudiées, parmi lesquelles les surpartitions, qui sont des partitions où l’on peut surligner la dernière occurrence d’un nombre, les paires de surpartitions ou encore les partitions n-colorées, qui sont liées à un modèle de physique statistique. On présente une généralisation aux paires de surpartitions les identités d’Andrews-Gordon, qui sont une extension d’un résultat classique de la théorie des partitions : les identités de Rogers-Ramanujan. Pour cela, on définit deux classes de séries hypergéométriques basiques et on montre que ce sont les séries génératrices des paires de surpartitions vérifiant différents types de conditions (multiplicités, rangs successifs, dissection de Durfee) et de certains chemins du plan. On montre également que pour certaines valeurs des paramètres, ces séries peuvent s’écrire comme des produits infinis, ce qui conduit à plusieurs identités de type Rogers-Ramanujan. La démonstration utilise diverses méthodes combinatoires et analytiques. On définit enfin une généralisation des partitions n-colorées, les surpartitions n-colorées, et on les utilise pour interpréter combinatoirement certaines séries multiples et démontrer d’autres identités de type Rogers-Ramanujan.
• Carine Pivoteau Calcul efficace de l’oracle de Boltzmann
  Résumé

  La génération aléatoire sous le modèle de Boltzmann repose sur les valeurs des séries génératrices en des points intérieurs à leur disque de convergence. Le calcul de ces valeurs est traditionnellement relégué à un “oracle”. Nous produisons un tel oracle pour une grande classe de structures spécifiées par des systèmes combinatoires. Cet oracle repose sur une itération de Newton au niveau des structures combinatoires elles-même, généralisant des travaux de Bergeron, Décoste, Labelle et Leroux. Il en découle aussi un algorithme quasi-optimal pour le calcul des séries génératrices d’énumération.
• Bruno Salvy Identités de suites et fonctions spéciales : D-finitude et au-delà
  Résumé

  L’algorithme de création télescopique de Zeilberger permet la sommation et l’intégration définie de nombreuses suites et fonctions spéciales. Il repose sur la théorie des D-modules holonomes qui fournit une condition suffisante de succès. Nous étendons cette approche en remplaçant l’holonomie par une condition plus légère sur la dimension de certains idéaux d’opérateurs. Ceci permet de traiter des sommes ou intégrales où interviennent des nombres de Stirling ou de Bernoulli, des fonctions Gamma incomplètes, des polyzêtas, … Notre approche unifie des extensions existantes de l’algorithme de Zeilberger, et ouvre la porte au traitement de sommes et d’intégrales qui n’étaient pas accessibles au calcul formel.

  Il s’agit d’un travail en commun avec Frédéric Chyzak et Manuel Kauers.

• Nicolas Thiéry Quelques structures relationnelles de profil polynomial et leurs algèbres d’âges
  Résumé

  Le profil d’une structure relationnelle $R$ est la fonction $\varphi_R$ qui compte, pour tout entier $n$, le nombre $\varphi_R(n)$, éventuellement infini, de sous structures induites de taille $n$, considérées à isomorphie près (exemple: compter les graphes simples à isomorphie près). Si $\varphi_R$ prend seulement des valeurs finies, c’est la fonction de Hilbert d’une algèbre graduée commutative associée à $R$, l’algèbre d’âge $A(R)$ introduite par P. J. Cameron.

  Dans cet exposé, nous présentons plus en détail cette association, en particulier dans le cas où la structure relationnelle $R$ admet une décomposition monomorphe finie. Ce cadre contient des algèbres bien connues comme les algèbres d’invariants des groupes de permutations ou les algèbres de polynômes quasi-symétriques.

  Nous étudions jusqu’à quel point les propriétés algébriques bien connues de ces dernières (Cohen-Macaulay, …) s’étendent aux algèbres d’âge au fur et à mesure que l’on élargit le cadre. En particulier, nous donnons une caractérisation combinatoire sur la structure relationnelle de l’engendrement fini de l’algèbre.

  Réciproquement, nous montrons que $\varphi_R$ est ultimement un quasi-polynôme, ce qui soutient la conjecture que, sous des hypothèses faibles sur $R$, $\varphi_R$ est ultimement un quasi-polynôme dès que sa croissance est bornée par un polynôme.

• Alexander Zvonkin Dessiner les fonctions rationnelles
  Résumé

  Une fonction rationnelle d’une variable complexe est une application de la sphère complexe de Riemann vers elle-même. Prenant un très simple dessin sur la sphère-destinée et considérant son image réciproque, on obtient un dessin sur la sphère de départ qui peut être, selon le cas, un arbre, un cactus, une carte, une hypercarte, etc. Ce dessin rend géométriquement lisibles certaines propriétés de la fonction rationnelle en question et parfois permet de trouver des solutions étonnamment faciles à des problèmes notoirement difficiles.

Emploi du temps

Mercredi 4 février

Jeudi 5 février

Vendredi 6 février

Participants

• Ali Akhavi (GREYC, Caen)
• Marie Albenque (LIAFA, Paris 7)
• Jean-Christophe Aval (LaBRI, Bordeaux)
• Axel Bacher (LaBRI, Bordeaux)
• Christine Bachoc (IMB, Bordeaux)
• Cyril Banderier (LIPN, Paris 13)
• Frédérique Bassino (LIPN, Paris 13)
• Nicolas Bedaride (LATP, Marseille)
• Bernard Bercu (IMB, Bordeaux)
• Jean Bétréma (LaBRI, Bordeaux)
• Nicolas Bonichon (LaBRI, Bordeaux)
• Mireille Bousquet-Mélou (LaBRI, Bordeaux)
• Adrien Boussicault (Institut Gaspard Monge, Marne la Vallée)
• Jérémie Bouttier (CEA, Saclay)
• Mathilde Bouvel (LIAFA, Paris 7)
• Nicolas Broutin (INRIA, Rocquencourt)
• Julien Cassaigne (IML, Luminy)
• Guillaume Chapuy (LIX, Palaiseau)
• Brigitte Chauvin (INRIA, IVersailles)
• Bruno Courcelle (LaBRI, Bordeaux)
• Patrick Dehornoy (LMNO, Caen)
• Philippe Duchon (LaBRI, Bordeaux)
• Delphine Féral (IMB, Bordeaux)
• Valentin Féray (Institut Gaspard Monge, Marne la Vallée)
• Olivier Guibert (LaBRI, Bordeaux)
• Matthieu Josuat-Vergès (LRI, Paris-Sud)
• Frédéric Jouhet (Institut Camille Jordan, Lyon 1)
• Nicolas Hanusse (LaBRI, Bordeaux)
• Mamadou Kanté (LaBRI, Bordeaux)
• Yvan Le Borgne (LaBRI, Bordeaux)
• Florent Le Gac (LaBRI, Bordeaux)
• Olivier Mallet (LIAFA, Paris)
• Jean-François Marckert (LaBRI, Bordeaux)
• Anne Micheli (LIAFA, Paris 7)
• Jean-Guy Penaud (LaBRI, Bordeaux)
• Carine Pivoteau (LIP6, Paris 6)
• Yann Ponty (LIAFA (ANR GAMMA), Paris 7)
• Dominique Poulalhon (LIAFA, Paris 7)
• Nicolas Pouyanne (LAMA, Versailles)
• Michael Rao (LaBRI, Bordeaux)
• Hejer Rejeb (LaBRI/INRIA, Bordeaux)
• Bruno Salvy (INRIA, Rocquencourt)
• Nicolas Thiéry (Dept. de Maths, Marne la Vallée)
• Xavier Viennot (LaBRI, Bordeaux)
• Julian West (CNRS/Ecole Polytechnique, Palaiseau)
• Gilles Zémor (IMB, Bordeaux)
• Alexander Zvonkin (LaBRI, Bordeaux)

Organisateurs

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

Soutien financier

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