2017 – 2018

Le séminaire a eu lieu les jeudis 21 septembre 2017, 7 décembre 2017, 15 février 2018, 12 avril 2018, et 7 juin 2018.

21 septembre 2017

  • Laurent Ménard (Université Paris Ouest),
    Triangulations munies d’un modèle d’Ising : algébricité et convergence locale.
    Transparents. 
En 2003, Angel et Schramm ont montré que la loi uniforme sur les triangulations planaires convergeait au sens de la limite locale lorsque l’on faisait tendre leur taille vers l’infini. La loi limite, appelée UIPT (pour Uniform Infinite Planar Triangulation) a été depuis très étudiée et est maintenant un objet bien compris.

Dans mon exposé, je montrerai un résultat analogue à celui d'Angel et Schramm mais pour des triangulations échantillonnées selon la loi correspondant à un modèle d’Ising et non à la loi uniforme.

La principale difficulté est d’étendre au modèle d’Ising les résultats combinatoires et énumératifs connus dans le cadre des triangulations « sans matière ». En partant des travaux de Bernardi et Bousquet-Mélou, nous allons voir que les séries génératrices de triangulations à bord simple munies de spins sont algébriques quelles que soient les conditions au bord. Une analyse de singularité donnera alors accès aux informations voulues.

La partie combinatoire de l'exposé parlera surtout de la méthode des invariants de Tutte (et un peu de maple si on a le temps!). Pour le côté probabiliste, on se basera sur une décomposition en tranches des triangulations "à la Krikun".

Il s’agit d’un travail commun avec Marie Albenque et Gilles Schaeffer.
  • Viviane Pons (LRI, Université Paris Sud),
    Treillis et Algèbre de Hopf sur les relations binaires.
    Transparents. 
Nous expliquons comment des structures bien connues telles que l'ordre faible sur les permutations ou bien l'algèbre de Hopf de Malvenuto Reutenaurer peuvent être obtenues à partir de définitions très simples sur les relations binaires. Nous définissions tout d'abord un treillis et une algèbre de Hopf sur les relations binaires. A partir de ces deux objets, nous obtenons un treillis et une algèbre de Hopf sur les posets d'entiers. Nous voyons ensuite comment de nombreux objets combinatoires tels que les permutations ou les arbres binaires peuvent être représentés par des posets d'entiers ce qui nous amène à re-découvrir des structures algébriques bien connues ainsi qu'à en définir de nouvelles.
  • Axel Bacher (LIPN, Université Paris Nord),
    Autour des algorithmes de rejet anticipé.
    Transparents. 
Les algorithmes de rejet anticipé sont une classe d'algorithmes de génération aléatoire dont les plus célèbres sont les algorithmes dits florentins pour les mots de Motzkin (Barcucci et al., 1992). Je présenterai plusieurs de ces algorithmes et montrerai des résultats permettant de les analyser de manière systématique en loi limite. Je montrerai aussi comment, dans certains cas (mots de Dyck ou arbres binaires, notamment), on peut obtenir des algorithmes plus efficaces en s'affranchissant de tout rejet. Enfin, je détaillerai les propriétés des lois limites de ces algorithmes, dont les densités vérifient une équation différentielle avec retard, ce qui entraîne une structure un peu inhabituelle (par exemple, elles ont une singularité en tous les points entiers).

Travail en commun avec Olivier Bodini, Alice Jacquot et Andrea Sportiello.

7 décembre 2017

  • Enrica Duchi (IRIF, Université Paris 7),
    Fighting fish.
    Transparents. 
Fighting fish are combinatorial structures made of square tiles that form two dimensional branching surfaces. A main feature of these fighting fish is that the area of uniform random fish of size $n$ scales like $n^{5/4}$ as opposed to the typical $n^{3/2}$ area behavior of the staircase or direct convex polyominoes that they generalize. In this talk we concentrate on enumerative properties of fighting fish: in particular we show that the number of fighting fish with $i$ left lower free edges and $j$ right lower free edges is equal to $(2i+j−2)!(2j+i−2)!/i!j!(2i−1)!(2j−1)!$.
These numbers are known to count rooted planar non-separable maps with $i+1$ vertices and $j+1$ faces, or two-stack-sortable permutations with respect to ascending and descending runs, or left ternary trees with respect to vertices with even and odd abscissa.
  • Riccardo Biagioli (ICJ, Universite Claude Bernard Lyon 1),
    $321$-avoiding affine permutations, heaps, and periodic parallelogram polyominoes.
    Transparents. 
Among permutations, those that avoid the pattern $321$ are of great interest in combinatorics and algebra. They are known to be counted by the $n$th Catalan number. From an algebraic point of view, a permutation is $321$-avoiding if, and only if its corresponding element in the Coxeter group of type $A$ is fully commutative.

In this talk we consider their affine analogues, so $321$-avoiding affine permutations. We show some combinatorial characterizations of them, and we prove a formula for their enumeration with respect to the inversion number. This is done in two different ways, both related to Viennot’s theory of heaps. First, we encode these permutations using certain heaps of monomers and dimers. For the second method, we introduce periodic parallelogram polyominoes, which are new combinatorial objects of independent interest. We enumerate them by extending the approach of Bousquet-Mélou and Viennot used for classical parallelogram polyominoes. We finally establish a connection between these new objects and $321$-avoiding affine permutations. 

This talk is based on a joint work with Frédéric Jouhet and Philippe Nadeau.
  • Louis Esperet (G-SCOP, Grenoble),
    Coloration de graphes et autres espaces métriques.
    Transparents. 
