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

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

• Jean-Christophe Aval Fonctions de parking rectangulaires
  Résumé

  Les chemins de Dyck sont des objets classiques en combinatoire. On les représente usuellement par des chemins à pas Nord et Est traversant diagonalement un carré et restant au-dessus de la diagonale (leur taille correspond au côté du carré). Ils sont énumérés par les nombre de Catalan . Cette notion se généralise naturellement en considérant les chemins traversant un rectangle de dimensions (et restant encore au-dessus de la diagonale). Dans le cas où et sont premiers entre eux, la formule d’énumération est elle aussi “classique” : . Dans le cas général, la formule est moins connue, mais elle a été obtenue dès 1958 (par Bizley).

  Les fonctions de parking peuvent être définies comme des chemins de Dyck (carrés dans le cas classique, rectangulaires dans le cas général) dont les n pas Nord sont étiquetés par les entiers de 1 à n (avec une condition de croissance sur des pas Nord consécutifs). Je présenterai dans cet exposé une étude de ces objets : je reviendrai sur leur énumération et j’étudierai l’action du groupe symétrique .

  Travail en collaboration avec F. Bergeron (Montréal).

• Charles Bordenave Dénombrement asymptotique des graphes avec une suite de voisinages acycliques donnés
  Résumé

  Pour un graphe fini et un entier h donnés, la suite des h-voisinages est la suite des sous-graphes enracinés de rayon h enracinés sur les sommets du graphe. On peut calculer le nombre asymptotique de graphes avec n sommets et une suite de h-voisinages acycliques donnés. On peut s’en servir pour définir une entropie associée à la convergence faible locale de Benjamini et Schramm et en déduire des principes de grandes déviations.

  Travail en collaboration avec Pietro Caputo.

• Alin Bostan Efficient Experimental Mathematics for Lattice Path Combinatorics
  Résumé

  Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, experimental mathematics has been used to explore and solve a number of difficult questions related to lattice walks. In this talk, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.
• Jérôme Casse Automates cellulaires probabilistes à loi invariante markovienne
  Résumé

  Un automate cellulaire probabiliste (ACP) à 2 voisins sur la ligne est un algorithme probabiliste qui transforme un mot bi-infini sur un alphabet au temps en un autre mot bi-infini au temps de telle sorte que la loi de la lettre ne dépend que des lettres et (pas de ). De plus, les transformations sont indépendantes. Ainsi, lorsque l’on part d’une configuration aléatoire (ou non) , en itérant notre PCA, nous construisons successivement des mots . Une question est alors de savoir s’il existe ou non une loi invariante…

  Dans cet exposé, nous verrons les conditions nécessaires et suffisantes pour qu’un ACP admette une ou plusieurs lois invariantes markoviennes en espace dans le cas où est fini et, plus généralement, où est un espace polonais (fini ou infini, discret ou continu). Dans le cas où , on retrouve le résultat classique de Belyaev & al.

• Brigitte Chauvin B-urnes
  Résumé

  Les arbres-B sont des arbres de recherche dans lesquels toutes les feuilles sont au même niveau. Dans un arbre-B de paramètre , les nœuds de l’arbre contiennent entre et clés. Nous décrivons un algorithme de croissance de tels arbres, dans lequel il apparaît que la structure des nœuds terminaux est celle d’une urne de Pólya. La transition de phase habituelle dans les urnes de Pólya, entre un comportement asymptotique gaussien ou non gaussien, se produit pour . Comme les valeurs de courantes en pratique sont de plusieurs centaines, les arbres-B constituent un exemple concret de grande urne de Pólya. Pour , nous étudions le vecteur composition des nœuds terminaux de l’arbre. Après renormalisation, les fluctuations convergent fortement vers une variable aléatoire , dont nous obtenons quelques propriétés, bien que sa loi ne semble pas classique : elle est à valeurs dans C, elle possède des moments exponentiels, une densité par rapport à la mesure de Lebesgue sur C, son support est C tout entier, elle est solution d’une équation en loi de type “smoothing equation”.
