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

Les JCB 2014 ont eu lieu du mercredi 12 au vendredi 14 février 2014, 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.

• Luca Castelli Aleardi Forêts de Schnyder en genre supérieur: du codage au dessin de graphes
  Résumé

  Les forêts de Schnyder (et les ordres canoniques) fournissent des jolies structures combinatoires permettant de comprendre de manière fine et profonde la notion de planarité d’un graphe. Parmi les très nombreuses applications (génération exhaustive et aléatoire, codages succincts et compression, spanners de graphes planaires, critères de planarités, …) l’une des premières application conduit à deux algorithmes de dessin, très simples et élégants, permettant de dessiner un graphe planaire à n sommets sur une grille dont l’aire est quadratique en n. L’une des formulations plus connues des forêts de Schnyder est probablement celle donnée pour la famille des triangulations planaires, pour lesquelles les arêtes internes se partitionner en 3 arbres couvrants de l’ensemble des sommets, chacun ayant comme racine l’un des trois sommets incidents à la face externe. Dans cet exposé nous allons esquisser quelques généralisations de ces structures combinatoires récemment formulées pour les cas des triangulations toriques et de genre supérieur, qui ont conduit à des algorithmes éfficaces de dessin et de codage pour des graphes plongés sur les surfaces.
• Nicolas Broutin La limite d’échelle de l’arbre couvrant de poids minimal du graphe complet
  Résumé

  On considère l’arbre couvrant minimum d’un graphe complet dont les arêtes sont pondérées aléatoirement et indépendamment. J’introduirai la convergence des graphes lorsqu’on les considère comme des espaces métriques (avec la distance de graphe). Puis, je montrerai comment un mélange de combinatoire, d’analyse d’algorithmes et de probabilités conduit à une construction de la limite de l’arbre couvrant minimum (une fois renormalisé). J’expliquerai aussi dans quelle mesure l’objet limite est une fractale (aléatoire) intéressante.
• Julien Courtiel Un cadre général pour l’activité et le polynôme de Tutte
  Résumé

  On retrouve dans la littérature plusieurs descriptions du polynôme de Tutte d’un graphe. Tutte l’a notamment défini grâce à une notion d’activité basée sur un étiquetage ordonné des arêtes. Plus récemment, Bernardi a donné une notion non équivalente de l’activité où le graphe est plongé dans une surface. On verra que d’autres notions d’activité peuvent être ainsi imaginées et qu’elles se regroupent toutes en une seule et même définition. On en profitera pour comprendre macroscopiquement le lien entre les différentes expressions du polynôme de Tutte. Aucun prérequis ne sera nécessaire pour assister à cet exposé.
• Maciej Dolega Central limit theorem for random Young diagrams with respect to Jack measure
  Résumé

  In 1977 Vershik and Kerov and independently Logan and Shepp discovered that large random Young diagrams with respect to Plancherel measure concentrate around some explicit limit shape. In 1993 Kerov showed that the fluctuations around that limit shape are Gaussian. Jack measure is a probability measure on the set of Young diagrams of fixed size which is parametrized by a positive real value . For Jack measure coincide with the Plancherel measure, hence it can be considered as a continous deformation of the Plancherel measure. We present a central limit theorem for the Jack measure which gives an extension of the results of Vershik-Kerov (Logan-Shepp) and Kerov for the Plancherel measure.
• Bertrand Eynard combinatoire des graphes de Strebel, des équations de Tutte au theoreme de Kontsevich Witten
  Résumé

  Les graphes de Strebel sont des cartes (planaires, ou bien en genre donné), dont les arêtes portent des longueurs données (réelles positives). Ils ont étés introduits, car il existe une bijection (homéomorphisme d’orbifold) entre l’espace des modules des surfaces de Riemann de genre g avec n points marqués, et l’ensemble des graphes de Strebel de genre g avec n faces. Les invariants topologiques, par exemple les classes de Chern dans l’espace des modules, s’écrivent très simplement en terme des longueurs d’arêtes des graphes (ceci est du à Penner, Harrer, Zagier, Kontsevich,…). Nous étudions la récurrence de Tutte sur ces graphes (ouverture de l’arête marquée). Cette récurrence se résout explicitement, et donne ainsi une preuve des “contraintes de Virasoro” pour les espaces de modules. Nous verrons aussi comment ceci donne une preuve combinatoire que la fonction génératrice de ces graphes est la fonction tau de la hiérarchie KdV (donc une nouvelle preuve du théorème de Witten-Kontsevich). Nous mentionnerons la généralisation aux graphes de spin r, menant ainsi à une preuve combinatoire de la “conjecture r-spin de Witten” (démontrée très récemment), qui dit que la fonction génératrice doit être la fonction tau de r-KdV. Ceci permet aussi de prouver des conjectures de Faber-Pandaripande sur les nombres d’intersections (intégrales de classes de Chern et de classes de Witten).
