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

Les JCB 2011 ont eu lieu du mercredi 26 au vendredi 28 janvier 2011, 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.

• Axel Bacher Animaux de Klarner
  Résumé

  Un animal sur le réseau carré est un ensemble fini et connexe de sommets, vu à une translation près. Énumérer les animaux de taille (ou aire) fixée est très difficile, de sorte qu’il est intéressant d’étudier des sous-familles d’animaux, plus faciles à compter.

  Klarner, en 1967, a décrit une telle sous-famille et montré qu’elle contenait au moins animaux d’aire . Nous donnerons une nouvelle caractérisation de ces animaux et montrerons des méthodes pour les énumérer.

• Frédérique Bassino Sous-groupes aléatoires du groupe libre
  Résumé

  Soit un alphabet fini. Le groupe libre est l’ensemble des mots réduits composés de lettres de et d’inverses (formels) de lettres de . Dans cet exposé, on montre comment étudier par des méthodes combinatoires et probabilistes certaines propriétés algébriques d’un sous-groupe aléatoire finiment engendrés de . On comparera différentes distributions de probabilités assez naturelles sur ces sous-groupes.
• Philippe Biane Le déterminant de la double énumération des ASM
  Résumé

  On considère la double énumération des matrices à signes alternants suivant les positions du 1 sur la première et la dernière ligne. Le déterminant de la matrice ainsi obtenue prend les valeurs successives, lorsque la taille de la matrice croît. On obtient la formule générale comme corollaire d’un résultat sur les déterminants de certaines fonctions de Schur.

  Travail en commun avec L. Cantini et A. Sportiello.

• Yao-ban Chan Series expansions via the corner transfer matrix renormalization group method
  Résumé

  The corner transfer matrix renormalization group method is a powerful algorithm for evaluating physical quantities in statistical mechanical models. It was developed by Nishino and Okunishi in 1996, and originates from Baxter’s corner transfer matrix equations and method, which were developed in 1978. The method has been applied to numerous models since its development to great success, but as far as we know has not been used to calculate series expansions (which Baxter did with his original method). In this talk, we discuss the CTM equations and method, the CTMRG method, and our work on this method which has enabled us to calculate series expansions from it.
• Bruno Courcelle The expression in monadic second-order logic of some graph polynomials.
  Résumé

  Logical definition of graph polynomials and algorithmic applications. Bijective proof of the equivalence of 2 definitions of the Tutte polynomial. Remarks on recursive definitions by elimination of edges or vertices.
• Philippe Di Francesco Preuve de la conjecture ASM-DPP
  Résumé

  Nous prouvons la conjecture de Mills-Robbins-Rumsey (1983) reliant l’énumeration raffinée des partitions planes descendantes (DPP) et des matrices à signe alternant (ASM).
• Gérard H. E. Duchamp Algebras of diagrams and functions coming from physics
  Résumé

  Nous considérons deux aspects de la formule du produit de Bender, Brody et Meister [1] appliquée aux séries formelles de la théorie combinatoire des champs. Premièrement, on remarque que le cas où les fonctions ont un terme constant est d’un intérêt spécial parce qu’elle donnent lieu à des groupes de substitution. Les groupes issus du problème de l’ordre normal sont naturellement associés à des champs de vecteurs [2] ou à des conjugués de champs de vecteurs dans le cas où il n’y a qu’une seule annihilation. Deuxièmement, nous discutons la représentation avec des graphes de type Feynman de cette formule du produit. Nous montrons qu’il y a une bijection entre cette structure de données (quand elle est étiquetée). Nous montrons que pour une valeur précise du jeu de paramètres, on retrouve l’algèbre de Hopf des Fonctions Quasi-Symétriques Non Commutatives Matricielles. En chemin, cette déformation donne, pour certeines valeurs des paramètres, l’algèbre des polylogarithmes ouvrant la voie vers la théorie des nombres [3].

  References: [1] C. M. Bender, D. C. Brody, and B. K. Meister, Quantum field theory of partitions, J. Math. Phys. Vol 40 (1999). [2] G. Duchamp, K.A. Penson, A.I. Solomon, A. Horzela, P. Blasiak, One-parameter groups and combinatorial physics, arXiv:quant-ph/0401126v1. [3] G.H.E. Duchamp (LIPN), V.H.N. Minh (LIPN), A.I. Solomon (LPTMC), S. Goodenough (LIPN), An interface between physics and number theory, arXiv:1011.0523v2.

• Éric Fusy Formule exacte pour les cartes biparties simples
  Résumé

  La formule des slicings de Tutte, retrouvée bijectivement par Gilles Schaeffer, donne une expression exacte pour le nombre de cartes biparties enracinées, avec nombre fixé de faces de chaque degré. Nous montrons bijectivement qu’une formule exacte très similaire existe pour compter les cartes biparties enracinées sans arêtes multiples, avec nombre fixé de faces de chaque degré. L’expression en terme de séries génératrices se généralise aux cartes biparties de maille plus grande.

  Travail en commun avec Olivier Bernardi.

