Séminaire de combinatoire Combinatoire Enumérative et Analytique (séminaire Flajolet)

Le Séminaire de Combinatoire Enumérative et Analytique, également appelé Séminaire Philippe Flajolet depuis 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. Le séminaire a lieu à l’IHP.

Prochaine séance : Jeudi 4 avril 2024 

Nous aurons 3 exposés:

  • 11h: Lucas Gerin (CMAP, Ecole Polytechnique),
    Plus longue sous-suite croissante dans une multi-permutation
Le problème d'Ulam (ou Ulam-Hammersley, ou Ulam-Hammersley-Versik-Kerov, ou...) consiste à étudier la longueur de la plus longue sous-suite croissante dans une permutation aléatoire uniforme. Apparu dans les années 60, ce problème a été souvent revisité en mélangeant combinatoire algébrique, calcul des variations, matrices aléatoires, processus aléatoires,... Le but de cet exposé est de rappeler le problème historique et de présenter l'approche "processus" pour le problème d'Ulam sur des k-multipermutations : il s'agit de mots dans lesquels chaque lettre parmi 1,...,n apparaît exactement k fois.
Référence : L.Gerin. The Ulam-Hammersley problem for multiset permutations (preprint, 2023).
  • 14h: Nathalie Aubrun (LISN),
    Jeux de tuiles robustes et problème du domino
L'un des problèmes les plus fondamentaux en théorie du pavage est le problème du domino : étant donné un ensemble de tuiles, peut-on décider s'il existe un moyen de paver le plan? Depuis les années 60 on sait que ce problème est indécidable en général y compris en se restreignant aux tuiles de Wang, qui sont des tuiles carrées unitaires avec des couleurs sur leurs bords et que l'on peut assembler à condition qu'elles partagent la même couleur sur leur bord commun. Dans cet exposé je présenterai une notion de robustesse pour des jeux de tuiles de Wang : plusieurs jeux de tuiles célèbres de la littérature possèdent cette propriété, et satisfont donc un certain invariant de manière prouvable, et le problème du domino devient décidable pour les jeux de tuiles robustes.
Il s’agit d’un travail en collaboration avec Manon Blanc et Olivier Bournez.

  • 15h: Alin Bostan (INRIA Saclay),
    How to decide if a D-finite power series is algebraic?
A power series is said to be D-finite ("differentially finite”) if it satisfies a linear differential equation with polynomial coefficients. D-finite power series are ubiquitous in combinatorics, as well as in number theory and mathematical physics. In a seminal 1980 article, Richard Stanley asked whether it is possible to decide if a given D-finite power series is algebraic or transcendental.  There are several very useful sufficient criteria for transcendence, but none also provides a sufficient condition. One of them is a powerful criterion due to Philippe Flajolet, based on asymptotics of coefficients. Characterizing the algebraicity of a D-finite power series is a highly non-trivial task even if the sequence of its coefficients satisfies a recurrence of order one: this question was completely settled only in 2023 by Florian Fürnsinn and Sergey Yurkevich, building on important articles by Gilles Christol (1986) and by Frits Beukers and Gert Heckman (1989). In this talk, I will present answers to Stanley’s question and illustrate them through several examples coming from combinatorics and number theory.

Liste des séances de l’année

Les séances de l’année 2023-2024 ont lieu :

    • jeudi 28 septembre 2023:
      • Valentin Bonzom
      • Cédric Boutillier
    • jeudi 07 décembre 2023: (commun avec la conférence Computer Algebra for Functional Equations in Combinatorics and Physics)
      • Arvind Ayyer
      • Mireille Bousquet-Mélou
      • Tony Guttmann
      • Dan Romik
    • jeudi 08 février 2024
      • Mylène Maïda
      • Carla Groenland
      • Carola Doerr
      • Sanjay Ramassamy
    • jeudi 04 avril 2024
    • jeudi 06 juin 2024