Un problème classique d'Hadwiger et Nelson (1945) demande le nombre minimum de couleurs nécessaires pour colorier les points du plan, de manière à ce que toute paire de points à distance exactement $1$ aient des couleurs différentes (on sait que la réponse se situe entre $4$ et $7$ couleurs). Une propriété du plan est que le nombre de couleurs nécessaires ne change pas si au lieu de considérer les paires de points à distance $1$ on considère les paires de points à distance $d$ (pour un réel $d > 0$ arbitraire). En revanche dans d'autres espaces métriques, il n'est pas clair que la réponse est indépendante de $d$ (dans le plan hyperbolique, c'est un problème ouvert). Dans cet exposé, on s'intéressera à une version discrète de ce problème, introduite récemment par Parlier et Petit. Dans cette version, on cherche à colorier les sommets de l'arbre $q$-régulier infini de manière à ce que les sommets à distance $d$ aient des couleurs différentes. Quand $d$ est impair c'est facile (deux couleurs suffisent). Quand $d$ est pair on montre que le nombre de couleurs nécessaires est de l'ordre de $d \log (q) / \log (d)$. Il se trouve que cela donne une réponse négative à un problème de van den Heuvel et Naserasr sur la coloration des graphes planaires. 

Travail en commun avec Nicolas Bousquet, Ararat Harutyunyan, et Rémi de Joannis de Verclos.

15 février 2018

  • Bruno Vallette (Université Paris 13),
    La diagonale de l’associaèdre.

Les associaèdres forment une famille de polytopes convexes qui sont les réalisations géométriques du treillis des arbres de Tamari. Ils ont de nombreuses propriétés algébriques, combinatoires, topologiques et géométriques remarquables et ils jouent un rôle crucial dans la reconnaissance des espaces de lacets itérés, en lien avec la notion d’algèbre associative à homotopie près et en géométrie algébrique via les variétés toriques par exemple. Dans cet exposé, nous expliquerons ce qu’est le problème de la diagonale de l'associaèdre à la fois algébriquement avec le calcul opéradique et combinatoirement avec la décomposition cellulaire de ces derniers. Nous montrerons aussi pourquoi ce problème est crucial : sa résolution permet de considérer le produit de A_infini-catégories de Fukaya en topologique sympléctique, le produit tensoriel en théorie des cordes ou de faire des calculs des groupes d’homologie d’espaces fibrés. L’exposé tachera de rester le plus élémentaire possible et inclura des dessins significatifs.
  • Marthe Bonamy (CNRS, LaBRI, Univ. Bordeaux),
    Partitioning a graph into isomorphic subgraphs.
    Transparents. 
Given a graph G and a subgraph H of G, we can wonder whether G admits a perfect H-packing, i.e. whether we can partition the vertices of G into (induced) copies of H. A classical example of such a question is whether a graph admits a perfect matching. There does not seem to be any good sufficient conditions for G to admit a perfect H-packing. Here, we investigate when a sufficiently high Cartesian power of G admits a perfect H-packing. We generalize a theorem of Gruslys for hypercubes to powers of even cycles, and disprove a conjecture of Gruslys as well as one by Gruslys, Leader and Tan that considers the edge setting. This type of questions has ramifications far beyond the scope of graph theory.

This is joint work with Natasha Morrison and Alex Scott.
  • Igor Kortchemski (CNRS, CMAP, École polytechnique),
    Comportement asymptotique de grandes structures discrètes aléatoires.

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.

12 avril 2018 

In this talk we will introduce a new Hopf algebra structure on pipe dreams. These combinatorial objects were introduced by Bergeron and Billey back in the 90’s, and play a fundamental role in the combinatorial understanding of Schubert polynomials in the study of Schubert varieties. We will show remarkable combinatorial properties of the Hopf dream algebra, unexpected connections to the enumeration of certain lattice walks on the quarter plane, and applications to the theory of multivariate diagonal harmonics. This is current joint work with Nantel Bergeron and Vincent Pilaud.
  • Hugo Duminil-Copin (IHES),
    Compter les marches auto-évitantes sur le réseau hexagonal.

Dans cet exposé, nous présenterons les progrès récents dans le décompte des marches auto-évitantes sur le réseau hexagonal. En particulier, nous expliquerons comment calculer la constante de connectivité du modèle, prédite par le physicien Bernard Nienhuis. Travail joint avec Stanislav Smirnov.
  • Bérénice Delcroix-Oger (IRIF, Paris 7),
    Polytopes d’hypergraphes, algèbres et opérades.
    Transparents. 
En 2011, Dosen et Petric ont généralisé la notion d'épine d'un graphe aux hypergraphes. Après avoir expliqué ces notions, nous verrons une construction qui associe à une "bonne" famille d'hypergraphes une algèbre graduée sur les épines de ces hypergraphes, et l'opérade associée. Cela fournit un cadre général dans lequel s'intègrent notamment le simplexe, le cube, l'associaèdre et le permutoèdre. Ce travail est en collaboration avec Emily Burgunder et Pierre-Louis Curien.

7 juin 2018

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

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.
  • Vlady Ravelomanana (IRIF, Paris 7),
    Combinatorics of some tractable phase transitions.

Several combinatorial structures are subject to phase transitions as one of their parameters increases when their sizes are large but fixed. Such structures include random CNF formulas (a SAT/UNSAT transition occurs from under to overconstrained instances) or random graphs (from sparse to dense instances some properties vanish).

Determining the nature of a phase transition (sharp or coarse), locating it, determining a precise scaling window and better understanding the structure of the space of solutions turn out to be very interesting tasks. These challenges have aroused a lot of interest in different communities, namely mathematics, computer science and physics. 

In this talk, we will review various phase transitions of random graph properties or  $2$-CNF formulas, emphasizing the strengths (and limits?) of enumerative/analytic approaches.