• Adriano Garsia Les Matrices de Tesler et la combinatoire des fonctions Harmoniques Diagonales
  Résumé

  Une matrice triangulaire à éléments entiers positifs ou nuls est dite de “Tesler de forme ” si pour tout élément diagonal la somme des éléments dans sa ligne ( inclus) moins la somme des éléments dans sa colonne ( exclu) est égale à . Dans un travail récent J. Haglund a démontré qu’une somme pondérée de matrices de Tesler de forme de taille donne la série de Hilbert bigraduée de l’espace des harmoniques diagonales. Dans cet exposé on donne une nouvelle démonstration de ce résultat, et on montre le lien avec la combinatoire des fonctions de parking.
• Florent Le Gac Énumération de matrices à signe alternant avec un nombre fixé d’entrées négatives
  Résumé

  Les matrices à signes alternants sont des objets largement étudiés en physique statistique. Elles sont en bijection avec les configurations de boucles compactes, objets sur lesquels portait l’ex-conjecture de Razumov-Stroganov. Leur étude du point de vue de leur nombre d’entrées négatives, lorsque ce nombre est petit comparé à la taille des matrices n’est pas l’objet de nombreux résultats et nous présenterons une étude des matrices à signes alternants dans ce cadre là.
• Jean-Gabriel Luque Une généralisation des polynômes de Jack. Calculs et propriétés liés au graphe de Yang-Baxter
  Résumé

  Nous étudions une généralisation des polynômes de Jack (définis comme fonctions propres simultanés des opérateurs de Cherednik Dunkl avec certaines propriétés de dominance) dont les multiplicités sont prises dans un module irréductible de . Ces polynômes ont été définis dans le cadre général des groupes de réflexions complexes par Griffeth et étudié par Dunkl dans le cas du groupe symétrique (). Nous utilisons le graphe de Yang-Baxter afin d’écrire un algorithme permettant de calculer ces polynômes et nous explicitons certaines propriétés des polynômes de Jack en termes de graphes (norme, opérations de symétrisation/antisymétrisation, restriction etc…)
• Régine Marchand Croissance d’une population de bactéries en milieu hostile
  Résumé

  Il s’agit d’un travail commun avec Olivier Garet.

  Une bactérie très fertile essaie de se reproduire au milieu de cellules de type immunitaire qui gênent son développement. Les cellules de type immunitaires évoluent (sur ) au cours du temps () comme des amas de percolation orientée sous-critique sur , et bénéficient d’une immigration constante. La bactérie tente alors de se développer dans l’espace resté vacant comme un amas percolation orientée surcritique. Pourra-t-elle survivre ?

• Hoang Ngoc Minh Polyzêtas
  Résumé

  Euler a été le premier à utiliser sa formule sommatoire (également découverte par la suite, et de manière indépendante, par Mac-Laurin) pour obtenir le développement asymptotique des sommes harmoniques classiques et il a fait apparaître des constantes, comme la constante gamma et la valeur en les entiers positifs de la fonction zêta de Riemman dont la nature arithmétique reste encore à élucider. Ces sommes ont été généralisées récemment en les sommes multiples emboîtées dont la structure algébrique, déduite de celle des polylogarithmes, donnent des algorithmes efficaces pour déterminer leur comportement asymptotique dans diverses échelles de comparaison et d’en extraire la partie constante. Les coefficients de ces développements appartiennent à une algèbre de nombres spéciaux engendrée par la constante gamma et par la valeur en les multi-indices entiers positifs de la fonction polyzêta de Riemman dont les non relations entre elles méritent des attentions particulières pour leur natures combinatoire, algorithmique et arithmétique.
• Cyril Nicaud Analyse en moyenne d’algorithmes en théorie des langages
  Résumé

  Je montrerai sur deux exemples, l’algorithme de Glushkov et l’algorithme de Moore, le genre de résultats que l’on peut obtenir quand on essaye d’analyser la complexité en moyenne d’algorithmes qui manipulent des objets issus de la théorie des langages. Ce sera l’occasion de montrer quelques techniques de combinatoire analytique et de discuter des choix de distributions.
• Dominique Poulalhon Comment minimiser une tresse ?
  Résumé

  Le groupe des tresses à brins est décrit de façon standard comme le groupe engendré par éléments satisfaisant les relations suivantes: pour tous et , si , alors , et sinon . La notion de longueur d’une tresse induite par cette présentation est la plus intuitive, puisqu’elle coïncide avec le nombre minimal de croisements de brins des isotopes de la tresse considérée. Mais alors que pour d’autres présentations de , la longueur et les géodésiques sont assez bien comprises, aucun résultat n’est connu pour la présentation standard dès que . Nous présenterons de nouveaux résultats concernant , et proposerons un algorithme polynomial pour le calcul d’un représentant géodésique (dont la correction n’est que partiellement prouvée). Travail en cours avec Jean Mairesse et Anne Micheli.
