2016 – 2017

Le séminaire a eu lieu les jeudis 29 septembre 2016, 1er decembre 2016, 2 février 2017, 30 mars 2017, et 1er juin 2017.

29 septembre 2016

  • Arnau Padrol (IMJ, Paris 6),
    Tropical Catalan Subdivisions.
    Transparent. 
We revisit an ubiquitous associahedral triangulation, introduced by Gelfand, Graev and Postnikov in 1997, to provide geometric realizations of the v-Tamari lattice of Préville-Ratelle and Viennot as the dual of a triangulation of a polytope, as the dual of a mixed subdivision, and as the edge-graph of a polyhedral complex induced by an arrangement of tropical hyperplanes. The method generalizes to type B. 

This is joint work with Cesar Ceballos and Camilo Sarmiento.
  • Kilian Raschel (LMPT, Tours),
    Marches aléatoires dans des cônes : exposants critiques.
    Transparent. 
Le modèle combinatoire des marches dans des cônes connaît actuellement un essor considérable. Dans cet exposé nous parlerons de marches à grands pas, en dimension quelconque et de marches avec des poids. Nous nous concentrerons sur les exposants critiques qui apparaissent dans les asymptotiques


  1. des nombres d'excursions (marches reliant deux points fixés en un nombre donné de pas tout en restant dans un cône),
    2. 

  2. des nombres de marches de longueur prescrite.

Nous présenterons les travaux fondateurs de Denisov et Wachtel répondant à (1) ainsi que des résultats partiels et des conjectures liés à (2). Nous évoquerons des énoncés nouveaux de non-D-finitude des séries génératrices de comptage.

Il s'agit de résultats correspondant à des travaux en cours avec Julien Courtiel, Steve Melczer et Marni Mishna d'une part, Rodolphe Garbit et Sami Mustapha d'autre part.
  • Sophie Morier-Genoud (IMJ, Paris 6),
    Cônes tangents aux variétés de Schubert.

Les variétés de Schubert, objets classiques en théorie des représentations, ont une géométrie et combinatoire très riches. Ces variétés admettent très souvent des singularités au point origine (commun à toutes les variétés). Le cône tangent à une variété au point origine, i.e. l'ensemble des vecteurs tangents à l'origine, donne une caractéristique de la singularité. Cette caractéristique est plus précise que celle donnée par l'espace tangent. Cependant les cônes sont bien moins étudiés et compris que les espaces tangents. Dans cet exposé nous rappellerons les notions élémentaires liées aux variétés de drapeaux et aux variétés de Schubert, puis nous formulerons un critère combinatoire pour que deux variétés de Schubert admettent le même cône tangent. 

Travail en commun avec D. Fuchs, A. Kirillov, V. Ovsienko.

1 décembre 2016

  • Christina Goldschmidt (Oxford),
    Parking on a tree.

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).
  • Jean-Christophe Novelli (LIGM, Marne-la-Vallée),
    Promenade autour de l’inversion de Lagrange.

Cet exposé présentera des travaux récents ayant tous des liens profonds avec l'inversion de Lagrange, notamment des calculs dans les opérades dendriformes, des résultats sur les probabilités libres et encore d'autres composantes de la combinatoire algébrique et bijective. 

Travaux en commun avec Matthieu Josuat-Vergès, Frédéric Menous et Jean-Yves Thibon.
  • Guillem Perarnau (Birmingham),
    A switching approach to random graphs with a fixed degree sequence.

For a fixed degree sequence $D=(d_1,...,d_n)$, let $G(D)$ be a uniformly chosen (simple) graph on $ \{1,...,n\} $ where the vertex $i$ has degree $d_i$. The study of $G(D)$ is of special interest in order to model real-world networks that can be described by their degree sequence, such as scale-free networks. While many aspects of $G(D)$ have been extensively studied, most of the obtained results only hold provided that the degree sequence $D$ satisfies some technical conditions. 

In this talk we will introduce a new approach (based on the switching method) that allows us to study the random graph $G(D)$ imposing no conditions on $D$. Most notably, this approach provides a new criterion on the existence of a giant component in $G(D)$. Moreover, this method is also useful to determine whether there exists a percolation threshold in $G(D)$. 

The first part of this talk is joint work with F. Joos, D. Rautenbach and B. Reed, and the second part, with N. Fountoulakis and F. Joos.

2 février 2017

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

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.
  • Vadim Gorin (MIT),
    Boundaries of branching graphs through stochastic monotonicity.

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.

30 mars 2017

  • Gaetan Borot (Max Planck Institute for Mathematics, Bonn),
    The ABCD of topological recursion.

