2017 - 2018


Le séminaire aura lieu les jeudis 21 septembre 2017, jeudi 7 décembre 2017, 8 février 2018, 12 avril 2018, et 7 juin 2018.

21 septembre 2017
  • 10h30 - 11h30 : 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.

  • 13h45 - 14h45: 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.

  • 14h45 - 15h45 : 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
  • 10h30 - 11h30 : Enrica Duchi (IRIF, Université Paris 7),
    Fighting fish,
    ,

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.

  • 13h45 - 14h45: Riccardo Biagioli (ICJ, Universite Claude Bernard Lyon 1),
    $321$-avoiding affine permutations, heaps, and periodic parallelogram polyominoes,
    ,

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.

  • 14h45 - 15h45 : Louis Esperet (G-SCOP, Grenoble),
    Coloration de graphes et autres espaces métriques,
    ,

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
12 avril 2018
7 juin 2018