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 à tou·te·s les chercheur·se·s et étudiant·e·s intéressé·e·s.

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

En 2020-2021, le séminaire reprend en mode virtuel. Première séance le jeudi 1er octobre à 10 heures!
Jeudi 4 février 2021

Cette journée du séminaire Flajolet a lieu dans le cadre des journées combinatoires de Bordeaux. Les exposés ont eu lieu en visioconférence.

  • 10h00 - 11h00 : Valentin Ovsienko (Laboratoire de Mathématiques de Reims),
    Combinatorial and analytic properties of $q$-deformed real numbers,
    .

I will explain a recent notion of $q$-deformed real numbers, and discuss its various combinatorial and analytic properties. A "$q$-deformed real" is a Laurent series in one variable, $q$, with integer coefficients. The subject is connected to different theories, such as knot invariants, continued fractions, and cluster algebras. I will formulate a challenging conjecture about the convergence of the series arising as $q$-deformed real numbers. (Here we understand $q$ as a complex variable.) The conjecture is proved in particular cases and concrete examples. In the most simple examples of $q$-Fibonacci and $q$-Pell numbers, the explicit formulas for the radius of convergence are very similar to certain formulas of Ramanujan.
The talk is based on a joint work with Ludivine Leclere, Sophie Morier-Genoud and Alexander Veselov.

  • 11h00 - 12h00 : Ilse Fischer (Universität Wien),
    Bijective proofs of alternating sign matrix theorems,
    .

Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and alternating sign triangles, and their numbers are given by a simple product formula. For about 40 years now, combinatorialists have been trying to construct bijective proofs of these relations.
We present the first bijective proof of the enumeration formula for alternating sign matrices and of the fact that alternating sign matrices are equinumerous with descending plane partitions. Our constructions rely on signed sets, sijections and related notions such as a generalization of the Garsia-Milne involution principle. The starting point for these constructions are known “computational” proofs, but the combinatorial point of view led to several drastic modifications. We also provide computer code where all of our constructions have been implemented.
This is joint work with Matjaz Konvalinka.

Jeudi 3 décembre 2020

Les exposés auront lieu en visioconférence. Le lien pour accéder aux exposés est https://bbb.lipn.univ-paris13.fr/b/bas-wsn-pcg-dri (code d'accès 07084X) où X est le premier entier suivant 2.

La vidéo des exposés est accessible ici.

  • 10h00 - 11h00 : Marni Mishna (Simon Fraser University),
    The Kaleidoscopic Splendor of Lattice Walk Enumeration,
    .

This talk will examine the rich topic of lattice path enumeration. A very classic object of combinatorics, lattice walks withstand study from a variety of perspectives. Even the simple task of classifying the two dimensional walks restricted to the first quadrant has brought into play a surprising diversity of techniques from algebra to analysis to geometry. We will consider walks under a few different lenses. We will see how lattice walks arise in algebraic combinatorics and group theory, and the impact of classification. We will show that a geometric perspective can offer a visual intuition of the role of weighted steps in enumeration formulas. We will also consider some of the existing recent developments using elliptic curves to unravel where the future may lie.

  • 11h00 - 12h00 : Laurent Viennot (INRIA & IRIF),
    A trip through hub labeling in graphs,
    .

Hub labeling is a simple method for coding distances in a graph. It work surprisingly well in road networks where it offers a very compact representation of travel times between any two points and thus allows very fast computation of shortest paths. We will see a graph property called skeleton dimension that explains such efficiency and that seems to fit with road networks. This method has been shown to work well also on various practical graphs. An intriguing problem in distributed computing resides in building such compact representation for sparse graphs in general. We will see that a family of sparse graphs requires almost quadratic space for any hub labeling. These graphs are connected to the Rusza-Szemerédi function counting induced matchings in dense graphs. We also relate the problem of finding more general distance labels for these graphs to the sum index problem in communication complexity, a second hint that representing distances with sub-quadratic space seems hard even in sparse graphs.

Jeudi 1er octobre 2020

Les exposés ont eu lieu en visioconférence.

La vidéo des exposés est accessible ici.

  • 10h00 - 11h00 : Élise Goujard (Institut de Mathématiques de Bordeaux),
    Méandres en genre supérieur,
    , 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.
  • 11h00 - 12h00 : Andrew Elvey-Price (CNRS, Université de Tours),
    Counting lattice walks by winding angle,
    , Transparents.

We count walks by winding angle around the origin on four different lattices. Our method uses a decomposition of each lattice, which allows us to write functional equations characterising generating functions for these walks. We then exactly solve these equations in terms of Jacobi theta functions, allowing us to extract asymptotic information about the associated counting sequences using methods popularised by Flajolet and Sedgewick. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.

Liste des séances de l'année

Les séances de l'année 2020-2021 auront lieu :

  • jeudi 1er octobre 2020 - en visioconférence.
    • Élise Goujard (Institut de Mathématiques de Bordeaux)
    • Andrew Elvey-Price (CNRS, Université de Tours)
  • jeudi 3 décembre 2020 - en visioconférence
    • Marni Mishna (Simon Fraser University)
    • Laurent Viennot (INRIA & IRIF)
  • jeudi 4 février 2021 - en visioconférence.
    • Ilse Fischer (Universität Wien)
    • Valentin Ovsienko (Laboratoire de Mathématiques de Reims)
  • jeudi 1er avril 2021
  • jeudi 3 juin 2021