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

Les JCB 2013 ont eu lieu du mercredi 13 au vendredi 15 février 2013, 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.

• Cyril Banderier Analyse en moyenne de problèmes NP-complets : pourquoi tant d’algorithmes ont une complexité en moyenne du type n^(ln n) ?
  Résumé

  De nombreux problèmes se résolvent par une stratégie divide and conquer, optimisée de plus à chaque étape pour un certain “élagage”. L’archétype de cette stratégie sur un archétype de problème NP-complet est l’algorithme de Tarjan qui exhibe un “MIS” (maximum independent set) d’un graphe.

  Une nouvelle révolutionnaire serait de trouver un algorithme de complexité polynomiale (ne serait-ce même qu’en moyenne), or nous montrerons pourquoi toute optimisation (même avec des élagages plus futés) de cette stratégie aboutit toujours à une complexité en moyenne de type $n^{\log n}$.

  Cela étend des travaux initiaux de Chvátal et Pittel sur le modèle de graphes aléatoires $G(n,p)$.

  Nos preuves reposent sur les outils de la combinatoire analytique, tels que magnifiquement présentés (pub!) dans le petit livre violet de Flajolet & Sedgewick : “Analytic Combinatorics”.

  Il y a de forts liens avec des récurrences apparaissant aussi en théorie des nombres (partitions de Mahler), dans des équations aux q-différences, et dans d’autres analyses d’algorithmes randomisés.

  Cet exposé est notamment basé sur l’article “Analysis of an exhaustive search algorithm in random graphs and the $n^{c\log n}$-asymptotics”, de Cyril Banderier, Hsien-Kuei Hwang, Vlady Ravelomanana et Vytas Zacharovas.

• Jean-Luc Baril Balade de statistiques entre les permutations et les cycles
  Résumé

  Récemment, Sergi Elizalde (2011) a présenté une bijection entre l’ensemble $C_{n+1}$ des cycles de taille $n+1$ et l’ensemble $S_n$ des permutations sur ${1, 2, \ldots, n}$ qui conserve les positions des descentes (sur les $n$ premières positions). Dans cet exposé, nous présentons une bijection entre $C_{n+1}$ et $S_n$ qui conserve les positions des excédences faibles et qui transporte les points quasi-fixes vers les points fixes. Cela induit une bijection de l’ensemble des dérangements de taille $n$ vers l’ensemble des cycles de taille $n+1$ sans point quasi-fixe qui conserve les positions des excédences faibles. De plus, on construit une sorte de continuité discrète entre $C_{n+1}$ et $S_n$ qui conserve à chaque étape les positions des excédences faibles. Un résultat similaire pour les descentes est présenté en problème ouvert.
• François Bergeron Encore des surprises concernant les fonctions de stationnement
  Résumé

  L’étude des fonctions de stationnement foisonne en belles identités, et liens avec des sujets variés. Nous allons ajouter à ce répertoire, en mettant en évidence de nouvelles interactions entre fonctions de stationnement, polyominos parallélogrammes, représentations de $SL_2$, combinatoire des nombres de Catalan généralisés, et identités entre fonctions symétriques.
• Jérémie Bettinelli Croissance de cartes planaires par une approche bijective
  Résumé

  Au cours de cet exposé, je présenterai des bijections sur les cartes planaires permettant de faire varier certains paramètres. En particulier, cela permet de rajouter une face à une quadrangulation uniforme ou d’augmenter la taille du bord d’une quadrangulation à bord. On peut également retrouver directement la formule des slicings de Tutte comptant les cartes planaires dont les faces ont des degrés prescrits, deux au plus de ces degrés étant impair. La stratégie générale de ces bijections consiste à définir convenablement un chemin dans la carte initiale, à couper le long de ce chemin, puis à recoller avec un léger décalage, ce qui modifie légèrement la structure de la carte.