• Gwendal Collet Cartes simples : distances et convergence
  Résumé

  Nous démontrons la convergence du profil des distances dans les cartes simples (sans boucles ni arêtes multiples), en exploitant une bijection entre une sous-famille des cartes simples et celle des triangulations eulériennes. Cette bijection permet de garder la trace de nombreuses paramètres de la carte (distances, nombre de sommets, de faces), utiles pour l’énumération, la génération aléatoire, mais aussi — combinée avec une bijection vers des arbres étiquetés — pour esquisser la démonstration de la convergence des cartes simples vers la carte brownienne.
• Bérénice Delcroix-Oger Posets de partitions semi-pointées
  Résumé

  Nous introduisons une généralisation des posets de partitions d’ensemble et de partitions pointées, appelées partitions semi-pointées. Une partitions semi-pointée est une partition d’ensemble munie, pour chacune de ses parts, d’un élément distingué ou non. Après avoir introduit ces posets, nous présentons l’étude de leurs nombres de Moebius en nous appuyant sur la théorie des espèces.
• Romaric Duvignau Arbre de génération pour les permutations et simulation en aveugle
  Résumé

  Nous décrivons un nouvel arbre de génération uniforme pour les permutations, ayant la propriété que, pour la majorité des permutations, tous leurs descendants ont le même nombre de points fixes ; notre arbre est optimal en ce sens. Grâce à cet arbre, nous obtenons un nouvel algorithme de génération aléatoire uniforme de dérangements, algorithme qui nécessite, en moyenne, n + o(n) appels à un générateur de nombres aléatoires ; ainsi qu’une méthode combinatoire de simulation exacte de la loi de Poisson de paramètre 1.

  Notre arbre de génération permet en outre de simuler efficacement en aveugle la distribution Binomiale(n, 1/n). Nous appelons simulation en aveugle le fait de devoir simuler une distribution qui dépend d’un paramètre inconnu n à l’aide uniquement d’un générateur de n-uniformes. Ce problème se retrouve notamment lors de la maintenance de réseaux logiques.

• Wenjie Fang Constellations : mise en équation, résolution, rationalité
  Résumé

  Dans l’étude des cartes combinatoires, les constellations possèdent une position particulière. Elles sont à la fois un modèle spécial et une généralisation des cartes biparties, et elles sont aussi reliées aux problèmes de factorisation dans le groupe symétrique. Même si les constellations sont bien comprises combinatoirement grâce aux bijections, leur équation fonctionnelle a résisté jusqu’il y a peu. En genre supérieur, elles sont beaucoup moins bien comprises. Dans cet exposé, nous verrons la mise en équation des constellations dans le cas planaire et en genre supérieur, la résolution dans le cas planaire, et la rationalité en genre supérieur pour le cas biparti.
• Lucas Gerin Processus d’Hammersley discrets et pseudo-sous-suites croissantes
  Résumé

  A la fin des années 60, Hammersley a introduit un processus à temps et espace continus pour étudier le comportement de la plus longue sous-suite croissante d’une permutation aléatoire. Plus récemment, deux variantes discrètes de ce processus ont été introduites, ces variantes comptent des objets semblables à des sous-suites croissantes. En étudiant les mesures stationnaires de ces processus nous revisitons et unifions ces résultats avec un point de vue plus probabiliste.

  (Travail en commun avec A.-L. Basdevant, N. Enriquez, J.-B. Gouéré)

