Le Séminaire de Combinatoire Enumérative et Analytique, rebaptisé Séminaire Philippe Flajolet le 7 avril 2011, a pour objectif de couvrir un large spectre de recherche en combinatoire, et est ouvert à tous les chercheurs et étudiants intéressés.

Il se tient un jeudi tous les deux mois à l'IHP, plus de détails ici.

Les séances de l'année 2017 - 2018 auront lieu :

  • jeudi 21 septembre 2017 - IHP, Amphi Hermite
  • jeudi 7 décembre 2017 - IHP, Amphi Hermite
  • jeudi 15 février 2018 - IHP, Amphi Hermite
  • jeudi 12 avril 2018 - IHP, Amphi Hermite
  • jeudi 7 juin 2018 - IHP, Amphi Darboux


Prochaine séance : jeudi 7 décembre 2017, Amphi Hermite, IHP
  • 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.

  • 16h : pause café