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 6 juin 2024 

Nous aurons 3 exposés:

  • 11h: Gilles Schaeffer (LIX, Polytechnique)
    TBD
  • 14h: Aline Parreau (LIRIS, Université Lyon 1)
    Complexité algorithmique du jeu de domination Maker-Breaker sur les graphes
  • Dans cet exposé, nous expliquerons à travers l'exemple du jeu de domination Maker-Breaker dans les graphes comment être sûr de pouvoir construire une structure donnée face à un adversaire malveillant. Dans le jeu de domination dans les graphes, à chaque tour, Dominator choisit un sommet du graphe puis Staller lui interdit un sommet. A la fin, Dominator gagne si elle a obtenu un ensemble dominant avec ses sommets: c'est-à-dire si chaque sommet du graphe est à distance au plus 1 d'un sommet de Dominator.
    
    Alors que les problèmes classiques de graphes sont très souvent dans la classe NP, savoir si Dominator peut gagner à tous les coups est un problème PSPACE-complet. Cela est en particulier dû au fait que décrire une stratégie pour l'un des joueurs ne peut se faire en temps polynomial en général. Nous verrons dans cet exposé des stratégies structurelles pour Dominator qui sont suffisantes pour certaines classes de graphes comme les graphes d'intervalles, les graphes planaires extérieures ou les graphes réguliers. Cela permet en particulier d'améliorer la complexité du problème dans ces classes de graphes : ainsi les graphes réguliers peuvent toujours être dominés par Dominator, déterminer qui gagne pour un graphe planaire extérieur est polynomial. Pour les graphes d'intervalles, nous obtenons que ce problème est dans NP en le ramenant à la recherche d'une structure particulière dans le graphe mais ne savons pas si cette recherche peut se faire en temps polynomial...
  • 15h: Baptiste Rognerud (IMJ-PRG)
    Un ordre partiel d’origine algébrique sur les tableaux de permutation
  • Les treillis de Tamari sont des ordres partiels particulièrement bien étudiés, qui apparaissent dans de nombreux domaines des mathématiques.En théorie des représentations ils apparaissent, par exemple, comme ensembles de modules basculants d'une certaine algèbre. Dans cet exposé nous allons brièvement introduire une famille de modules qui généralise les modules basculants. Ces modules sont en réalité très anciens, ils remontent essentiellement à Schur, mais de façon curieuse aucun résultat de classification n'a été obtenu avant nos travaux. Nous allons voir que dans un cas simple, cette classification fait intervenir de la combinatoire très sympathique de remplissages de diagrammes.
    Il sera ensuite très naturel d'introduire une relation d'ordre sur ces objets et nous verrons que celle-ci généralise la relation d'ordre de Tamari. Informellement c'est un "ralentissement" de la rotation des arbres binaires. Dans la seconde partie de l'exposé, nous verrons que cette relation d'ordre possède d'excellentes propriétés : essentiellement toutes les propriétés de l'ordre de Tamari.
    C'est un travail en commun avec Crawley-Boevey, Ma et Sauter et plus récemment avec Corteel et Jang.

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
      • Lucas Gerin
      • Nathalie Aubrun
      • Alin Bostan
    • jeudi 06 juin 2024
      • Gilles Schaeffer
      • Aline Parreau
      • Baptiste Rognerud