• Florent Hivert Le monoïde semi-plaxique
  Résumé

  On s’intéresse à la classe des monoïdes dits de type plaxique qui possèdent les propriétés de compatibilité avec la standardisation et avec la restriction aux intervalles. En effet, par passage au quotient dans l’algèbre des fonctions quasi symétriques libres (algèbre de Hopf des permutations de Malvenuto Reutenauer), ils donnent naissance à des algèbres de Hopf intéressantes. Cette situation possède plusieurs exemples importants :

  • le monoïde plaxique lui-même qui fabrique l’algèbre des tableaux dont l’image commutative est l’algèbre des fonctions symétriques, ce qui permet de prouver la règle de Littlewood-Richardson ;
  • le monoïde sylvestre qui construit l’algèbre des arbres binaires de Loday-Ronco ;
  • le monoïde hypoplaxique qui construit les fonctions quasi symétriques et symétriques non commutatives.

  D’autre part, Priez a montré que l’intersection de deux monoïdes de type plaxique est encore de type plaxique.

  Dans cet exposé, je présenterai un travail en cours sur l’intersection des monoïdes plaxique et sylvestre. Le résultat principal est le suivant : pour toute classe de permutations, il existe un ordre partiel dont la classe est exactement l’ensemble des extensions linéaires. Ces ordres sont des objets intermédiaires entre les tableaux et les arbres binaires de recherche ; ils sont construits grâce à un algorithme d’insertion. La preuve de ce résultat se fait en étudiant un système de réécriture non pas sur les mots, mais sur les ordres partiels eux-mêmes.

• Pierre Lairez Sommes binomiales multiples et diagonales de fractions rationnelles
  Résumé

  (Travail commun avec Alin Bostan et Bruno Salvy) Nous définissons précisément une classe de suites, les sommes binomiales, close pour de nombreuses opérations (somme, produit, sommation indéfinie, etc) et contenant les coefficients binomiaux. On y trouve toutes les sommes binomiales, y compris les sommes multiples, au sens usuel du terme, comme [formules non retranscrites, voir le PDF original].

  Notre premier résultat montre que les sommes binomiales sont exactement les coefficients des diagonales de fractions rationnelles, donnant ainsi une caractérisation intrinsèque des sommes binomiales. Notre second résultat est un algorithme pour décider de l’égalité dans la classe des sommes binomiales. On peut donc prouver de manière entièrement automatique, et relativement rapide, des identités comme [formule non retranscrite, voir le PDF original].

  De nombreux outils existent déjà pour traiter ce genre de sommes, et même des sommes bien plus générales que les sommes binomiales, mais une intervention humaine est souvent nécessaire pour conclure les preuves. Ce que nous apportons est un test d’égalité automatique de bout en bout sur la classe précisément délimitée des sommes binomiales.

  Dans les deux cas, le principe est d’éviter la représentation des sommes binomiales par des systèmes d’équations récurrentes pour lui préférer la représentation des séries génératrices des sommes binomiales par des intégrales multiples de fractions rationnelles. L’idée n’est pas neuve, elle a notamment été exploitée en profondeur par Egorychev [Ego84] mais nous la systématisons et l’automatisons. Par exemple, nous calculons automatiquement que [formule non retranscrite, voir le PDF original], pour un certain domaine d’intégration . En plus des preuves d’identités, ce type de représentation intégrale permet de calculer des récurrences satisfaites par les sommes binomiales.

• Henri Mühle Poset-Topological Aspects of Noncrossing Partition Lattices
  Résumé

  This talk addresses some poset-topological aspects of the noncrossing partition lattices associated with well-generated complex reflection groups. In particular, we will review more or less recent results on the lexicographic shellability of these lattices. An important concept is that of a compatible reflection order. Such orders are crucial in the proofs of the lattice property and the lexicographic shellability of the noncrossing partition lattices. Subsequently we will discuss the connection between the lexicographic shellability and the transitivity of the Hurwitz action on reduced decompositions of a Coxeter element.
• Tridib Sadhu Pattern formation in growing sandpile
  Résumé

  It is a common observation that as a baby animal grows, different parts of the body grow, to the first approximation, at the same rate. This property is called proportionate growth. How this is achieved is an interesting problem in Biology, and is not well understood. I will discuss a simple toy model where this feature comes out quite naturally from local rules without fine tuning any parameter. In the model, one starts with a simple periodic background on a lattice, and adds particles at one site. There is a relaxation rule that distributes particles to neighboring sites if there are too many particles at any site. Depending on the initial state, and the choice of the rules one gets different beautiful but intricate patterns. An example is shown in the figure. The patterns produced are composed of large distinguishable structures with sharp boundaries, all of which grow at the same rate, keeping their overall shapes unchanged. I will indicate how, in some special cases, the limiting pattern can be characterized exactly in terms of discrete holomorphic functions. I will also present an interesting connection to Apollonian circle packing problem.
