---

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

présentation au format pdf

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.


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.


Lundi 7 octobre: Lionel Pournin (LIPN, Paris)
titre: 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

Résumé: 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.


Français English

Groupe

Événements

GT CI

* Années précédentes

Ressources

edit SideBar