• Édouard Maurel-Ségala Limite d’échelle de matrices aléatoires et énumérations de cartes
  Résumé

  Le but de cet exposé est de prolonger le parallèle entre matrices hermitiennes et énumérations de cartes au cas de matrices unitaires. Nous verrons en particulier comment la dynamique du mouvement brownien unitaire est relié à la construction de cartes.
• Jiang Zeng Symétrie et unimodalité de polynômes de descente via combinatoire de fractions continues
  Résumé

  Il est bien connu que les coefficients de polynômes de descente de permutations forment une suite symétrique et unimodale. Dans cet exposé on propose une nouvelle preuve de cette propriété en utilisant des combinatoires de fractions continues. Cette approche permet en particulier de démontrer une conjecture de Brändén sur la divisibilité de coefficients dans une formule de polynômes Eulériens généralisés. On discute ensuite des formules analogues pour les dérangements avec l’interprétation de coefficients et les (p, q)-analogues des identités reliant des polynômes de descente et les nombres d’Euler. Enfin, on mentionnera quelques problèmes ouverts.

Emploi du temps

Mercredi 26 janvier

Jeudi 27 janvier

Vendredi 28 janvier

Participants

• Marie Albenque (LIX, CNRS, Ecole Polytechnique)
• Jean-Christophe Aval (LaBRI, Bordeaux)
• Axel Bacher (LaBRI, Bordeaux 1)
• Frédérique Bassino (LIPN, Paris XIII)
• Jean Bétréma (LaBRI, Bordeaux)
• Philippe Biane (ICM, Marne la Vallée)
• Nicolas Bonichon (LaBRI, Bordeaux)
• Mireille Bousquet-Mélou (LaBRI, Bordeaux)
• Adrien Boussicault (LaBRI, Bordeaux)
• Mathilde Bouvel (LaBRI, Bordeaux)
• Yao-ban Chan (LaBRI, Bordeaux)
• Guillaume Chapuy (LIAFA, Paris 7)
• Philippe Chassaing (IECN, Nancy)
• Brigitte Chauvin (LMV, Versailles Saint-Quentin)
• Hayat Cheballah (LIPN, Paris 13)
• Gwendal Collet (LIX, Paris Sud)
• Robert Cori (LaBRI, Bordeaux)
• Sylvie Corteel (LRI, Orsay)
• Julien Courtiel (MPRI)
• Bruno Courcelle (IUF, LaBRI, Bordeaux)
• Michele D’Adderio (Max-Planck-Institut für Mathematik Bonn)
• Sandrine Dasse-Hartaut (LIAFA, Paris 7)
• Matthieu Deneufchâtel (LIPN, Paris 13)
• Philippe Di Francesco (CEA Saclay)
• Paul Dorbec (LaBRI, Bordeaux)
• Gérard H. E. Duchamp (IG, Paris-Nord)
• Philippe Duchon (LaBRI, Bordeaux)
• Valentin Feray (LaBRI, Bordeaux)
• Éric Fusy (LIX, Palaiseau)
• Adriano Garsia (San Diego)
• Samuele Giraudo (Institut Gaspard Monge, Paris- Est Marne la Vallée)
• Olivier Guibert (LaBRI, Bordeaux)
• Alice Jacquot (LIP6, Paris)
• Matthieu Josuat-Vergès (LRI, Orsay)
• Robin Langer (LIAFA, Paris 7)
• Florent Le Gac (LaBRI, Bordeaux)
• Jean-Gabriel Luque (IGM, Marne-la-Vallée)
• Jean Mairesse (CNRS, Univ. Paris 7)
• Régine Marchand (IECN, Nancy)
• Jean-François Marckert (LaBRI, Bordeaux)
• Édouard Maurel-Ségala (Orsay)
• Rémi Maurice (Institut Gaspard Monge, Paris- Est Marne la Vallée)
• Anne Micheli (LIAFA, Univ. Paris 7)
• Philippe Nadeau (Faculty of Mathematics of the University of Vienna)
• Hoang Ngoc Minh (LIPN, Paris 13)
• Cyril Nicaud (Institut Gaspard Monge, Paris- Est Marne la Vallée)
• Jean-Christophe Novelli (Institut Gaspard Monge, Paris- Est Marne la Vallée)
• Jean Guy Penaud (LaBRI, Bordeaux 1)
• Adeline Pierrot (LIAFA, Paris 7)
• Dominique Poulalhon (LIX, Palaiseau)
• Nicolas Pouyanne (LMV, Versailles Saint-Quentin en Yvelines)
• Louis-Francois Preville-Ratelle (UQAM)
• Mike Robson (LaBRI, Bordeaux 1)
• Thomas Selig (LaBRI, Bordeaux)
• Andrea Sportiello (LIPN, Paris 13)
• Ekaterina Vassilieva (LIX, Ecole Polytechnique)
• Jiang Zeng (ICJ, Lyon 1)
• Alexandre Zvonkin (LaBRI, Bordeaux)

Organisateurs

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

Soutien financier

• Projet ANR A3
• LaBRI
• Université Bordeaux 1