• Adrian Tanasa Polynôme de Tutte de graphes (et matroïdes) - liens avec la théorie quantique des champs
  Résumé

  In the first part of the talk I will introduce the Tutte polynomial of graphs and explicitly show its relation with polynomials appearing in the so-called parametric representation of integrands canonically associated to graphs in quantum field theory. In the second part of the talk I will show a new proof of the celebrated property of universality of the Tutte polynomial of graphs (or matroids), proof which does not require the usual edge induction arguments. Finally, I will present how this proof generalizes for the universality property of the Bollobás-Riordan polynomial of ribbon graphs (or embedded graphs).

Emploi du temps

Mercredi 4 février

Jeudi 5 février

Vendredi 6 février

Participants

• Jean-Christophe Aval (LaBRI, Université de Bordeaux)
• Cyril Banderier (LIPN, CNRS)
• Frédérique Bassino (LIPN)
• Jean Bétréma (LaBRI)
• Nicolas Bonichon (LaBRI)
• Valentin Bonzom (LIPN)
• Charles Bordenave (Institut de mathématiques, Toulouse)
• Alin Bostan (INRIA, Saclay)
• Mireille Bousquet-Mélou (CNRS, LaBRI)
• Astrid Casadei (LaBRI)
• Jérôme Casse (LaBRI, Université de Bordeaux)
• Zakaria Chemli (LIGM)
• Gwendal Collet (Institut für Diskrete Mathematik)
• Vincent Delecroix (LaBRI)
• Clément Dervieux (LIAFA)
• Paul Dorbec (LaBRI, Univ. Bordeaux)
• Romaric Duvignau (LaBRI, Université de Bordeaux)
• Lucas Gerin (École Polytechnique)
• Yvan Le Borgne (LaBRI, Université de Bordeaux)
• Bérénice Delcroix-Oger (Institut Camille Jordan)
• Adrian Tanasa (LIPN, Paris XIII)
• Brigitte Chauvin (LVM, Université de Versailles St Quentin en Yvelines)
• Van Chiên (BUI, LIPN)
• Henri Derycke (Labri/ENS Lyon)
• Louis Dumont (Inria)
• Wenjie Fang (LIAFA, Université Paris Diderot)
• Joël Gay (LIX)
• Samuele Giraudo (LIGM, Université Paris-Est Marne-la-Vallée)
• Olivier Guibert (LaBRI)
• Quoc Hoan (NGO, LIPN)
• Florent Hivert (LRI, Orsay)
• Matthieu Josuat-Vergès (Laboratoire d’Informatique Gaspard Monge, CNRS)
• Vincent Jugé (LIAFA(Paris 7) et École des Mines de Paris)
• Sébastien Labbé (Université de Liège)
• Pierre Lairez (TU Berlin)
• Patxi Laborde Zubieta (LaBRI)
• Thibault Manneville (LIX (Polytechnique))
• Philippe Marchal (CNRS et Université Paris 13)
• Jean-François Marckert (LaBRI, Université de Bordeaux)
• Thierry Monteil (LIPN, CNRS)
• Philippe Nadeau (CNRS & ICJ, Univ. Lyon 1)
• Nicolas Pouyanne (Labo math Versailles)
• Henri Mühle (LIAFA, Université Paris Diderot)
• Pierre Nicodeme (LIPN)
• Jean-Guy Penaud (Labri)
• Claire PENNARUN (LaBRI)
• Mathias Pétréolle (Institut Camille Jordan)
• Carine Pivoteau (LIPN)
• Tridib Sadhu (IPhT, Saclay)
• Andrea Sportiello (LIPN)
• Christophe Tollu (LIPN, université de Paris 13)
• Omar TOUT (LaBRI)
• Brigitte VALLEE (CNRS, Laboratoire GREYC)
• Vincent Vong (LIGM)
• Pascal Weil (LaBRI)

Organisateurs

• Yvan Le Borgne
• Jean-François Marckert

Soutien financier

• ANR GRAAL
• LaBRI