• Thomas Fernique Distances sur les pavages par losanges
  Résumé

  Il est connu que l’ensemble des pavages par losanges d’une région simplement connexe du plan euclidien est connexe par flips (un flip est l’opération élémentaire consistant à tourner de 180° un hexagone formé de trois losanges). Motivés par l’étude de la formation des quasicristaux, nous cherchons ici à mieux comprendre à quel point un tel ensemble est “bien” connecté par flips. Nous introduisons une borne inférieure (la distance de Hamming) sur le nombre minimal de flips pour relier deux pavages (la distance de flip) et nous étudions l’optimalité de cette borne.

  Il s’agit d’un travail en commun avec Olivier Bodini, Michael Rao et Eric Rémila.

• Jérémie Lumbroso Génération aléatoire exacte de Boltzmann avec un oracle approximatif
  Résumé

  La génération aléatoire de Boltzmann, introduite par Duchon et al. en 2002, permet de tirer uniformément des objets combinatoires, à taille approchée en évaluant — généralement en un nombre constant de points — les séries génératrices associées pour obtenir les bonnes probabilités.

  Cette évaluation de séries génératrices (notamment à proximité de leur singularité) est longtemps demeuré un aspect inachevé de la méthode. En 2008, Pivoteau et al. ont apporté une vaste réponse à cette question en introduisant un cadre d’itération efficace avec convergence quadratique. Pour des raisons pratiques, les évaluations — bien que pouvant être obtenues avec une précision arbitraire — sont souvent toujours réalisées avec une précision tronquée en raisonnant que l’impact sur l’uniformité des objets est négligeable.

  Nous présentons une nouvelle approche complémentaire, qui consiste à se servir de la technique du rejet, traditionnelle dans la simulation de lois aléatoires (et déjà employée dans Boltzmann pour un autre aspect de la génération — le contrôle de la taille), afin d’obtenir une génération exacte à partir d’évaluations approchées, voire même grossières. En contrepartie, ces approximations se paient par un rejet supplémentaire qui est fonction de leur (im)précision.

  Ce travail est pertinent pour compléter les approches précédentes, en assurant une génération prouvablement exacte même avec des valeurs tronquées à 10, 20, 40 décimales. Mais il semble surtout de première utilité pour les classes combinatoires qui requièrent l’évaluation de leur série génératrice en un nombre non constant de point (par exemple les arbres d’Otter, binaires non plans).

  Travail en commun avec Olivier Bodini et Nicolas Rolin.

• Cécile Mailler Classes d’équivalence d’arbres et/ou, application au problème SAT pour les arbres de Catalan
  Résumé

  Un arbre booléen est un arbre binaire plan dont les nœuds internes sont étiquetés par des connecteurs logiques (ici, et et ou) et dont les feuilles sont étiquetées par des littéraux, éléments de l’ensemble . Je présente dans cet exposé un nouveau modèle d’arbres booléens et/ou aléatoires dans lequel le nombre de variables distinctes étiquetant un arbre à feuilles est borné par – étant une suite croissante et tendant vers quand tend vers . On dit que deux arbres sont équivalents s’ils ont la même forme, si leurs étiquettes internes (et et ou) sont les mêmes et si les étiquettes de leurs feuilles sont les mêmes à renumérotation près. Nous pouvons ainsi compter les classes d’équivalence d’arbres par combinatoire analytique et étudier la distribution induite sur l’ensemble des classes d’équivalence de fonctions booléennes. Il s’avère que ce modèle ressemble au modèles sat de la littérature, notamment le modèle 3–sat, mais sans la contrainte de structure.