I will give a short introduction to the formalism of topological recursion, which has been simplified and generalised by a recent proposal by Kontsevich and Soibelman: no geometry is necessary to present it, only algebra and combinatorics. The initial data is now a collection (L_i)_i of differential operators in many variables, which are atmost quadratic in derivatives and satisfy Lie algebra commutation relations. The topological recursion then produces the Taylor coefficients of the common solution to the equations {L_i Z = 0}_{i}. For the simplest initial data, Z just counts trivalent graphs with certain conditions, and can be exactly computed in terms of Whittaker functions. In general, the topological recursion appears as a sum over these graphs. 

In fact, finding initial data is not a priori an easy task ! I will present 3 classes of initial data, respectively obtained from the data of a Frobenius algebra, of a non-commutative Frobenius algebra, and of the vector space of formal series with coefficients in a Frobenius algebra. This third class of examples contains the topological recursion from the former Eynard and Orantin perspective -- so, I will review some already known applications of topological recursion to various problems of enumerative geometry, in light of Kontsevich-Soibelman approach, which is hopefully combinatoralist-friendly.

If time permits I will pose and motivate open questions about large genus asymptotics.
 
Based on joint work with J.E. Andersen, L. Chekhov and N. Orantin.
  • Rinat Kedem (University of Illinois at Urbana-Champaign),
    T-systems and discrete integrable systems.
    Transparent. 
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.
  • Cédric Boutillier (LPMA, Paris 6),
    The Z-invariant Ising model on isoradial graphs.
    Transparent. 
The Ising model is a mathematical model for ferromagnetism in which spins are located at vertices of a graph. For a large class of embedded planar graphs, called isoradial graphs, local weights for this model can be found so that an integrability condition (the Yang-Baxter relation) is satisfied. The model is then said to be Z-invariant.

In a joint work with Béatrice de Tilière (Créteil) and Kilian Raschel (Tours), we study the Z-invariant Ising model on infinite isoradial graphs. We show that certain probabilistic quantities have a local expression in terms of the geometry of the embedding of the graph. Our main tool is Fisher's bijection between the Ising model and a dimer model on a decorated graph. We will discuss the properties of this model in connection with the geometry of an algebraic curbe naturally associated to the dimer model.

1 juin 2017

  • Irène Marcovici (Université de Lorraine, Nancy),
    Ergodicité de certains automates cellulaires bruités.
    Transparent. 
Quand on perturbe un automate cellulaire par un bruit aléatoire (probabilité positive d'erreur, indépendamment pour différentes cellules), on s'attend généralement à ce que le système soit ergodique, c'est-à-dire à ce qu'il oublie progressivement la configuration initiale au cours de son évolution. Lorsque le bruit est suffisamment élevé, des méthodes classiques de couplage permettent de le montrer. Mais lorsque le bruit est faible, l'ergodicité est souvent difficile à prouver. Je présenterai différentes extensions de la méthode de couplage lorsque l'automate cellulaire a des propriétés spécifiques (nilpotence, permutivité...).
  • Elie de Panafieu (Bell Labs France, Nokia),
    Combinatoire analytique des graphes connexes.
    Transparent. Synthèse. 
Nous présentons le calcul, basé sur la combinatoire analytique, de l'asymptotique des graphes connexes en fonction de leur nombre de sommets et d'arêtes. Il s'agit à la fois d'un problème naturel pour de nombreuses applications où les graphes connexes apparaissent, mais aussi d'un défi motivant l'élaboration de nouveaux outils d'énumération des graphes. Pour parvenir au résultat, nous aborderons l'énumération des graphes à degrés contraints, et des graphes où une famille de sous-graphes est interdite. Une partie de ces travaux a été présentée à FPSAC'16.
  • Jean-Christophe Aval (Labri, Bordeaux),
    Fonctions de parking.
    Transparent. 
Les fonctions de parking sont des objets classiques en combinatoire, énumérative ou algébrique. On peut les définir comme des étiquetages de chemins de Duck, qui sont des chemins avec des pas $(1,0)$ et $(0,1)$, usuellement dessinés dans le carré $n \times n$, et contraints à être au-dessus de la diagonale. Il est bien connu que leur nombre est $(n + 1)^{n-1}$. Le groupe symétrique $S_n$ agit sur les fonctions de parking par permutation des étiquettes. Cette action est élégamment traduite en termes de fonctions symétriques via la caractéristique de Frobenius. Dans cet exposé, nous étudierons certaines généralisations : pour les fonctions de parking incluses dans un rectangle $m\times n$, pour les fonctions de parking de Schroder, analogues du cas précédent pour les chemins de  Schroder, pour lesquels un troisième type de pas $(1,1)$ est permis. Enfin, nous verrons une notion de fonctions de parking {\em entrelacées}, relatives à une action de $S_n \times S_m$. 

C'est un travail en commun avec F. Bergeron (Montréal).