G
  • Lucas Gerin (CMAP, Ecole Polytechnique), Processus d’Hammersley discret et sous-suites croissante, 2/06/2016
    .

À 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 uniforme. 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. Travail en commun avec A.-L.Basdevant, N.Enriquez, J.-B.Gouéré.

  • Samuele Giraudo (IGM, Paris-Est Marne-la-Vallée), Some combinatorial structures related to operads, 7/02/2019
    , Transparents.

Operads are devices intended to study algebraic structures by providing an abstraction of the notion of operation, their compositions, and the relations they satisfy. We introduce some elementary notions about operads and review some interactions between this theory and combinatorics. For this purpose, we shall explore how operads are linked with rewrite systems of trees and how to handle them as tools to enumerate families of combinatorial objects. We shall also present analogs of the Young lattice and a notion of dual pairs of graded graphs obtained from operads.

  • Xavier Goaoc (École des Mines de Nancy), Compter et simuler les types d'ordres du plan, 30/01/2020
    , Transparents.

Cet exposé introduira aux types d'ordres et aux chirotopes, des structures combinatoires d'origine géométrique qui sont encore mal comprises. Nous aborderons en particulier les questions de leur comptage et de leur génération aléatoire, deux questions actuellement mal comprises.
L'exposé ne supposera pas de connaissance géométrique et présentera plusieurs problèmes ouverts.

  • Christina Goldschmidt (Oxford), Parking on a tree, 1/12/2014
    .

Consider the following particle system. We are given a uniform random rooted tree on vertices labelled by $ [n]=\{1,2,...,n\} $, with edges directed towards the root. Each node of the tree has space for a single particle (we think of them as cars). A number $m \le n$ of cars arrives one by one, and car $i$ wishes to park at node $S_i$, $1 \le i \le m$, where $S_1, S_2, \ldots, S_m$ are i.i.d. uniform random variables on $ [n] $. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until the first time it encounters an empty space, in which case it parks there; otherwise, it leaves the tree. Let $A_{n,m}$ denote the event that all $m$ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Set $m = [\alpha n]$. Then if $\alpha \le 1/2$, $P(A_{n,[\alpha n]}) \to \sqrt{1-2\alpha}/(1-\alpha)$, whereas if $\alpha > 1/2$ we have $P(A_{n,[\alpha n]}) \to 0$. (In fact, they proved more precise asymptotics in $n$ for $\alpha \ge 1/2$.) In this talk, I will give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method.
Based on joint work in progress with Michal Przykucki (Oxford).

  • Vadim Gorin (MIT), Boundaries of branching graphs through stochastic monotonicity, 2/2/2017
    .

The problem of identifying all harmonic functions on a given directed graded graph has many faces depending on the graph specification. Advanced examples include classifications of random exchangeable sequences, of finite factor representations for infinite-dimensional symmetric and unitary groups, of Gibbs measures on lozenge tilings, of Macdonald-positive homomorphisms from the algebra of symmetric functions. I will present a recent approach to such problems based on a combination of the ideas of monotonicity and the Law of Large Numbers.

  • Élise Goujard (Institut de Mathématiques de Bordeaux), Méandres en genre supérieur, 1/10/2020
    , Transparents.

Un méandre est la configuration topologique d'une droite et d'une courbe fermée simple dans le plan (la route et la rivière) qui s'intersectent transversalement, qu'on peut voir de façon (quasi) équivalente comme la configuration de deux courbes fermées simples transversales sur la sphère. Ce point de vue permet de définir les méandres de genre g comme les configurations topologiques de deux courbes fermées simples s'intersectant transversalement sur des surfaces compactes de genre g (ces méandres de genre supérieur ont été introduits par Di Francesco-Golinelli-Guitter). On définit également les méandres orientés qui correspondent au cas où les courbes sont orientées et elles s'intersectent toujours dans le même sens (ils n'existent qu'en genre supérieur).
Les développements récents sur l'énumération des surfaces à petits carreaux en grand genre, et la correspondance entre surfaces à petits carreaux à un cylindre horizontal et un cylindre vertical avec les méandres, permettent d'énumérer les méandres dans deux cas

