2022-2023
Lundi 26 juin : Benjamin Hellouin
Titre : Mixing in Hom shifts / Path reconfiguration in graphs
Résumé : Hom shifts are a family of simple two-dimensional subshifts (rules for colourings of the grid Z^2) that look the same in every direction, i.e. invariant by rotation and symmetry. This restriction breaks classical methods for embedding computation in subshifts, and problems that are undecidable in general seem to become tractable, and can usually be restated in terms of graphs.
This talk is about gluing distance in Hom shifts: given two n x n admissible partial colourings, how far do they need to be so that we can glue them together in a larger colouring ? It turns out that the problem can be restated in terms of homomorphism reconfiguration in graph theory, and the proofs rely on some kind of path transformations in graphs that can be intuitively seen as homotopies, making a link with algebraic topology in graphs.
On every simple example, this distance is constant or linear; however, we produce a more elaborate example with logarithmic gluing distance. We conjecture that constant, linear and logarithmic distances are the only three possible behaviours, and that this makes an argument for these behaviours to be "combinatorially natural" for general subshifts (in the absence of computation).
This is a joint work with Silvère Gangloff and Piotr Opocha.
Lundi 19 juin : Thomas Budzinski
Titre : Le problème du plus grand sous-arbre commun pour les arbres aléatoires
Résumé : On considère deux arbres binaires dont les feuilles sont étiquetées de 1 à n. Quelle est la taille du plus grand ensemble d’étiquettes telle que la généalogie de ces étiquettes est la même dans les deux arbres ? Dans le cas où les deux arbres sont aléatoires uniformes et indépendants, un argument brutal montre que cette taille est au plus en racine carrée de n. On montre que cette borne n’est en fait pas optimale. De manière peut-être un peu surprenante, le problème est relié à l’étude de la régularité des homéomorphismes entre deux arbres Browniens indépendants. Travail en cours avec Delphin Sénizergues.
Lundi 12 juin : Dimitrios Mitsios (IPHT, Saclay)
Titre : A new formula for intersection numbers
Résumé : The main goal of this talk is to present a new formula that computes Kontsevich-Witten intersection numbers and its application in proving the ELO conjecture. We will begin by introducing Kontsevich-Witten intersection numbers and their connection to the KdV equation. Then, the notion of determinantal formulas and the role of the Airy function will be discussed. Following this, we will present the new formula along with its proof and properties. It involves summations over partitions of products of factorials and Kostka numbers (numbers of semi-standard tableaux of given shape and weight) with bounded weights. Finally, the application of this formula in proving the ELO conjecture will be presented. The conjecture, now a theorem, states that the generating polynomials of the intersection numbers expressed in the basis of elementary symmetric polynomials have an unexpected vanishing of their coefficients.
This is joint work with Bertrand Eynard.
Lundi 5 juin :
Lundi 22 mai : Niloufar Fuladi
Titre : Universal families of arcs and curves on surfaces
Résumé : In this talk I introduce a family of curves that realize all pants decomposition of a surface: a family of simple closed curves Γ on a surface realizes all types of pants decompositions if for any pants decomposition of the surface, there exists a homeomorphism sending it to a subset of the curves in Γ. The study of such universal families of curves is motivated by questions on graph embeddings, joint crossing numbers and finding an elusive center of moduli space. I will discuss the case of surfaces without punctures, where we establish an exponential upper bound and a superlinear lower bound on the minimum size of the family of curves with this universal property. I also talk about a similar concept of universality for triangulations of polygons, where we provide bounds which are tight up to logarithmic factors. In this talk, I will explain the background and context and no prior knowledge in topology or surfaces is needed. This is joint work with Arnaud de Mesmay and Hugo Parlier.
Lundi 15 mai : Adrian Tanasa
Titre : On 0-dimensional quantum field theory (aka combinatorial quantum field theory) and random matrix models
Résumé : In this expository talk, I will first show a glimpse on quantum field theory (QFT) and the combinatorics used to write down its mathematical formalism. I will then have a closer look at the simplest type of QFT, namely 0-dimensional scalar QFT (aka combinatorial QFT). In the last part of the talk, I will exhibit how these ideas generalize to the case of random matrix models (seen as 0-dimensional QFT models), models which are known to successfully describe 2-dimension quantum gravity, but also to give an original approach to combinatorial map counting.
Lundi 24 avril : Florent Koechlin
Titre : Two criteria to prove the inherent ambiguity of bounded context-free languages
Résumé : A context-free language is inherently ambiguous if any grammar recognizing it is ambiguous, i.e. there is a word that is generated in two different ways. Deciding the inherent ambiguity of a context-free language is a difficult problem, undecidable in general. The first examples of inherently ambiguous languages were discovered in the 1960s, using iteration techniques on derivation trees. They belonged to a particular subfamily of context-free languages, called bounded context-free languages.
Although they made it possible to prove the inherent ambiguity of several languages, as for example the language L = a^n b^m c^p with n=m or m=p, iteration techniques are still very laborious to implement, are very specific to the studied language, and seem even sometimes unadapted. For instance, the relative simplicity of the proof of inherent ambiguity of L completely collapses by replacing the constraint "n=m or m=p" by "n≠m or m≠p".
In this talk, I will present two useful criteria based on generating series to prove easily the inherent ambiguity of many bounded context-free languages, extending on a recent criterion developed by Makarov in 2021. These languages, which have a rational generating series, resisted both the classical iteration techniques developed in the 1960’s and the analytic methods introduced by Philippe Flajolet in 1987.
Lundi 27 mars : Baptiste Louf
Titre : Quelques questions autour des cartes de grand genre
Résumé : Une carte combinatoire est une surface discrète formée par recollements de polygones. Dans cet exposé, j’évoquerai l’étude de ces cartes quand le genre de la surface sous-jacente devient grand. Je présenterai quelques résultats existants et les questions qui restent ouvertes. On parlera de bijections, d’énumération (asymptotique ou pas), de probas et d’autres modèles de géométrie des surfaces.
Lundi 20 mars : Daria Pchelina
Titre : Densité des empilements de sphères : des pièces de monnaie aux oranges
Résumé : Comment empiler un nombre infini d'oranges pour maximiser la proportion de l'espace couvert ? Kepler a conjecturé que l'empilement des "balles de canon" est optimal. 400 ans se sont écoulés avant que cette conjecture soit démontrée par Hales et Ferguson dont la preuve comporte 6 papiers et plus de 50000 lignes de code. Comment arranger un nombre infini de pièces de monnaie de 3 rayons différents sur une table infinie pour maximiser la proportion de la surface couverte ? Un arrangement de disques est dit triangulé si chacun de ses "trous" est borné par trois disques tangents. Connelly a conjecturé que si de tels arrangements existent, l'un d'eux maximise la proportion de la surface couverte. Nous avons démontré cette assertion pour 31 triplets de rayons de disques et l'avons réfuté pour 40 autres triplets. Je vais vous présenter nos résultats sur les arrangements triangulés à 3 disques et les analogies entre notre preuve et celle de la conjecture de Kepler.
Lundi 6 mars : Mireille Bousquet-Mélou
Titre : Intervalles de Tamari gloutons
Résumé : En 2006, F. Chapoton a établi que le nombre d'intervalles dans un certain poset défini sur les chemins de Dyck de longueur 2n, appelé treillis de Tamari, était aussi le nombre de triangulations de taille n. Ce phénomène a ensuite été expliqué bijectivement par Bernardi et Bonichon. Plus tard, le dénombrement de ces intervalles a été généralisé à une famille de treillis dits de m-Tamari (ici, m désigne un entier), par É. Fusy et L.-F. Préville-Ratelle et l'oratrice. Pour un m général, les nombres restent très simples, mais ne sont pas connus pour compter des cartes. Nous montrerons en revanche, que si on considère un ordre de m-Tamari ``glouton'', alors le nombre d'intervalles est bien le nombre de certaines cartes, connues sous le nom de (m+1)-constellations. Notre preuve est récursive, et procède par équations fonctionnelles. Une preuve bijective reste à construire.
Il s'agit d'un travail en commun avec Frédéric Chapoton (Strasbourg).'
Lundi 27 février : Loïc Foissy
Titre : Equations de groupe de renormalisation de tout ordre
Résumé : En théorie des champs quantiques, l'équation de groupe de renormalisation est vérifiée par les fonctions de Green. Cette équation est relevée au niveau de l'algèbre de Hopf des arbres de Connes-Kreimer, où elle s'interprète comme une évolution linéaire de certains coefficients attachés à une série en les arbres enracinés, généralement obtenue à l'aide d'une équation de Dyson-Schwinger combinatoire dans le cadre de la théorie des champs quantiques.
D'autres séries en les arbres enracinés sont intéressantes, par exemple la série de Connes-Moscovici, ou d'autres plus exotiques. Nous étendons la notion d'équation de groupe de renormalisation à ces séries. Nous caractérisons les séries qui vérifient une équation de groupe de renormalisation d'ordre fixé pour toute règle de Feynman et donnons quelques éléments sur les séries qui vérifient une telle équation pour une règle de Feynman bien choisie.
Cet exposé est issu d'un article écrit en collaboration avec William Dugan et Karen Yeats.
Lundi 20 février : Vincent Delecroix
Titre : Permutations aléatoires et multicourbes aléatoires
Résumé : Nos nous intéressons aux familles de courbes disjointes sur une surface. Lorsque le genre de la surface sous-jacente tend vers l'infini ces dernières se comportent (plus ou moins) "comme" la décomposition en cycles d'une permutation aléatoire.
Travail en commun avec E. Goujard, A. Zorich et P. Zograf d'une part et M. Liu d'autre part.
Lundi 23 janvier : Philippe Duchon
Titre : Complexité des automates non-déterministes aléatoires
Résumé : (Travail en commun avec Arnaud Carayol, Florent Koechlin et Cyril Nicaud)
Les automates finis sont un modèle bien connu de programmes ne disposant que d'une mémoire finie. Si l'on ignore les questions de lettres, de mots reconnus et de langages, un automate déterministe complet ressemble très fort à un graphe orienté où chaque sommet a un degré sortant constant (et possiblement des arcs multiples). On sait beaucoup de choses sur ces graphes k-sortants aléatoires uniformes: existence d'une grosse composante fortement connexe "puits", ainsi que de nombreux résultats sur les distances à l'intérieur comme à l'extérieur de cette composante.
Dans le monde des automates, on peut également définir des automates non déterministes, dans lesquels un même état peut avoir plus d'une transition étiquetée par la même lettre; en particulier il est classique que leur pouvoir d'expression est le même que celui des automates déterministes, et il existe des algorithmes bien connus de déterminisation - partant d'un automate non déterministe, on calcule un automate déterministe qui accepte le même langage. Il est également bien connu que la taille de l'automate déterminisé est, dans le pire cas, exponentielle en la taille de l'automate de départ.
Dans ce travail, nous cherchons à savoir si ce comportement d'explosion de la taille est rare ou non. Il est difficile de choisir un modèle pertinent d'automates non déterministes aléatoires, aussi nous choisissons un modèle minimalement non-déterministe: partant d'un automate déterministe aléatoire, nous lui ajoutons une transition aléatoire.
Notre résultat principal est que, sous ce modèle, la taille moyenne de l'automate déterminisé est superpolynomiale. Plus précisément, pour tout degré d, la probabilité que l'automate déterminisé ait une taille supérieure à ⚠ $n^d$ reste loin de 0. Notre analyse repose sur une analyse de la structure un peu fine de l'algorithme, et la détection de structures raisonnablement probables dans les automates aléatoires.
Lundi 16 janvier : Ivan Yakovlev
Titre :Spectre de longueurs des graphes sur le tore
Résumé : Soit G un graphe aux arêtes pondérées, plongé (de manière cellulaire) dans une surface topologique S. Le spectre marqué de longueurs de G est la fonction qui sur une classe d'homotopie libre de S vaut la longueur d'un cycle le plus court de G qui est dans cette classe d'homotopie. Le spectre non-marqué est une liste croissante de toutes les valeurs du spectre marqué.
Je vais présenter des algorithmes pour calculer les spectres de longueur dans le cas ou S est le tore (surface de genre 1). Plus précisément, pour un graphe de complexité n, le prétraitement en temps O(n^2 log log n) permet de calculer : pour un cycle à k arêtes, la longueur minimale d'un cycle homotope en O(k + log n); les k premières valeurs du spectre non-marqué en O(k * log n). Je vais aussi présenter des algorithmes pour tester l'égalité des spectres de deux graphes différents.
Lundi 9 janvier : Jean-François Marckert
Titre :Chaînes de Markov avec noyaux presque triangulaires sur N
Résumé : Les processus de naissances et morts sont des chaînes de Markov, à valeurs dans N, dont les incréments valent +1, - 1 ou 0. Leur matrice de transition sont dites "tridiagonales".
Dans une série de travaux des années 50, Karlin et McGregor donnent des CNS pour leur récurrence et récurrence positive. Ils calculent également leur mesure invariante (qui existe toujours et est unique pour tout noyau irréductible).
Dans ce travail, nous nous intéressons au modèle nettement plus général des chaînes sur N dont les noyaux sont dits presque triangulaires: -- presque triangulaires supérieures PTS: les incréments valent au moins -1 -- presque triangulaires inférieures PTI: les incréments valent au plus +1
Les tri-diagonales sont donc à l'intersection de ces 2 familles.
Pour ces 2 familles, on donne des CNS de récurrence, et récurrences positives. On calcule les mesures invariantes quand il y en a... et on observe que les PTS et les PTI sont très différentes.
Les méthodes sont principalement de nature combinatoire, et sont différentes de celles de Karlin et McGregor.
Travail commun avec Luis Fredes, IMB, Bordeaux
Lundi 12 décembre : Zoé Varin
Titre : Un système de particules : le modèle de golf sur ⚠ $\znz$ et sur ⚠ $\Z$.
Résumé : On considère un modèle de golf aléatoire, ou parking aléatoire, sur un graphe fini connexe. On assigne des balles et des trous à chaque sommet (aléatoirement ou non), puis les balles sont activées une par une, chacune réalisant une marche aléatoire jusqu'au premier trou libre qu'elle trouve. Sur les cycles (⚠ $\Z/n\Z$), on caractérise la loi des trous résiduels dans le cas où on tire uniformément une configuration avec des nombres de balles et de trous fixés. On peut alors étendre la définition du modèle à un graphe infini, ⚠ $\Z$, et on explicite également la loi des trous résiduels dans ce cas.
Lundi 5 décembre : Carole Porrier
Titre :Aperiodic tilesets derived from cut and project tilings
Résumé : Ammann bars are formed by segments (decorations) on the tiles of a tiling such that forming straight lines with them while tiling forces non-periodicity. Only a few cases are known, starting with Robert Ammann's observations on Penrose tiles, but there is no general explanation or construction. We propose a general method for cut and project tilings based on the notion of subperiods and we illustrate it with an aperiodic set of 36 decorated prototiles corresponding to what we called Cyrenaic tilings. We also explore how to get aperiodic Wang tilesets from cut and project tilings with local rules. To illustrate this, we construct an aperiodic Wang tileset from a decomposition of golden octagonal tilings.
La première partie de l'exposé est basé sur https://arxiv.org/abs/2205.13973
Lundi 28 novembre : Olivier Carton
Titre :Discrepancy and nested perfect necklaces
Résumé : M. B. Levin constructed a real number x such that the first N terms of the
sequence b^n x mod 1 for n >= 1 have discrepancy ⚠ $O((log N)^2/N)$. This is
the lowest discrepancy known for this kind of sequences. In this talk, we
present Levin's construction in terms of nested perfect necklaces, which
are a variant of the classical de Bruijn sequences. For base 2 and the
order being a power of 2, we give the exact number of nested perfect
necklaces and an explicit method based on matrices to construct each of
them.
Transparents Enregistrement image
Lundi 21 novembre : Bastián Espinoza
Titre :An S-adic characterization of sublinear complexity subshifts
Résumé : In the context of symbolic dynamics, the class of "sublinear complexity subshifts" is of particular relevance as it occurs in a variety of areas, such as geometric dynamical systems, language theory, number theory, and numeration systems, among others. During the intensive study carried on this subject from the beginning the 90's, it was proposed that a hierarchical decomposition based on S-adic sequences that characterizes sublinear complexity subshifts would be useful to understand this class. The problem of finding such a characterization was given the name "S-adic conjecture" and inspired several influential results in symbolic dynamics. In this talk, I will present an S-adic characterization of sublinear complexity subshifts and some of its applications, which in particular give a solution to this conjecture.
Lundi 14 novembre : Doriann Albertin
Titre : The canonical complex of the weak order
Résumé :The canonical join complex of a join-semidistributive lattice L is a simplicial complex whose faces are in bijection with the elements of L and record the canonical join representations in L. We introduce the canonical complex of a semidistributive lattice L, another simplicial complex containing both the canonical join and meet complexes, and whose faces are in bijection with intervals of L. Like the canonical join complex, the canonical complex is flag, and behaves well with quotients of L. In 2015, N. Reading introduced the non-crossing complex, a combinatorial model for the canonical join complex of the right weak order on permutations. Its faces are described with non-crossing arc diagrams. We focus in this talk on the example of the weak order, and extend this combinatorial model to a description of the canonical complex of the weak order, the semi-crossing complex, and its faces, the semi-crossing arc bidiagrams. This allows us to compute a generalization of the Kreweras complement on non-crossing partitions to all quotients of the weak order.
Lundi 7 novembre 9h30 : Pierre Bonnet
Titre :Algébricité de modèles de marche à grands pas dans le quart de plan
Résumé : Depuis une vingtaine d'année, différents modèles de marches confinées dans un cône du plan sont étudiés. Notamment, la classification complète de la nature des séries génératrices pour les modèles à petits pas dans le quart de plan a été achevée. Dans ce cadre d'étude, on fournit dans cet exposé une preuve de l'algébricité des séries de deux modèles à grands pas, jusqu'alors conjectures algébriques, en introduisant de nouveaux outils issus de la théorie de Galois.
Lundi 7 novembre 10h45 : Mélodie Andrieu
Titre :Complexities of hypercubic billiard words
Résumé : [Based on a joint work with Léo Vivion.]
Sturmian words (1940) form a class of infinite words over the binary alphabet which sheds light, through their various equivalent definitions, on the remarkable interactions between combinatorics, dynamical systems and number theory.
On larger alphabets, these definitions give birth to different classes of words (e.g.: Arnoux- Rauzy or episturmian words, words associated with d−dimensional continued fraction algorithms, polygonal or cubic billiard words, etc.) A large program, initiated by G. Rauzy (∼1980), is to determine whether some of these classes of words coincide, and which characteristic properties of Sturmian words they still satisfy.
In this talk, we will focus on a combinatorial quantity which characterizes Sturmian words, called abelian complexity, and compute it for words generated by a billiard in a cube of dimension d.
Lundi 10 octobre : Hugo Mlodecki
Titre :Un automorphisme bidendriforme de WQSym
Résumé : Grâce aux travaux de Foissy, on sait que l'algèbre de Hopf WQSym est isomorphe à sa duale car bidendriforme. Dans cet exposé nous montrons comment construire un isomorphisme bidendriforme combinatoire explicite. Pour ceci nous représentons deux décompositions récursives des mots tassés par deux nouvelles familles combinatoires appelées forêts biplanes rouge et bleue. On obtient alors deux bases de WQSym et sa duale. L'intérêt de ces bases est qu'en prenant des sous-ensembles explicites, on obtient des bases d'éléments primitifs et totalement primitifs. Nous combinons soigneusement les forêts rouges et bleues pour obtenir des forêts bicolores. Une simple recoloration des arêtes nous permet d'obtenir le premier automorphisme bidendriforme explicite de WQSym.
Lundi 19 septembre : Sébastien Labbé
Titre : Paires asymptotiques indistinguables et configurations sturmiennes multidimensionelles
Résumé : Two asymptotic configurations on a full ⚠ $\mathbb{Z}^d$-shift are indistinguishable if for every finite pattern the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of ⚠ $\mathbb{Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a ``flip condition'' are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together the two results provide a generalization to ⚠ $\mathbb{Z}^d$ of the characterization of Sturmian sequences by their factor complexity ⚠ $n+1$. Many open questions are raised by the current work which was made in collaboration with Sebastián Barbieri (https://arxiv.org/abs/2204.06413).