2020-2021
Lundi 28 juin : Rachel Domagalski
Titre : Pattern Avoidance in Circular Permutations
Résumé : A cyclic permutation is the set of all rotations of a linear permutation. Callan initiated the study of permutation avoidance in cyclic permutations and characterized the avoidance classes for all single permutations of length 4. We continue this work. In particular, we establish a cyclic variant of the Erdős-Szekeres Theorem and derive results about avoidance of multiple patterns of length 4. We also determine generating functions for the cyclic descent statistic on these classes. This is joint work with Jinting Liang, Quinn Minnich, Bruce Sagan, Jamie Schmidt, and Alexander Sietsema.
Lundi 14 juin : Jean-Philippe Labbé (FU Berlin)
Titre :Lineup polytopes and applications in quantum physics
Résumé : From a geometric point of view, Pauli's exclusion principle defines a hypersimplex. This convex polytope describes the compatibility of 1-fermion and N-fermion density matrices, therefore it coincides with the convex hull of the pure N-representable 1-fermion density matrices. By employing ideas from convex analysis and combinatorics, we present a comprehensive solution to the convex relaxation of the 1-body N-representability problem. In particular, we adapt and further develop tools such as symmetric polytopes, sweep polytopes, and Gale order. For both fermions and bosons, generalized exclusion principles are discovered. These exclusion principles are expressed as linear inequalities satisfying a hierarchy. The two families of polytopes resulting from these inequalities are part of the new class of so-called lineup polytopes.
This is joint work with physicists Julia Liebert, Christian Schilling and mathematicians Eva Philippe, Federico Castillo and Arnau Padrol.
Lundi 7 juin : Jana Lepšová
Titre :A numeration system for Fibonacci-like Wang shifts
Résumé : Motivated by the study of Fibonacci-like Wang shifts,
we define a numeration system for ⚠ $\mathbb{Z}$ and ⚠ $\mathbb{Z}^2$
based on the binary alphabet ⚠ $\{0,1\}$.
We introduce a set of 16 Wang tiles
that admits a valid tiling of the plane described by
a deterministic finite automaton
taking as input the representation of a position ⚠ $(m,n)\in\mathbb{Z}^2$ and
outputting a Wang tile.
Lundi 31 mai : Séverin Charbonnier
Titre : Generalised Kontsevich graphs: topological recursion and r-spin intersection numbers.
Résumé : Some models of ribbon graphs can be interpreted as Feynman graphs of matrix models. In this manner, the graphs used by Kontsevich in his proof of Witten's conjecture -- about the generating function of intersection numbers of psi-classes satisfying the KdV hierarchy -- are Feynman graphs of a cubic hermitian matrix model with an external field. Together with Raphaël Belliard, Bertrand Eynard and Elba Garcia-Failde, we studied a combinatorial model, which can be interpreted as a generalisation of Kontsevich's matrix model. We proved that certain generating functions can be computed by topological recursion, a procedure developed by Chekhov, Eynard and Orantin. We then studied the implications of this result in the framework of the conjecture made by Witten in 93 (later proved by Faber, Shadrin and Zvonkine), stating that the generating series of intersection numbers of Witten's class satisfies the r-KdV integrable hierarchy.
I will first describe the combinatorial model and the generating functions we are interested in, as well as some combinatorial identities. Second, I will detail Tutte's equation and the topological recursion statement regarding this model. Last, I will explain the path we followed to show, starting from the combinatorial result, that r-spin intersection numbers can be computed by higher topological recursion.
Lundi 17 mai : Baptiste Louf
Titre :Géométrie des cartes de grand genre
Résumé : Les propriétés géométriques des grandes cartes aléatoires ont fait l’objet de nombreux travaux depuis une vingtaine d’années, particulièrement dans le cas de la sphère (cartes planaires), et plus récemment quand la carte est de genre fixé.
On étudie ici un autre régime, où le genre de la carte croît au même rythme que sa taille, on parle de cartes de grand genre. Ces objets présentent plusieurs propriétés hyperboliques. Je ferai un tour d’horizon des travaux récents et des questions ouvertes.
Lundi 3 mai : Jérémie Bouttier
Titre : Compter les pantalons serrés
Résumé :On appelle «pantalon» une carte planaire à trois faces marquées, vues comme des bords. Dans le cas biparti avec contrôle des degrés des faces, une formule d'énumération particulièrement simple a été obtenue par Eynard via la récurrence topologique, et redémontrée bijectivement par Collet et Fusy.
Un pantalon est dit «serré» si chaque bord est de longueur minimale dans sa classe d'homotopie. Dans un article récemment écrit avec Emmanuel Guitter et Grégory Miermont, nous observons que les pantalons serrés admettent une série génératrice encore plus simple que celle des pantalons quelconques. Bien que notre formule soit équivalente à celle d'Eynard-Collet-Fusy (via une décomposition le long de cycles minimaux séparants dans un pantalon quelconque), elle appelle une preuve bijective directe.
Nous donnons une telle preuve, s'inscrivant dans le cadre de la méthode dite de la «décomposition en tranches» que nous enrichissons de nouveaux objets appelés diangles et triangles géodésiques. La construction se fait naturellement sur le revêtement universel d'un pantalon et emploie plusieurs idées liées à la géométrie métrique et hyperbolique.
Lundi 12 avril 14h-15h : Theodosios Douvropoulos
Titre :Coxeter factorizations with generalized Jucys-Murphy weights and Matrix Tree theorems for reflection groups
Résumé : We prove universal (case-free) formulas for the weighted enumeration of factorizations of Coxeter elements into products of reflections valid in any well-generated reflection group W, in terms of the spectrum of an associated operator, the W-Laplacian. This covers in particular all finite Coxeter groups. The results of this paper include generalizations of the Matrix Tree and Matrix Forest theorems to reflection groups, and cover reduced (shortest length) as well as arbitrary length factorizations. Our formulas are relative to a choice of weighting system that consists of n free scalar parameters and is defined in terms of a tower of parabolic subgroups. To study such systems we introduce (a class of) variants of the Jucys-Murphy elements for every group, from which we define a new notion of `tower equivalence' of virtual characters. A main technical point is to prove the tower equivalence between virtual characters naturally appearing in the problem, and exterior products of the reflection representation of W. Finally we study how this W-Laplacian matrix we introduce can be used in other problems in Coxeter combinatorics. We explain how it defines analogues of trees for W and how it relates them to Coxeter factorizations, we give new numerological identities between the Coxeter number of W and those of its parabolic subgroups, and finally, when W is a Weyl group, we produce a new, explicit formula for the volume of the corresponding root zonotope.
This is a joint work with Guillaume Chapuy
Lundi 22 mars 9h-10h30 : Vincent Delecroix
Titre : Petite école de combinatoire : Récursion géométrique et topologique (4/4)
Résumé : Les surfaces orientables sont classifiées par leur genre et leur nombre de composantes de bords . La récursion topologique est un cadre général pour "compter des objets sur les surfaces" due tu B. Eynard and N. Orantin (2007).
L'exemple principal du cours sera celui des graphes dans les surfaces appelés aussi cartes combinatoires. Par exemple, nous exliquerons comment calculer rapidement le nombre de quadrangulations sur une surface de genre avec faces. Nous discuterons les propriétés analytiques des fonctions génératrices des cartes combinatoires.
A la fin du cours, nous aborderons quelques autres situations pour laquelle la récursion topologique s'applique. page du cours
Lundi 22 mars 9h-10h30 : Vincent Delecroix
Titre : Petite école de combinatoire : Récursion géométrique et topologique (3/4)
Résumé : Les surfaces orientables sont classifiées par leur genre et leur nombre de composantes de bords . La récursion topologique est un cadre général pour "compter des objets sur les surfaces" due tu B. Eynard and N. Orantin (2007).
L'exemple principal du cours sera celui des graphes dans les surfaces appelés aussi cartes combinatoires. Par exemple, nous exliquerons comment calculer rapidement le nombre de quadrangulations sur une surface de genre avec faces. Nous discuterons les propriétés analytiques des fonctions génératrices des cartes combinatoires.
A la fin du cours, nous aborderons quelques autres situations pour laquelle la récursion topologique s'applique. page du cours
Lundi 22 mars 10h45-11h45 : Marc Heinrich
Titre : Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth
Résumé : The Glauber dynamics on the colourings of a graph is a random process which consists in recolouring at each step a random vertex of a graph with a new colour chosen uniformly at random among the colours not already present in its neighbourhood. It is known that when the total number of colours available is at least Δ+2, where Δ is the maximum degree of the graph, this process converges to a uniform distribution on the set of all the colourings. Moreover, a well known conjecture is that the time it takes for the convergence to happen, called the mixing time, is polynomial in the size of the graph. Many weaker variants of this conjecture have been studied in the literature by allowing either more colours, or restricting the graphs to particular classes, or both. This paper follows this line of research by studying the mixing time of the Glauber dynamics on chordal graphs, as well as graphs of bounded treewidth. We show that the mixing time is polynomial in the size of the graph in the two following cases:
- on graphs with bounded treewidth, and at least Δ+2 colours,
- on chordal graphs if the number of colours is at least (1+ε)(Δ+1), for any fixed constant ε.
Lundi 8 mars : Vincent Delecroix
Titre : Petite école de combinatoire : Récursion géométrique et topologique (2/4)
Résumé : Les surfaces orientables sont classifiées par leur genre et leur nombre de composantes de bords . La récursion topologique est un cadre général pour "compter des objets sur les surfaces" due tu B. Eynard and N. Orantin (2007).
L'exemple principal du cours sera celui des graphes dans les surfaces appelés aussi cartes combinatoires. Par exemple, nous exliquerons comment calculer rapidement le nombre de quadrangulations sur une surface de genre avec faces. Nous discuterons les propriétés analytiques des fonctions génératrices des cartes combinatoires.
Lundi 1er mars : Vincent Delecroix
Titre : Petite école de combinatoire : Récursion géométrique et topologique (1/4)
Résumé : Les surfaces orientables sont classifiées par leur genre et leur nombre de composantes de bords . La récursion topologique est un cadre général pour "compter des objets sur les surfaces" due tu B. Eynard and N. Orantin (2007).
L'exemple principal du cours sera celui des graphes dans les surfaces appelés aussi cartes combinatoires. Par exemple, nous exliquerons comment calculer rapidement le nombre de quadrangulations sur une surface de genre avec faces. Nous discuterons les propriétés analytiques des fonctions génératrices des cartes combinatoires.
Lundi 1er mars : Nicolas Bedaride
Titre : Groupes de cohomologies pour pavages du plan par coupe et projections
Résumé : Dans cet exposé on s'intéressera aux pavages du plan obtenus par coupe et projections On étudiera en détails ceux qui possèdent une symétrie locale d'ordre 12. On présentera une méthode pour calculer les groupes de cohomologie associés à l'enveloppe de cette famille de pavages.
Lundi 22 février : Lucia Di Vizio
Titre : Le théorème de Klazar sur les nombres de Bell (2003) est un exemple d'un phénomène général
Résumé : Le titre est aussi le leitmotiv de l'exposé, qui portera sur un travail en collaboration avec A. Bostan et K. Rachel. Les nombres de Bell ⚠ $B_n$ sont définis par l'identité
⚠ $1+ \sum_{n\geq 1}B_n\frac{t^n}{n!}=\exp(\exp t-1).$
En 2003, M. Klazar a prouvé la transcendance différentielle de la série génératrice
⚠ $1+\sum_{n\geq 1}B_nt^n$ des nombres de Bell (et d'autres séries qui lui sont reliées) sur
les corps C({t}) des fonctions localement méromorphes en 0. En utilisant la théorie de Galois aux différences, je vais montrer que le théorème de Klazar est un exemple d'un phénomène général, en deux sens différents : d'une part, beaucoup de séries définies par des "fonctions exponentielles" peuvent être ramenées à des solutions d'équations aux différences, comme la série génératrice des nombres de Bell ; d'autre part, les solutions de ce type d'équations sont toujours soit rationnelles, soit différentiellement transcendantes sur C({t}).
Lundi 8 février : Eric Fusy
Titre : Cartes de genre non fixé et arbres bourgeonnants
Résumé : Les bijections à l'aide d'arbres étiquetés ou arbres bourgeonnants impliquent que la fonction à 2 points R_i(g) des quadrangulations planaires satisfait le système récursif R_i(g)=1+g*R_i(g)*(R_{i-1}(g)+R_i(g)+R_{i+1}(g)), et en particulier R_1(g) est la série génératrice des quadrangulations planaires (enracinées), ou dualement des cartes tétravalentes planaires. Par ailleurs la méthode des polynômes orthogonaux permet de montrer que la série génératrice des cartes tétravalentes de genre non fixé est la première composante r_1(g) de la séquence r_i(g) de séries formelles satisfaisant le système récursif r_i(g)=i+g*r_i(g)*(r_{i-1}(g)+r_i(g)+r_{i+1}(g)). Nous en donnerons une interprétation bijective à l'aide d'arbres bourgeonnants, qui explique aussi la grande ressemblance avec la récurrence pour les R_i(g). Une extension de la construction donne également une interprétation des r_i(g) comme comptant certaines cartes avec marquages multiples. Cette interprétation permet ensuite d'établir une equi-énumération (dont une preuve bijective reste à trouver) entre les cartes avec poids N par face (permettant un contrôle sur le genre) et certaines cartes avec marquages multiples.
Travail en commun avec Emmanuel Guitter
Lundi 25 janvier : Mathilde Bouvel
Titre : Limite en graphon des cographes aléatoires
Résumé : Étant donnée une famille de graphes, une question naturelle (qui constitue un pan de la littérature en graphes aléatoires) est de décrire la forme limite d'un graphe pris uniformément au hasard dans cette famille. On étudiera cette question pour la famille des cographes, et on décrira leur limite (appelée le "cographon Brownien") dans le formalisme des graphons. Dans l'exposé, je ne supposerai aucune connaissance préalable des cographes ni des graphons. J'en présenterai d'abord les définitions et quelques propriétés clés, notamment le codage des cographes par des "cotrees". Je décrirai les étapes principales de la preuve de la limite en graphon dans le cas des cographes étiquetés. Cette preuve utilise surtout de la combinatoire analytique sur les "cotrees". Si le temps le permet, je mentionnerai plusieurs résultats associés, notamment la limite en graphon des cographes non-étiquetés, et des résultats parallèles dans le monde des permutations qui suggèrent une universalité du cographon Brownien.
Travail en commun avec F. Bassino, V. Feray, L. Gerin, M. Maazoun, A. Pierrot.
Lundi 4 janvier : Wenjie Fang
Titre : Bijective link between Chapoton's new intervals and bipartite planar maps
Résumé : In 2006, Chapoton defined a class of Tamari intervals called "new intervals" in his enumeration of Tamari intervals, and he found that these new intervals are equi-enumerated with bipartite planar maps. We present here a direct bijection between these two classes of objects using a new object called "degree tree". Our bijection also gives an intuitive proof of an unpublished equi-distribution result of some statistics on new intervals given by Chapoton and Fusy.
Lundi 30 novembre : Valentin Feray
Titre : Graphes de dépendance (pondérés) et normalité asymptotique
Résumé : Le but de cet exposé est de présenter la théorie des graphes de dépendance et une extension pondérée que j'ai récemment introduite. Cette théorie donne un critère de normalité asymptotique pour des sommes de variables aléatoires faiblement dépendantes. Elle s'applique en particulier aux nombres de sous-structures de taille fixée dans des objets combinatoires aléatoires ; l'exposé sera illustré par des résultats sur les occurrences de motifs dans des permutations aléatoires d'une part, et dans des partitions d'ensemble d'autre part.
Lundi 16 novembre : PEC : Sébastien Labbé
Titre : Pavages apériodiques en dimension 1: de la combinatoire à la géométrie en passant par l'algèbre (2e partie)
Résumé : La structure des pavages apériodiques sont souvent expliquées par des règles combinatoires faisant intervenir la géométrie et l'algèbre. Dans cette petite école de combinatoire, nous allons présenter ces liens en se basant sur un exemple en dimension 1 associé au nombre irrationel le plus simple de toute la terre. À partir de la substitution de Fibonacci, nous allons construire la substitution géométrique associée. Cela permettra de définir un pavage apériodique de la droite réelle. Nous observerons que ce pavage s'explique via le schéma de coupe et projection et la conjugaison algébrique dans le plongement de Minkowski de Z[sqrt(5)].
Dans la 2e partie, nous commencerons en définissant le schéma de coupe et projection. Ensuite, nous déclinerons cette définition sur les exemples vus lors du premier exposé. Si le temps le permet, nous ferons le lien avec la description des pavages apériodiques de Jeandel-Rao par le schéma de coupe et projection.
Lundi 2 novembre : Reza Mohammadpour
Titre : Zero temperature limits of equilibrium states for subadditive potentials
Résumé : In this talk we discuss ergodic optimization problems for subadditive sequences of functions on a topological dynamical system. We show that for ⚠ $t \rightarrow \infty$ any accumulation point of a family of equilibrium states is a maximizing measure. We also show that the Lyapunov exponent and entropy of equilibrium states converges in the limit ⚠ $t \rightarrow \infty$ to the maximum Lyapunov exponent and entropy of maximizing measures.
Lundi 19 octobre : PEC : Sébastien Labbé
Titre : Pavages apériodiques en dimension 1: de la combinatoire à la géométrie en passant par l'algèbre
Résumé : La structure des pavages apériodiques est souvent expliquée par des règles combinatoires faisant intervenir la géométrie et l'algèbre. Dans cette petite école de combinatoire, nous allons présenter ces liens en se basant sur un exemple en dimension 1 associé au nombre irrationnel le plus simple de toute la terre. À partir de la substitution de Fibonacci, nous allons construire la substitution géométrique associée. Cela permettra de définir un pavage apériodique de la droite réelle. Nous observerons que ce pavage s'explique via le schéma de coupe et projection et la conjugaison algébrique dans le plongement de Minkowski de Z[sqrt(5)].
Lundi 12 octobre : Vincent Delecroix
Titre : Les courbes simples en grand genre ne séparent pas
Résumé : Fixons une surface compacte S de genre g >= 2. On s'intéresse dans cette surface aux courbes fermées simples à homotopie près ou autrement dit aux plongements du cercle dans la surface sans auto-intersection. Il y a un nombre infini dénombrable de telles courbes. A chaque courbe on associe son type topologique: lorsqu'on la découpe, soit elle sépare la surface en deux sous-surfaces de genre g1 et g2 avec g1 + g2 = g soit elle est non-séparante. En particulier, il y a un nombre fini de types topologiques. Nous expliquerons comment donner sens à la notion de courbe aléatoire dans S et associer une fréquence d'apparition à chaque type topologique. J'expliquerai alors pourquoi lorsque le genre tend vers l'infini, le type topologique d'une courbe aléatoire est non-séparant.
Lundi 21 septembre : Sergey Dovgal
Titre : The birth of the strong components
Résumé :It is known that random directed graphs D(n,p) undergo a phase transition around the point p = 1/n. Moreover, the width n^{-4/3} of the transition window has been known since the works of Luczak and Seierstad. In particular, they have established that as n → ∞ when p = (1 + μn^{-1/3})/n, the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from 1 to 0 as μ goes from −∞ to ∞. By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of μ and provide more statistical insights into the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs. Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle-point method which can be systemat- ically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter p, we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not. Our theoretical predictions are supported by numerical simulations when the number of vertices is finite, and we provide tables of numerical values for the integrals of Airy functions that appear in this study.
This is a joint work with Élie de Panafieu, Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, and Stephan Wagner
Arnaud Casteigts
Titre : Efficient generation of simple temporal graphs up to isomorphism
Résumé : In this work, we consider a particular kind of isomorphism between temporal graphs, where two graphs are isomorphic if and only if they have the same reachability (set of temporal paths) up to time distortion. The underlying motivation is to capture infinite sets of temporal graphs by finitely many representatives, on which conjectures can be tested in a comprehensive manner. In this talk, I will focus on the case of "simple temporal graphs", where the edges have exactly one presence time and times are different for adjacent edges. The automorphisms of these graphs have special features which allow one to generate canonical representatives efficiently. The talk will be structured as a gentle discussion covering several topics, from symmetry, to spanners, to generation trees, and a few conjectures.