• Paul Dorbec Un survol de la domination de puissance dans les graphes
  Résumé

  La domination de puissance est un problème de graphes issu d’une question de maintenance de réseaux électriques. Il s’agit de placer des appareils de mesure sur certains sommets afin de surveiller tout le graphe. Au départ, sont surveillés tous les sommets voisins des appareils de mesure ; c’est l’étape de domination. Puis on autorise une propagation : chaque sommet qui est l’unique voisin non surveillé d’un sommet surveillé est à son tour surveillé. Un ensemble de sommets permettant de surveiller tout le graphe de la sorte est appelé dominant de puissance. La question qui nous intéresse est de minimiser la taille d’un tel ensemble.

  La première étape de surveillance correspond au problème classique de la domination, très étudié en théorie des graphes. La possibilité de propagation propre à la deuxième étape altère beaucoup la nature du problème, et des techniques de preuves originales doivent être mises en place pour faire face à ce comportement. Au cours de cet exposé, nous présenterons les principaux résultats connus sur le sujet ainsi que certains aspects originaux des techniques de preuves utilisées.

• Olivier Guibert Quelques cas d’énumération de permutations triées par pile et en combinant des symétries
  Résumé

  D. Knuth a introduit en 1973 les permutations à motifs exclus pour le problème du tri d’une permutation par passage par une pile, celle-ci vérifiant la condition dite tour de Hanoï (c.-à-d. dont les éléments décroissent de la base vers le sommet de la pile). Ainsi, il a montré que les permutations évitant le motif 2-3-1 (c.-à-d. celles dont aucune sous-suite $yzx$ ne vérifie $x < y < z$) sont exactement ces permutations 1-triables, comptées par les nombres de Catalan. Les permutations 2-triables (qui sont donc triées après deux passages successifs par la pile) ont également été caractérisées par des motifs exclus par J. West et on doit à D. Zeilberger en 1992 la première preuve de la formule d’énumération suivie en 1996 par deux preuves bijectives (de I. Goulden et J. West et de S. Dulucq, S. Gire, O. Guibert et J. West).

  Quatre décennies plus tard, le problème est toujours d’actualité, notamment car M. Albert, M. Atkinson, M. Bouvel, A. Claesson et M. Dukes en 2010 se sont intéressés au cas où, entre deux tris, la permutation intermédiaire subit une éventuelle transformation combinant les symétries miroir, complément et inverse. Nous étudierons en particulier, bijectivement, un cas faisant intervenir trois passages successifs par la pile et combinant des symétries, en connexion avec certains chemins de Motzkin… et d’autres permutations triables par deux passages successifs par la pile et combinant elles aussi des symétries.

• Christian Krattenthaler Une équation différentielle de Riccati et des nombres de sous-groupes libres pour PSL2(Z) modulo des puissances de premiers
  Résumé

  Dans la théorie de croissance des sous-groupes, des propriétés des nombres de sous-groupes dans un groupe (infini) donné d’un indice donné ont été étudié. Dans cet exposé, nous sommes intéressés au nombre de sous-groupes libres dans $PSL_2(\mathbb{Z})$ d’un indice donné, et nous étudions le comportement de ces nombres modulo des puissances de premiers. Comme les séries génératrices de ces nombres satisfont à une équation différentielle de Riccati, cela revient à une étude des solutions sous forme des séries formelles de cette équation différentielle modulo des puissances de premiers. À la fin, nous allons voir que ces nombres sont toujours périodiques modulo des puissances $p^{\alpha}$, pour des premiers $p$ supérieurs à 5. Je vais décrire l’approche vers ce résultat, qui est - à mon avis - assez intéressante.

  Il s’agit d’un travail fait en commun avec Thomas W. Müller.