- à combinatoire fixée (nombre d'arcs minimaux fixé), énumération des méandres de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini
- énumération des méandres orientés de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini.
  • Emmanuel Guitter (CEA Saclay), Énumération des cartes planaires irréductibles par découpage géodésique, 6/06/2013
    , Transparents.

Une carte $d$-irréductible est une carte dont tous les cycles ont une longueur au moins égale à $d$, et dont tous les cycles de longueur exactement $d$ sont des bords de faces. Je montrerai comment une technique éprouvée d'énumération des cartes, le découpage géodésique, peut être adaptée avec succès au cas des cartes $d$-irréductibles. Les briques élémentaires obtenues par découpage, les "slices", ont elles-mêmes une structure récursive, induisant un codage naturel des cartes $d$-irréductibles par des arbres.
Cet exposé décrit un travail en commun avec J. Bouttier.

H
  • Bénédicte Haas (LAGA, Université Paris 13), Quelques propriétés géométriques des graphes stables, 20/09/2018
    .

Considérons un graphe $G_n$ uniformément choisi dans l'ensemble des graphes à $n$ noeuds étiquetés avec des degrés $D_1,\ldots,D_n$ donnés, eux-mêmes aléatoires i.i.d. tels que $\mathbb E[D^2]<\infty$ et $\mathbb P(D=2)<1$. Molloy et Reed 95 ont montré l'existence d'une composante géante si et seulement si $E[D(D-1)]>E[D]$. On se place ici dans le cas critique $E[D(D-1)]=E[D]$ et on suppose que $\mathbb P(D=k) \sim c k^{-2-\alpha}$, $1<\alpha<2$. Des travaux de Joseph 14, Riordan 12 et Conchon-Kerjan et Goldschmidt (à paraître), il résulte que le graphe $G_n$, après normalisation, converge alors vers un graphe continu aléatoire appelé \emph{graphe stable} d'indice $\alpha$. Nous présenterons ici quelques propriétés géométriques de ce graphe limite.
Basé sur un travail en collaboration avec C. Goldschmidt et D. Sénizergues.

  • Florent Hivert (LITIS-Rouen), Autour de la Formule des équerres pour les arbres, 7/04/2011
    , Transparents.

Soit $T$ un arbre binaire à $n$ noeuds. On s'intéresse au nombre d'étiquetages décroissants de $T$ par les entiers de $1$ à $n$, chaque entier apparaissant une fois et une seule. La formule des équerres pour les arbres, exprime le nombre de ces étiquetages comme le quotient de $n!$ par le produit du nombre de noeud de chacun des sous-arbres. Il est frappant de remarquer que cette formule très simple à prouver par récurrence admet un grand nombre de raffinement et de multiples facettes. Nous présenterons les liens avec la résolution de certaines équations fonctionnelles, la combinatoire du produit de mélange et le calcul dendriforme ainsi que quelques identités sur les fractions rationnelles.

  • Christophe Hohlweg (LaCIM, Université du Québec à Montréal), Ordre faible et cône imaginaire dans les groupes de Coxeter infinis, 3/04/2014
    , Transparents.

L'ordre faible est un outil combinatoire intimement liée à l'étude des mots réduits dans les groupes de Coxeter. Dans les groupes de Coxeter finis, c'est un treillis qui oriente le graphe sommets/arêtes du permutaèdre et qui donne un cadre naturel pour construire les associaèdres généralisées (via les treillis Cambrien de N. Reading). Lors cet exposé, nous allons discuter une conjecture de Matthew Dyer qui propose une généralisation de l'ordre faible et des mots réduits aux groupes de Coxeter infinis. Il sera notamment question de la relation entre les limites des racines et le pavage de leur enveloppe convexe, des ensembles biclos et d'ensemble d'inversions de mots réduits infinis.

Partiellement basé sur des travaux communs avec M. Dyer, JP Labbé et V. Ripoll

J
  • Matthieu Josuat-Vergès (Université Paris-Est Marne-la-Vallée), Factorisations minimales de cycles, une série multivariée, 4/02/2016
    , Transparents.

Pour factoriser le long cycle $(1,2,...,n)$ en produit de transpositions dans le groupe symétrique, il faut au moins $n-1$ facteurs. Le nombre de factorisations est alors $n^{n-2}$, et ces factorisations sont dites minimales. Et si on compte les factorisations du long cycle en $k$ cycles de longueur fixées $(a_1,...,a_k)$, avec une condition de minimalité, le nombre est $n^{k-1}$. De nombreuses généralisations de ce genre de résultats existent, par exemple lorsqu'on factorise une permutation quelconque, et ces problèmes ont des interprétations géométriques (nombres de Hurwitz, cartes). Ici, nous montrons qu'on peut raffiner le résultat sur $n^{k-1}$, en considérant une série génératrice multivariée (au lieu d'un simple comptage), qui se factorise dans les polynômes multivariés.

Il s'agit d'un travail en collaboration avec Philippe Biane.

  • Frédéric Jouhet (ICJ, Universite Claude Bernard Lyon 1), Congruences modulo des polynômes cyclotomiques et indépendance algébrique de $q$-séries, 20/09/2018
    , Transparents.

De nombreuses $G$-fonctions ont des coefficients satisfaisant des congruences modulo des nombres premiers. Ces congruences sont de même nature que celles découvertes par Lucas pour les coefficients binomiaux, qui se généralisent à des congruences modulo des polynômes cyclotomiques pour les coefficients $q$-binomiaux. Je donnerai une congruence générale pour des quotients multidimensionnels de $q$-factorielles qui, via un processus de spécialisation, généralise de nombreux résultats de ce type. En termes de séries génératrices, de telles congruences relient des séries entières combinatoires classiques à leurs $q$-analogues. En me focalisant sur le cas des séries à coefficients dans $\mathbb{Z}[q]$, je décrirai un phénomène de propagation de l'indépendance algébrique : lorsque de telles séries sont algébriquement indépendantes sur le corps des complexes pour $q=1$, c'est aussi le cas de leurs $q$-analogues.
Cet exposé est basé sur des travaux communs avec Boris Adamczewski, Jason Bell et Eric Delaygue.

K
  • Rinat Kedem (University of Illinois at Urbana-Champaign), T-systems and discrete integrable systems, 30/3/2017
    , Transparents.

The T-system for type A is a restricted octahedron relation, which first appeared in the context of quantum integrable spin chains with quantum affine algebra symmetries in the 80's. It has many beautiful combinatorial properties and applications, such as Frieze patterns, pentagram maps and Zamolodchikov periodicity. As a cluster algebra, it also admits a quantization. In this talk, I'll demonstrate some of the manifestations of the integrability of this system and explain the combinatorial solutions in the classical and quantum case. This talk is based on joint work with Philippe Di Francesco.

  • Bernhard Keller (IMJ, Université Paris Diderot), Mutation des carquois et identités dilogarithmiques quantiques, 20/10/2011
    .

Dans cet exposé, nous commencerons par présenter une opération élémentaire sur les graphes orientés (les carquois) : la mutation. Cette opération est apparue en physique dans la dualité de Seiberg dans les années 90 et en mathématiques dans la définition des algèbres amassées (cluster algebras) par Fomin-Zelevinsky en 2002. A des suites de mutations, nous associerons des produits de certaines séries formelles non commutatives : les (exponentielles de) dilogarithmes quantiques. Il s'avère que ces produits, construits de facon élémentaire, sont reliés aux "invariants de Donaldson-Thomas raffinés" introduits récemment par Joyce, Kontsevich-Soibelman et d'autres.

  • Matjaz Konvalinka (Université de Ljubljana), Smirnov words, Smirnov trees, and e-positivity, 7/6/2018
    .

A word is called Smirnov if adjacent letters are distinct. It is known that the generating function for Smirnov words is e-positive, i.e. it can be expressed as a linear combination of elementary symmetric functions with non-negative integer coefficients. We will define Smirnov trees and prove, via a bijection, that their generating function is also e-positive.
This is joint work with Vasu Tewari.

  • Igor Kortchemski (CNRS, CMAP, École polytechnique), Comportement asymptotique de grandes structures discrètes aléatoires, 15/2/2018
    .

On s'intéressera au comportement asymptotique d'objets « discrets » aléatoires (comme des marches aléatoires et des arbres aléatoires) lorsque leur taille tend vers l'infini, et on se demandera s'il existe une limite « continue ». Le cas échéant, on verra que son existence permet d'obtenir d'intéressantes conséquences à la fois dans le monde discret et dans le monde continu. Enfin, on étudiera plus spécifiquement le modèle des factorisations aléatoires minimales du n-cycle en transpositions (c'est-à-dire des factorisations du cycle (1,...,n) en produit de n-1 transpositions), qui fait l'objet d'un travail avec Valentin Féray.

  • Christian Krattenthaler (Wien Universitat), Crible cyclique pour des partitions non-croisées généralisées associées aux groupes de réflection complexes, 24/05/2012
    , Transparents, Synthèse.

Le crible cyclique est un phénomène énumeratif énoncé par Reiner, Stanton et White. Bessis et Reiner ont proposé deux conjectures sur des phénomènes de crible cyclique pour les partitions non-croisées généralisées associées aux groupes de réflection complexes de Armstrong et Bessis. Je commencerai en expliquant ce qu'est le crible cyclique et les partitions non-croisées généralisées, et ensuite j'exposerai les idées principales d'une démonstration de ces deux conjectures.
Ce travail a été effectué en partie avec Thomas Müller.

  • Greg Kuperberg (UC Davis), Quantum graph theory, 2/2/2017
    .

Classical error correction can be interpreted as the theory of independent sets on graphs. There is an analogous notion of a quantum graph, which is implied in quantum error correction work and has been defined in greater generality by the author and Nik Weaver. I will discuss quantum graphs and the related concept of quantum metric spaces. One pair of interesting results is that there is a version of Brooks' theorem for the independence number of a quantum graph, but not the chromatic number.

L
  • Victoria Lebed (Université de Caen), Du triangle au carré, 4/04/2019
    .

Derrière quelque chose d'aussi simple que la relation d'associativité se cache une combinatoire extrêmement riche, qui fait intervenir les triangles, les tétraèdres, les arbres binaires, les réseaux de Tamari, les associaèdres. On s'en inspirera pour parler de la combinatoire de l'équation de Yang-Baxter, et l'on verra apparaître les carrés, les cubes, les tresses, les ordres de Bruhat supérieurs, et une mystérieuse série de polytopes qui commence par un octogone. On esquissera les liens entre cette combinatoire et les théories homologique et homotopique des solutions de l'équation de Yang-Baxter.

  • Marc Lelarge (INRIA, DI ENS), Law of large numbers for matchings, extension and applications, 28/03/2013
    , Transparents, Synthèse.

The fact that global properties of matchings can be read from local properties of the underlying graph has been rediscovered many times in statistical physics, combinatorics, group theory and computer science. I will present a probabilistic approach allowing to derive law of large numbers. I will show how it extends previous results in several directions and describe some algorithmic applications.
Joint work with Charles Bordenave, Justin Salez, Mathieu Leconte, Laurent Massoulié, Hang Zhou.