Résumé: Cet exposé fait suite à l'avant-dernier exposé de l'année dernière, où Lauren Williams nous avait présenté la relation entre l'énumération selon trois paramètres des "permutation tableaux" et la distribution limite du PASEP (Partially Asymmetric Exclusion Process). L'une des questions restant en suspens était de donner une interprétation combinatoire du résultat, sous la forme d'une chaîne de Markov au niveau des tableaux, qui, par la transformation déjà proposée (non injective) des tableaux en configurations du PASEP, se projetterait en ce même PASEP.
C'est exactement la question qu'ont récemment résolue Sylvie Corteel et Lauren Williams, et c'est cette construction que je me propose de présenter.Résumé: Il y a quelques semaines, Wendelin Werner a reçu la médaille Fields pour l'ensemble de ses travaux. Son domaine de recherche se situe à la frontière des probabilités et de la physique statistique.
Une des problématiques concernant plus particulièrement les combinatoristes est la suivante. Il y a dans la nature des tas de marches auto-évitantes dans le plan: on peut penser par exemple, aux marches auto-évitantes de longueur n munies de la loi uniforme, aux marches à boucles effacées, au bord d'un amas de percolation, à l'enveloppe d'une marche aléatoire conditionnée à revenir à son point de départ.
L'étude de tels objets est réputée difficile: ils sont du genre à ne même pas se laisser compter. Eh bien, WW et ses coauteurs Oded Schramm et Gregory F. Lawler ont mis au point une machinerie permettant de montrer qu'asymptotiquement ces objets correctement normalisés convergent en loi vers une courbe limite aléatoire, dont la loi ne dépend du modèle discret qu'à travers un seul paramètre; dans certains cas, la convergence n'est pas montrée, mais la "seule limite possible" est caractérisée. Il s'agit d'une très grande avancée d'un point de vue conceptuel puisque contrairement aux preuves antérieures de convergence de structures combinatoires, la preuve de tels résultats ne repose pas sur la convergence de lois finies-dimensionnelles, mais sur une propriété supposée ou prouvée de la limite: l'invariance conforme.
Résumé: Les ensembles indépendants d'un graphe G=(V,E) sont les sous ensembles de V ne contenant pas de sommets voisins.
Dénombrer les ensembles indépendants d'une grille carrée de côté N est un problème ouvert qui intéresse à la fois les communautés de combinatoristes et de physiciens statisticiens.
Il y a deux ans, trois physiciens ont publié des conjectures assez curieuses portant sur le nombre alterné de ces ensembles indépendants, c'est-à-dire sur la différence entre le nombre de tels ensembles de cardinal pair et impair.
On brodera sur ces conjectures, sur des résultats de même facture obtenus en collaboration avec Svante Linusson et Eran Nevo, et sur quelques questions de "topologie combinatoire": les ensembles indépendants d'un graphe, ordonnés par inclusion, forment un complexe simplicial sur la topologie duquel on peut s'interroger. Nous verrons que pour les grilles carrées que nous considérons, ces complexes ont une topologie très simple: ils sont homotopes à un point, une sphère ou un bouquet de sphères.
Toutes les notions topologiques seront introduites précautionneusement par une oratrice peut experte du sujet.
Résumé: Sur des réseaux réguliers comme le réseau carré, il existe une égalité formelle entre la densité de certains modèles de gaz de la physique statistique et les séries génératrices des animaux valués en fonction de l'aire et parfois d'autres paramètres. Une façon d'observer cette identité est d'identifier à un changement de variable près, deux systèmes d'équations associés respectivement à la densité et aux animaux. On propose un autre point de vue sous la forme d'une construction simultanée d'animaux aléatoires et de l'occupation des sites d'un modèle de gaz. On discutera ensuite des intérêts de cette approche.
Travail en commun avec Jean-François Marckert
Résumé: En physique théorique, plus précisément en gravité quantique, les cartes sont vues comme des espaces métriques: la loi uniforme sur les quadrangulations ayant n faces, par exemple, donne un modèle d'espace métrique aléatoire sur lequel des calculs explicites peuvent être menés à bien.
Il semble qu'intégrer selon "toutes les topologies" soit nécessaire en gravité quantique: on ne sait pas faire cela (ni donner un vrai sens à cela), mais on imagine que cette intégration est la limite de l'intégration contre les quadrangulations dont on ferait tendre les longueurs d'arêtes vers 0 (vues comme espaces métriques et donc topologiques).
Dans cet exposé, on s'intéresse à une limite d'échelle des quadrangulations. On explique que les quadrangulations peuvent être vues comme deux arbres collés (courant en combinatoire, oui), dont la loi est connue. On montre que ce couple d'arbres converge, soigneusement normalisé, vers un couple d'arbres continus, ceci ouvrant la porte à une notion de carte limite, continue, que l'on a nommé la carte Brownienne.
Des travaux récents de Le Gall renforcent l'idée que la métrique de la carte Brownienne est bien la limite de la métrique des quadrangulations uniformes.
L'exposé portera essentiellement sur un travail commun avec A. Mokkadem (Versailles) et seront évoqués également quelques résultats obtenus avec G. Miermont (Orsay).
Résumé:L'énumération des chemins de Dyck (oh!) est un domaine archi-balisé de la combinatoire énumérative. On sait bien, notamment, que
On clarifiera dans cet exposé comment ceci s'étend à des chemins de Dyck généralisés (aussi appelés excursions, c'est plus court), prenant leurs pas dans un ensemble fini donné.
Résumé: Les "configurations de boucles compactes" (ou "fully-packed loops", FPL), en bijection bien connue avec les matrices à signes alternants, sont l'objet de multiples conjectures, dont la désormais célèbre "conjecture de Razumov et Stroganov" qui fait couler beaucoup d'encre et carburer pas mal de cerveaux.
À chaque FPL de taille n, on fait naturellement correspondre, en suivant les chemins décrits d'un point à un autre du bord de la grille, un couplage (parfait, sans croisements) de 2n points répartis sur un cercle - une famille d'objets comptés par les nombres de Catalan. La conjecture de Razumov et Stroganov énonce que, si l'on agit sur ces couplages en "croisant" deux brins voisins choisis aléatoirement (c'est-à-dire si, dans le couplage, on remplace les couples (i,j) et (i+1,k) par (i,i+1) et (j,k)), on obtient une chaîne de Markov sur les couplages dont la distribution stationnaire (limite) est, pour chaque couplage, exactement proportionnelle au nombre de FPL qui réalisent ce couplage.
Si l'on interprète combinatoirement cette conjecture, elle prédit qu'il existe, sur l'ensemble des FPL de taille n, 2n "opérateurs de croisement de brins" qui ont, sur les couplages associés, exactement l'effet de croiser les brins, et qui, de plus, ont la propriété qu'en appliquant chacun des 2n opérateurs à chaque FPL, on obtient exactement 2n fois chaque FPL.
Il existe d'autres conjectures autour de ces objets, en particulier sur ce qui se passe lorsqu'on se limite aux FPL (de côté 2n) qui sont invariants par une symétrie centrale; la distribution de leurs couplages est apparemment une version symétrisée de celle des FPL non contraints.
Loin de démontrer ces conjectures, j'en présenterai une nouvelle, portant sur la distribution des couplages des FPL (de côté 4n) invariants par une rotation d'un quart de tour. Afin d'aiguiser les appétits, rappelons simplement l'une des formules d'énumération démontrées par Kuperberg: si A(n), B(n) et C(n) désignent respectivement les nombres de FPL de côté n généraux, symétriques par demi tour et symétriques par quart de tour, on a
Résumé: Cet exposé reprend les "configurations de boucles compactes" (FPL) de l'exposé précédent par Philippe Duchon, et leur bijection bien connue avec les matrices à signes alternants. Pour ce dernier exposé de l'année, je donnerai quelques friandises marsiennes pour mieux passer les fêtes.
Résumé: J'énumère les escaliers ayant une colonne droite et une colonne gauche fixes. Ces objets combinatoires correspondent aux configurations de glace carrée, ou aux matrices à signes alternants, ayant une partie haute et partie basse (de largeur arbitraire) fixées. En prenant un poids qui généralise les inversions des permutations, on obtient, comme fonctions de partition, des polynômes combinatoires bien connus dits polynômes de Schubert.
Résumé: Dans un article paru dans JCT, Marcus et Tardos démontrent que le nombre de permutation de n évitant un motif donné, est borné par cn, où c dépend du motif.
On donnera les détails de cette preuve.
Résumé: Le "glissement de dominos" est une procédure introduite par Elkies, Kiperberg, Larsen et Propp, et qui permet de démontrer que le nombre de pavages du "diamant aztèque" d'ordre n par des dominos est 2n(n+1)/2. Cette procédure permet de transformer un pavage partiel du diamant d'ordre n en pavage partiel du diamant d'ordre n+1; en s'appuyant sur une correspondance connue avec les matrices à signes alternants et les configurations de boucles compactes (FPL), on peut la voir comme un moyen systématique de passer d'un FPL quelconque de taille n à un ensemble de FPL de taille n+1.
Par ailleurs, parmi les nombreuses conjectures portant sur les FPL, on trouve celle-ci: le nombre de FPL de taille n est égal au nombre de FPL de taille n+1 de schéma de couplage (1,2)(3,4)...(2n+1,2n+2).
Je présenterai une construction déterministe, basée sur le glissement de dominos, qui permet, à partir d'un FPL quelconque, de construire un FPL de la taille suivante présentant le schéma de couplage ci-dessus (et un autre, présentant le couplage similaire (2n+2,1)(2,3)...(2n,2n+1)). Cette construction résoudrait la conjecture, si elle avait le bon goût d'être bijective - ce n'est malheureusement pas le cas. Elle donne néanmoins une piste possible pour trouver une variante qui, elle, le serait.
Résumé: Après quelques rappels concernant les permutations (notion de décomposition, ordres faible et fort), je présenterai comment l'ordre fort se comprend bien à l'aide de la notion de "clé" d'une permutation, ce qui permet de plus de plonger le groupe symétrique Sn dans le treillis des matrices à signes alternants (MSA).
Puis je montrerai que 2 notions de "clé" définies indépendamment sur les MSA coïncident.
Cette idée de clé permet d'obtenir facilement le nombre de MSA ayant un seul -1,... mais moins facilemnet que via une simple extraction observée par Viennot, qui se généralise d'ailleurs à 2 entrées négatives.
Résumé: Sous des hypothèse algébriques, certains systèmes dynamiques symboliques associés à des substitutions peuvent admettre une représentation géométrique. Dans ce cas, on peut établir des liens entre des propriétés de nature combinatoire, géométrique ou ergodique, et formuler de nombreuses questions encore non résolues.
Dans cet exposé, nous nous intéressont à l'étude de propriétés combinatoires. Après avoir rappelé les notions utiles à l'étude de systèmes substitutifs, nous montrerons comment l'étude des paires équilibrées irréductibles permet d'obtenir des informations sur l'algorithme des paires équilibrées. Nous nous intéresserons plus particulièrement aux cas des langages sturmiens, d'Arnoux-Rauzy, puis nous nous intéresserons à une représentation géométrique discrète permettant d'étudier une classe de langages substitutifs.
Résumé: Cet exposé est le premier d'une série de trois, formant un petit cours d'introduction à l'énumération asymptotique et à l'étude des grands objets aléatoires.
Cette première partie est essentiellement publicitaire, et cherche à expliquer pourquoi, même quand on a déjà obtenu des résultats exacts, on peut avoir envie d'obtenir également des résultats asymptotiques. Ces idées sont bien connues des familiers du groupe ALEA, qui auront le droit de bailler (discrètement).
Les deux exposés suivants donnent des méthodes pour faire de l'asymptotique. Ils serviront sans doute à boucher d'autres "trous" du groupe de travail, un de ces jours.
Résumé: Les tresses mathématiques sont issues d'une idée assez simple et naturelle. Cependant, leur étude mathématique, commencée par Artin en 1926, soulève des problèmes intéressants et difficiles.
Je commencerai par donner différentes présentations du groupe des tresses. Je parlerai plus particulièrement de la présentation par générateurs et relations, du problème du mot dans ce cas et comment y répondre. J'expliquerai ensuite comment compter et treseer aléatoirement quand on se limite à 3 brins et pourquoi il est difficile de passer à 4 brins (et a fortiori à un nombre quelconque de brins). Je donnerai ensuite l'idée d'une preuve pour calculer la série génératrice des tresses positives et finirai avec quelques questions et idées sur l'étude des tresses générales.
Résumé: La fouille de données est un domaine de l'informatique qui s'attache à extraire de nouvelles informations dans de grandes bases de données. Plusieurs approches existent et nous nous placerons dans le cadre de la fouille de données orientée motifs.
Dans ce contexte, les informations sont représentées par des motifs qui apparaissent fréquemment. Les éléments qui composent ces motifs sont de fait très liés entre eux, ce qui constitue une première information. Lors de l'exposé, je parlerai de trois types de motifs: les motifs fréquents, les motifs fermés et les motifs de la bordure négative. Ces motifs sont liés à des structures algorithmiques classiques comme les graphes bipartis, les hypergraphes ou les treillis. En revanche, très peu de choses sont prouvées concernant leur nombre. Dans le pire des cas, ce nombre est exponentiel, mais les expériences montrent un tout autre comportement.
L'objectif de l'exposé sera de faire l'analyse en moyenne de ces motifs à travers les structures de graphes et d'hypergraphes. On parlera alors des séparateurs (minimaux) dans les graphes bipartis pour l'analyse des motifs fréquents et fermés, alors que l'analyse des motifs de la bordure négative fera intervenir des traverses minimales d'hypergraphes.
Résumé: We will present two types of random lattice walks restricted to the quarter plane whose generating functions is not holonomic (not D-finite). The non-holonomy is established using the iterated kernel method, a variant of the kernel method recently introduced in work on walks in wedges (Janse van Renseberg et al.), and related to methods used by Bousquet-Mélou and Petkovsec in their work on Knight's walks.
These results add evidence to a recent conjecture about the holonomy of generating functions of walks in the quarter plane. We will also give an asymptotic expression for the number of walks of a given length, and discuss general characteristics of combinatorial objects with non-holonomic generating functions.
This is work done in collaboration with Andrew Rechnitzer
Résumé: On peut exprimer en logique du second-ordre (de préférence monadique) les versions "sokalisées" (multivariées) des polynômes de Tutte et d'entrelacement. Il en résulte pour leurs "troncations" des algorithmes polynomiaux de calcul explicite pour des graphes de largeur de clique ou arborescente bornée. Plus difficile d'un point de vue logique est de comprendre la signification des coefficients négatifs, par exemple du polynôme chromatique. Des pistes dans cette direction seront présentées.
Résumé: I will describe how a systematic approach of evaluating moments of orthogonal polynomials helps in the study of Hankel determinants and continued fractions, and also discuss a situation where Hankel determinants (related to the number of ternary trees) can best be evaluated by other methods.
Résumé: Dans un précédent exposé, j'ai présenté une nouvelle conjecture liant la distribution des schémas de couplage des configurations de boucles compactes (FPL) invariantes par quart de tour, de taille 4n, à celle des schémas de couplage des FPL invariantes par demi-tour de taille 2n.
Une conséquence de cette conjecture (et des formules d'énumération prouvées par Kuperberg) est qu'une certaine sous-classe des FPL invariantes par quart de tour de taille 4n doit être énumérée par le carré du nombre de FPL (sans symétries) de taille n. En utilisant la technique des "arêtes fixées" due à Caselli et Krattenthaler, on ramène cette énumération à celle des pavages par losanges de certaines régions du réseau triangulaire, et il s'avère que cette énumération par le carré du nombre de FPL de taille n a déjà été démontrée par Ciucu en 99.
Dans cet exposé "light" de fin d'année, je présenterai cette jolie histoire dont j'espère qu'elle n'est pas terminée.