• Marc Van Leeuwen Une bijection qui prouve le théorème du diamant aztèque en peignant des chemins
  Résumé

  Le diamant aztèque d’ordre $n$ est une configuration de $4\binom{n+1}{2}$ carrés arrangé en losange, et le théorème de ce nom (Elkies, Kuperberg, Larsen, Propp, 1992) affirme que le nombre de ses pavages par des dominos est $2^{\binom{n+1}{2}}$. Ces pavages correspondent par une bijection simple aux familles formées de $n+1$ chemins disjoints reliant les points sur un côté d’un carré de $n \times n$ cases aux points d’un côté adjacent, avec de pas horizontaux, diagonaux ou verticaux. Le nombre de telles familles s’exprime (via la méthode de Lindström-Gessel-Viennot) par un déterminant de nombres de Delannoy, quel déterminant s’évalue facilement, donnant une preuve du théorème du diamant aztèque. (Un grand nombre d’autres preuves sont connues, dont les 4 dans la publication originale reposent toutes sur une autre bijection, celle de pavages avec certaines paires de matrices à signes alternants.)

  On présentera une preuve directe (sans déterminant) et bijective de cette énumération de familles de chemins ; c’est à notre connaissance la première preuve bijective du théorème du diamant aztèque. Elle passe par des familles de chemins plus restreints (les pas verticaux ne sont admis que vers la fin d’un chemin) mais sans condition d’être disjoints, et qui sont faciles à énumérer. La bijection est établie par un algorithme inversible qui “peigne” une telle famille, supprimant tous les points d’intersection entre ses chemins, et donnant au final une famille disjointe du type cherché. Cet algorithme permet aussi d’engendrer de façon efficace des pavages aléatoires du diamant aztèque, par une méthode assez différente de la méthode du “domino shuffling” utilisée précédemment, et d’illustrer ainsi le phénomène du “cercle arctique”.

  Il s’agit d’un travail commun avec Frédéric Bosio (Poitiers), qui a proposé la bijection mentionnée.

• Nicolas Pouyanne Méthodes d’analyse des urnes de Pólya
• Kirone Mallick Fluctuations macroscopiques et combinatoire
  Résumé

  Le processus d’exclusion asymétrique (ASEP) est un modèle de particules en interaction de cœur dur qui évoluent selon une dynamique stochastique sur un réseau unidimensionnel. Ce modèle, très étudié en physique statistique hors d’équilibre, peut être résolu par des techniques inspirées de la théorie des systèmes intégrables. Nous expliquerons comment l’Ansatz de Bethe permet de déterminer analytiquement les propriétés spectrales d’ASEP et de calculer les grandes déviations du courant. Nous discuterons également de généralisations de ce modèle faisant apparaître des représentations d’algèbres quadratiques.
• Irène Marcovici Automates cellulaires probabilistes et champs aléatoires avec directions iid
  Résumé

  Considérons le modèle le plus simple d’automates cellulaires probabilistes (ACP) de dimension 1. Les cellules sont indexées par les entiers relatifs, l’alphabet est ${0,1}$, et toutes les cellules évoluent de manière synchrone. Le nouveau contenu d’une cellule est choisi aléatoirement, indépendamment des autres, selon une distribution dépendant seulement du contenu de la cellule et de sa voisine de droite. On connaît des conditions nécessaires et suffisantes portant sur les quatre paramètres d’un tel ACP pour qu’il ait la mesure produit de Bernoulli comme mesure invariante. Nous étudions les propriétés du champ aléatoire formé par le diagramme espace-temps obtenu lorsqu’on itère l’ACP à partir de sa mesure invariante de Bernoulli. Il s’agit d’un champ aléatoire non trivial, présentant de très faibles dépendances et de jolies propriétés combinatoires. En particulier, les lignes horizontales mais aussi les lignes selon les autres directions sont constituées de variables aléatoires i.i.d. Nous étudions l’extension de ces résultats à des mesures invariantes de forme markovienne, ainsi qu’aux ACP ayant des alphabets et des voisinages plus grands.
• Marni Mishna Vers la génération aléatoires de génomes
  Résumé

  Les réarrangements génomiques, qui modifient l’organisation du matériel génétique dans les chromosomes, forment un mécanisme majeur de l’évolution. Une approche maintenant standard pour l’étude de ces réarrangements est basée sur la modélisation de groupes de génomes proches par un ensemble de permutations signées. La structure de données appropriée à l’étude des permutations dans ce contexte est l’arbre des intervalles communs. Nous affinons ces arbres en fonction d’un paramètre, et les sous-familles résultantes se révèlent être de variétés d’arbres simples, qui se prêtent particulièrement bien aux techniques de combinatoire énumérative et de génération aléatoire de Boltzmann. Ce raffinement a également des implications dans l’analyse d’algorithme pour la reconstruction de génomes ancestraux. Enfin, nous comparons les arbres que nous générons avec ceux qui résultent de la comparaison directe d’une sélection de génomes de mammifères.

  Travail en collaboration avec Mathilde Bouvel, Cedric Chauve, Rosemary McCloskey, Cyril Nicaud et Carine Pivoteau.