• Pierre-Loic Méliot L’algèbre des isomorphismes partiels
  Résumé

  Si est une famille croissante de groupes finis, une limite projective permet de mener des calculs génériques sur tous les groupes Gn simultanément. Plus généralement, on peut utiliser à cet effet une algèbre A qui se projette sur toutes les algèbres de groupes CGn. Pour les groupes symétriques, une construction de ce type a été proposée par Ivanov et Kerov à la fin des années 90, à partir de la classe combinatoire des permutations partielles.

  Nous expliquerons comment utiliser la combinatoire des espaces vectoriels sur les corps finis pour adapter cette construction au cas des groupes GL(n, Fq). Ainsi, nous construirons des algèbres d’isomorphismes partiels, qui permettent d’établir des résultats de polynomialité pour les coefficients de structure des centres Z(CGL(n, Fq)).

• Viviane Pons Intervalles du treillis de Tamari
  Résumé

  Nous présentons un nouvel objet représentant les intervalles du treillis de Tamari : les intervalles-posets. Ils permettent d’encoder un couple d’éléments comparables (chemins de Dyck ou arbres binaires) et de décrire facilement les rotations élémentaires qui conservent cette comparabilité. Nous utilisons les intervalles-posets pour démontrer combinatoirement l’équi distribution de deux statistiques sur les intervalles.
• Thomas Selig Une extension stochastique du modèle du tas de sable sur un graphe
  Résumé

  Dans le modèle du tas de sable, lorsqu’un sommet devient instable, c’est-à-dire que le nombre de grains en ce sommet dépasse son degré, celui-ci s’éboule en envoyant un grain vers chacun de ses voisins. Dans notre modèle, un sommet instable envoie un grain vers chaque voisin avec probabilité p > 0 (indépendamment pour chaque voisin). On donnera une caractérisation des états récurrents de ce nouveau modèle, en termes d’orientations du graphe. De plus, on introduira un polynôme comptant ces états récurrents selon leur nombre (total) de grains de sable, et on verra que celui-ci satisfait une relation de récurrence qui ressemble celle du polynôme de Tutte.
• Béatrice de Tilière Du modèle d’Ising critique aux arbres couvrants : constructions explicites
  Résumé

  Nous allons montrer une (ou deux) relations explicites entre le carré de la fonction de partition du modèle d’Ising critique et les arbres couvrants, exhibant ainsi une relation forte entre deux modèles de mécanique statistique.
• Omar Tout A polynomiality property for the structure coefficients of the algebra of double-classes
  Résumé

  On considère une suite des paires où est un groupe et un sous-groupe de pour tout n. On s’intéresse aux coefficients de structure de l’algèbre des Kn-double classes. On peut déduire de ces coefficients les coefficients de structure des centres des algèbres des groupes. Dans des cas particuliers comme , et , on a une propriété de polynomialité pour ces coefficients malgré qu’une formule explicite n’existe pas. On présente un résultat général qui nous permet de retrouver la propriété du polynomialité dans ces trois cas.
• Ekaterina Vassilieva Constantes de structure et hypercartes localement orientables : approches bijectives et algébriques
  Résumé

  Cet exposé est dédié à l’évaluation des séries génératrices des constantes de structure de l’algèbre de double classe latérale. Hanlon, Stanley, Stembridge (1992) ont montré que ces séries donnent la distribution spectrale de certaines matrices jouant un rôle important dans la théorie des matrices aléatoires. Nous fournissons une évaluation explicite de ces séries en termes de monômes symétriques. Le problème est envisagé selon deux angles complémentaires : d’une part une approche bijective reposant sur l’interprétation des constantes de structure en question en termes d’hypercartes localement orientables ; d’autre part une approche algébrique basée sur les propriétés remarquables des polynômes zonaux.
