---
Lundi 16 septembre: conférence Highlights & Jewels of Automata Theory
- 09h00-09h50: Wolfgang Thomas "On the Finiteness of Infinite Regular Games"
- 09h50-10h40: byArtur Jeż "What's new in word equations"
- 11h10-12h00: Jarkko Kari "Low complexity colorings of the two-dimensional grid"
Lundi 23 septembre: Bishal Deb (LPSM, Paris)
title: Continued fractions using a Laguerre digraph interpretation of the Foata--Zeilberger bijection
abstract: In the combinatorial theory of continued fractions, the Foata–Zeilberger bijection and its variants have been extensively used to derive various continued fractions enumerating several (sometimes infinitely many) simultaneous statistics on permutations (combinatorial model for factorials) and D-permutations (combinatorial model for Genocchi and median Genocchi numbers). We will begin this talk by taking a look at some of these multivariate continued fractions. We will then sketch out the Foata--Zeilberger bijection.
We will then introduce a Laguerre digraph which is a digraph in which each vertex has in- and out-degrees 0 or 1. We then provide a new interpretation of the Foata–Zeilberger bijection in terms of Laguerre digraphs, which enables us to count cycles in permutations. This interpretation enables us to prove some conjectured continued fractions due to Sokal and Zeng (2022) in the case of permutations, and Randrianarivony and Zeng (1996) and Deb and Sokal (2024) in the case of D-permutations.
Attach:CI-2024-09-23-BishalDeb.pdf
Lundi 30 septembre: Florent Koechlin (LIPN, Paris)
Title: A canonical tree decomposition for chirotopes
Résumé : Dans cet exposé, je présenterai une notion d’arbre de décomposition d’un ensemble de points dans le plan (plus précisément de son chirotope, la fonction qui encode l'orientation de tout triplet de point de l'ensemble). Cette décomposition, qui s'appuie sur le concept d'ensembles de points s'évitant mutuellement ("mutually avoiding sets"), s'inspire de la décomposition modulaire des graphes. J'expliquerai pourquoi cette décomposition est canonique, et comment elle peut être utilisée pour calculer le nombre de triangulations d'un chirotope à l'aide de sa décomposition. Il s'agit d'un travail commun avec Mathilde Bouvel, Valentin Féray et Xavier Goaoc.
In this talk, I'll introduce a notion of decomposition tree for points set in the plane (more precisely, of its chirotope, that is the function encoding the orientation of any triplet of points in the set). This decomposition relies on the concept of mutually avoiding sets, and is inspired by the modular decomposition of graphs. I'll explain why this decomposition is canonical, and how it can be used to compute the number of triangulations of a chirotope using its decomposition. This is a joint project with Mathilde Bouvel, Valentin Féray and Xavier Goaoc.
Attach:Koechlin-2024-09-30.pdf
Lundi 7 octobre: Lionel Pournin (LIPN, Paris)
Title: The geometry of flip-graphs of topological surfaces
Abstract: A triangulation of a topological surface Σ is a set of pairwise non-crossing arcs in Σ that decompose the surface into triangles and whose endpoints belong to a prescribed, finite set of vertices. The flip-graph F(Σ) is the graph whose vertices are these triangulations and whose edges connect two triangulations when they differ by a single arc. This graph is always connected and, except for a few surfaces, it is infinite. By the Švarc--Milnor lemma, F(Σ) provides a combinatorial model for the mapping class group of Σ. More precisely, F(Σ) is quasi-isometric to the Cayley graphs of the mapping class group of Σ. When Σ is a Euclidean polygon whose vertex set is the vertex set of the triangulations, F(Σ) is finite and already interesting: it is the edge-graph of a polytope---the associahedron---and computing distances in this graph is a major open problem in computer science. This talk, based on joint work with Hugo Parlier and with Zili Wang, reviews the results obtained over the last few decades on the geometry of F(Σ).
In the first part of this talk, the quotient MF(Σ) of F(Σ) by the homeomorphisms of Σ is studied. This quotient is a finite graph whose diameter allows to estimate the constants of the quasi-isometry between F(Σ) and the Cayley graphs of the mapping class group of Σ. Results on the diameter of MF(Σ) are presented and a number of open problems are given.
The second part focuses on the Sleator--Tarjan--Thurston 3-dimensional triangulation model for the paths in F(Σ) in the case when it is the edge-graph of the associahedron. In their seminal 1988 article, they prove that, if the path is a geodesic, then this 3-dimensional model is a simplicial complex. The recent proof that this simplicial complex is flag is presented as well as several consequences.
Lundi 14 octobre: Paul Bastide (LaBRI)
Title: A Polynomial upper Bound for Poset Saturation
Abstract: We study a saturation problem on poset. Given a finite poset P, we say that a family F of subsets of [n] is P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The induced saturation number of P, denoted by sat∗(n,P), is the size of the smallest P-saturated family with ground set [n]. The function sat*(n,P) has received interest in the recent years from the extremal combinatorics community, but very few results are known to hold universally for every poset P. In this talk we will discuss a proof that the saturation number for any given poset grows at worst polynomially. More precisely, we show that sat∗(n,P)=O(n^c), where c≤|P| is a constant depending on P only. We obtain this result by bounding the VC-dimension of our family and introducing new arguably natural poset parameters.
Lundi 21 octobre: Frank Ferrari (Bruxelles)
Titre : Random Disks of Constant Curvature, Self-Overlapping Curves and Liouville CFT1
Abstract : An new model of two-dimensional gravity, called Jackiw-Teitelboim quantum gravity, has been extensively studied in recent years, in relation with the quantum theory of near-extremal black holes and holography. The studies in the physics literature have been limited so far to a particular limit of the theory in negative curvature, which is dominated by a so-called Schwarzian mode. The goal of the talk will be to present the theory “from first principles,” without taking the Schwarzian limit. A discretized approach makes the link with new interesting combinatorial problems (counting self-overlapping polygons or equivalently constant curvature metrics on a disk). An alternative direct “continuum” probabilistic approach suggests that tools from the Liouville theory can be adapted and imported to study JT gravity. The equivalence between the two points of view (combinatorial and Liouville-inspired) yields interesting conjectures for the critical exponents of the model.
Lundi 4 novembre: Mireille Bousquet-Mélou (LaBRI)
Titre: Le treillis des montées sur les chemins de Dyck
Résumé: Plusieurs "posets" définis sur les chemins de Dyck de longueur 2n ont été étudiés ces dernières années : treillis de Stanley, de Tamari, de Tamari glouton, treillis des pyramides... L'accent a souvent été mis sur le dénombrement de leurs intervalles, qui a parfois révélé des liens avec des familles de cartes.
Ici nous considérons une variante gloutonne du treillis de Stanley, où les relations de couverture sont obtenues en échangeant un pas descendant avec toute la montée qui le suit. Cet ordre est lié à un treillis plus général introduit récemment par Nadeau et Tewari, et est lui-même un treillis, appelé treillis des montées. Il en va de même pour l'ordre induit sur les m-chemins de Dyck (ceux où toutes les montées sont de hauteur multiple de m). L'ordre induit sur les m-chemins de Dyck miroir (les descentes sont de hauteur multiple de m) n'est plus qu'un semi-treillis supérieur.
L'énumération des intervalles révèle des liens avec le dénombrement des marches confinées dans un quadrant. Leur série génératrice est algébrique pour m=1, mais non D-finie pour m>1, que ce soit pour les m-chemins de Dyck ou leur miroir.
Pour ces derniers intervalles, on établit un lien bijectif avec les classes de congruence des m-fonctions de parking pour la congruence sylvestre, introduite en 2005 par Hivert, Novelli et Thibon.
Attach:2024-11-04-BousquetMelou.pdf
Lundi 18 novembre: Michel Bonnefont (IMB)
titre: Principe de grandes déviations précis pour le nombre de descentes d'une permutation aléatoire (et de son inverse). (travail en commun avec Bernard Bercu, Luis Fredes et Adrien Richou)
résumé: Dans cet exposé on va s'intéresser à la loi du nombre de descentes d'une permutation aléatoire ainsi qu'à celle du couple nombre de descentes et nombre de descentes de la permutation inverse. Certains résultats (loi forte des grands nombres, théorème central limite, principe de grande déviation) sont déjà connus. Comme indiqué par le titre, le but sera d'établir un principe de principe de grandes déviations précis. Ceci sera fait à l'aide d'une étude fine de la transformée de Laplace associée, laquelle est directement reliée aux nombres Eulériens.
Lundi 25 novembre: Thomas Muller (LaBRI)
Titre: Une généralisation des rectangulations en dimension arbitraire
Résumé: Les rectangulations (aussi appelés mosaic floorplans dans la littérature) sont des partitions de rectangles par des rectangles pour lesquels aucun point n'appartient au bord de quatre rectangles. Dans cet exposé, on s'intéressera à une généralisation en dimension d de ces rectangulations, qu'on appelle d-floorplans. En considérant ces objets avec une certaine relation d'équivalence, on verra qu'il est possible de définir leur arbre de génération et que l'étiquetage de ces objets est plus complexe que dans le cas 2d. On présentera ensuite une bijection entre les 2^{d-1}-floorplans et une sous-famille des d-permutations de Baxter introduites par Bonichon et Morel (2022). Cette bijection généralise celle connue entre les rectangulations et les permutations de Baxter. Ceci est un travail en collaboration avec Adrian Tanasa et Nicolas Bonichon.
Lundi 2 décembre: Alicia Castro (LaBRI)
déjeuner d'équipe en salle 76 après l'exposé
Title: Irreducible metric maps from a substitution approach
Abstract: In this talk, I will introduce irreducible metric maps and show how they are related to metric maps without an irreducibility constraint. This connection is established by identifying the appropriate disk function substitution, drawing an analogy with the discrete map case. With this substitution, we compute their moments and generating functions. Notably, we rediscover a relationship between the enumeration of irreducible metric maps and hyperbolic surfaces. This talk is based on work to be published in collaboration with Timothy Budd.
Lundi 9 décembre: Slim Kammoun (Poitiers)
Titre: Questions de positivité pour les motifs de permutations.
Résumé: Certaines suites combinatoires sont les moments de variables aléatoires. Par exemple, le nombre de permutations de taille n est le n-ième moment de la loi exponentielle, les nombres de Bell sont des moments d'une variable de Poisson, et les nombres de Catalan sont les moments de la loi semi-circulaire. En général, il est connu qu'une suite combinatoire est une suite de moments si et seulement si la matrice de Hankel associée est positive. Dans un travail en cours, avec Natasha Blitvic et Einar Steingrímsson, nous montrons que certaines familles de permutations avec des conditions sur les motifs sont des suites de moments.
Lundi 16 décembre: Pierre Bonnet (LaBRI)
titre: classification des marches à bords interactifs à petits pas de genre 0
lien zoom: https://u-bordeaux-fr.zoom.us/j/86324858533