• Adeline Pierrot Trier des permutations avec des piles en série
  Résumé

  Le tri d’une permutation par une pile a été étudié pour la première fois par Knuth dans les années 60. C’est le problème historique qui a amené à définir la notion de motif dans une permutation et de classe de permutations closes par motifs exclus, domaines de recherche très actifs en combinatoire. Le tri par pile fut ensuite généralisé par Tarjan qui a introduit les réseaux de tri, et de très nombreuses variantes de ce problème ont été étudiées par la suite, par exemple en considérant d’autres types de structures proches de la notion de pile, ou en restreignant les opérations possibles sur les piles.

  Dans cet exposé, on s’intéressera en particulier au problème de savoir décider si une permutation $\sigma$ donnée en entrée est triable par deux piles en série. Dans la littérature existante, ce problème a été conjecturé à la fois comme étant NP-complet ou polynomial. La difficulté du problème réside dans le fait que l’on considère les deux piles en même temps, ce qui laisse une grande latitude de choix d’opérations possibles sur la permutation et donne un algorithme naïf exponentiel, contrairement à d’autres variantes où l’on fait passer une permutation dans deux piles, mais en deux étapes en considérant une seule pile à chaque étape.

  En introduisant la notion de push-tri (tri dans lequel tous les éléments doivent être dans les piles en même temps) et en utilisant une décomposition du diagramme de la permutation, nous résolvons ce problème resté longtemps ouvert en donnant un algorithme en $O(|\sigma|^4)$. Cet algorithme utilise une bijection entre certains bi-coloriages du diagramme d’une permutation et l’ensemble des push-tri de la permutation.

• Vincent Pilaud Le barycentre des associaèdres généralisés
  Résumé

  Les associaèdres généralisés sont des polytopes qui apparaissent naturellement dans l’étude des algèbres amassées finies. Après une première construction due à F. Chapoton, S. Fomin and A. Zelevinsky, de multiples réalisations de ces polytopes ont été construites par C. Hohlweg, C. Lange et H. Thomas. Ces réalisations sont obtenues en retirant certaines facettes bien choisies d’un permutoèdre généralisé. Plus récemment, nous avons donné une autre interprétation de ces réalisations en utilisant le polytope des briques d’un complexe de sous-mots. Ceci nous a permis de donner une description des coordonnées des sommets de ces réalisations, et d’en déduire que le barycentre de leurs sommets coïncide avec le barycentre du permutoèdre. Dans cet exposé, je présenterai les grandes lignes de ces résultats ainsi que de nombreux exemples, en prenant soin d’éviter les détails techniques. Travail en commun avec Christian Stump (Universität Hannover).

  Prépublications http://arxiv.org/abs/1111.3349 et http://arxiv.org/abs/1210.3314.

• Matteo Silimbani Combinatorics of non-ambiguous trees
  Résumé

  Au cours de cet exposé, je définirai des nouveaux objets combinatoires, les arbres non-ambigus. Ces objets peuvent être vus comme des arbres dessinés sur une grille sous certaines contraintes et ils sont liés à plusieurs objets combinatoires, comme les polyominos parallélogrammes et les tableaux boisés définis par Aval, Boussicault et Nadeau. Je donnerai un analogue de la formule des équerres pour le comptage des arbres non-ambigus dont l’arbre sous-jacent est fixé. Ensuite, je montrerai que la suite qui énumère les arbres non-ambigus dont l’arbre sous-jacent est complet est liée à la fonction de Bessel d’ordre 0, et ce résultat me permettra de donner une preuve combinatoire d’une identité due à Carlitz. Enfin, j’utiliserai les arbres non-ambigus pour décrire une bijection très naturelle entre polyominos parallélogrammes et arbres binaires.