• Michael Wheeler Refined Cauchy identities, plane partitions and symmetry classes of alternating sign matrices
  Résumé

  In the theory of symmetric functions, it is well known that Cauchy identities can be interpreted as generating series for plane partitions with specific weightings. For example, in the case of Schur functions, an appropriate specialization of the Cauchy identity leads to MacMahon’s famous generating series for volume-weighted plane partitions. In this talk we will show that some Cauchy identities have “refined” versions, which contain partition functions of the six-vertex model, on relevant domains. This allows us to relate certain generating series of plane partitions to appropriate symmetry classes of alternating sign matrices. We will discuss three such examples in the talk.

  This work is in collaboration with Dan Betea.

Emploi du temps

Mercredi 12 février

Jeudi 13 février

Vendredi 14 février

Participants

• Marie Albenque (LIX, CNRS)
• Jean-Christophe Aval (LaBRI, Bordeaux)
• Axel Bacher (RISC, JKU Linz)
• Frédérique Bassino (LIPN, Paris 13)
• Bétréma (LaBRI, Bordeaux)
• Nicolas Bonichon (LaBRI, Bordeaux)
• Mireille Bousquet-Mélou (LaBRI, Bordeaux)
• Valetin Bonzom (LIPN, Paris 13)
• Nicolas Broutin (Inria, Rocquencourt.)
• Jérôme Casse (LaBRI, Bordeaux)
• Luca Castelli Aleardi (LIX, Saclay)
• Guillaume Chapuy (CNRS, Paris 7)
• Gwendal Collet (LIX, École Polytechnique)
• Bruno Courcelle (LaBRI, Bordeaux)
• Julien Courtiel (LaBRI, Bordeaux)
• Vincent Delecroix (LaBRI, Bordeaux)
• Clément Dervieux (LIAFA, Paris 7)
• Maciej Dolega (LIAFA, Paris 7.)
• Philippe Duchon (LaBRI, Bordeaux)
• Romaric Duvignau (LaBRI, Bordeaux)
• Bertrand Eynard (CEA, Saclay)
• Valentin Féray (Universität Zürich)
• Thomas Fernique (LIPN, Paris 13)
• Wenjie Fang (LIAFA, Paris 7)
• Eric Fusy (LIX, Saclay)
• Lucas Gerin (Ecole Polytechnique)
• Samuele Giraudo (LIGM, Marne la Vallée)
• Olivier Guibert (LaBRI, Bordeaux)
• Alice Jacquot (LIPN, Paris 13)
• Matthieu Josuat-Vergès (LIGM, Marne-la-Vallée)
• Kolja Knauer (LIRMM , Montpellier)
• Vincent Jugé (LIAFA, Paris 7)
• Patxi Laborde-Zubita (IMB, Bordeaux)
• Jérémie Lumbroso (Laboratoire d’Informatique de Paris 6)
• Cécile Mailler (LMV, Université Versailles St-Quentin)
• Thibault Manneville (LIX, École Polytechnique)
• Philippe Marchal (CNRS, Paris 13)
• Pierre-Loic Méliot (Paris 11)
• Jean-François Marckert (LaBRI, Bordeaux)
• Quentin de Mourgues (LIPN, Paris 13)
• François Nunzi (LIAFA, Paris 7)
• Bérénice Oger (ICJ, Lyon)
• Jean-Guy Penaud (LaBRI, Bordeaux)
• Adeline Pierrot (TU Wien)
• Vincent Pilaud (CNRS, LIX, École Polytechnique)
• Viviane Pons (Fakultät für Mathematik, Univ. Vienne)
• David Renault (LaBRI, Bordeaux)
• Thomas Selig (LaBRI, Bordeaux)
• Andrea Sportiello (LIPN, Paris 13)
• Béatrice de Tilière (LPMA, Paris 6)
• Omar Tout (LaBRI, Bordeaux)
• Alexandra Ugolnikova (LIPN, Paris 13)
• Ekaterina Vassilieva (LIX, Palaiseau)
• Michael Wheeler (LPTHE, Paris 6)
• Kerstin Weller (Oxford)
• Akka Zemmari (LaBRI, Bordeaux)
• Alexandre Zvonkine (LaBRI, Bordeaux)

Organisateurs

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

Soutien financier

• ANR PSYCO
• LaBRI