Emploi du temps

Mercredi 13 février

Jeudi 14 février

Vendredi 15 février

Participants

• Marie Albenque (LIX, CNRS)
• Jean-Christophe Aval (LaBRI, Bordeaux)
• Axel Bacher (LIPN, Paris XIII)
• Cyril Banderier (LIPN, Paris XIII)
• Jean-Luc Baril (LE2I, Université de Bourgogne)
• Frédérique Bassino (LIPN, Paris XIII)
• Nicholas Beaton (LIPN, Paris XIII)
• François Bergeron (UQAM, Montréal)
• Bétréma (LaBRI, Bordeaux)
• Jérémie Bettinelli (IECN, Nancy)
• Nicolas Bonichon (LaBRI, Bordeaux)
• Mireille Bousquet-Mélou (LaBRI, Bordeaux)
• Adrien Boussicault (LaBRI, Bordeaux)
• Mathilde Bouvel (LaBRI, Bordeaux)
• Jean-Paul Bultel (LITIS, Rouen)
• Jérôme Casse (LaBRI, Bordeaux)
• Brigitte Chauvin (LMV, Université Versailles St Quentin)
• Ali Chouria (LITIS, Rouen)
• Gwendal Collet (LIX, École polytechnique)
• Robert Cori (LaBRI, Bordeaux)
• Sylvie Corteel (LIAFA, Paris 7)
• Julien Courtiel (LaBRI, Bordeaux)
• Paul Dorbec (LaBRI, Bordeaux)
• Enrica Duchi (LIAFA, Paris 7)
• Philippe Duchon (LaBRI, Bordeaux)
• Romaric Duvignau (LaBRI, Bordeaux)
• Wenjie Fang (LIAFA, Paris 7)
• Valentin Feray (LaBRI, Bordeaux)
• Thomas Fernique (LIPN, Paris XIII)
• Eric Fusy (LIX, Ecole polytechnique)
• Samuele Giraudo (LIGM, Marne la Vallée)
• Olivier Guibert (LaBRI, Bordeaux)
• Nguyen Hoang-Nghia (LIPN, Paris XIII)
• Samuel Johnson (Department of Mathematics, Simon Fraser University)
• Matthieu Josuat-Vergès (LIGM, Marne la Vallée)
• Frédéric Jouhet (ICJ, Lyon 1)
• Christian Krattenthaler (Fakultat fur Mathematik, Vienne)
• Yvan Le Borgne (LaBRI, Bordeaux)
• Marc van Leeuwen (Mathématiques, Université de Poitiers)
• Jérémie Lumbroso (Laboratoire d’Informatique de Paris 6)
• Cécile Mailler (LMV, Université Versailles St-Quentin)
• Kirone Mallick (CEA, Saclay)
• Jean-François Marckert (LaBRI, Bordeaux)
• Irène Marcovici (LIAFA, Paris 7)
• Rémi Maurice (LIGM, Marne la Vallée)
• Marni Mishna (Department of Mathematics, Simon Fraser University)
• Philippe Nadeau (ICJ, Lyon 1)
• Bérénice Oger (ICJ, Lyon 1)
• Adeline Pierrot (LIAFA, Paris 7)
• Vincent Pilaud (LIX, Palaiseau)
• Dominique Poulalhon (LIX, Palaiseau)
• Nicolas Pouyanne (LMV, Université Versailles St Quentin)
• David Renault (LaBRI, Bordeaux)
• Gabriel Renault (LaBRI, Bordeaux)
• Gilles Schaeffer (LIX, Palaiseau)
• Thomas Selig (LaBRI, Bordeaux)
• Mateo Silimbani (LaBRI, Bordeaux)
• Andrea Sportiello (LIPN, Paris XIII)
• Omar Tout (LaBRI, Bordeaux)
• Ekaterina Vassilieva (LIX, Palaiseau)
• Alexandre Zvonkin (LaBRI, Bordeaux)

Organisateurs

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

Soutien financier

• ANR A3
• ANR PSYCO
• ANR CARTAPLUS
• LaBRI