Le séminaire a eu lieu les jeudis 1 octobre 2020, 3 décembre 2020, 4 février 2021, 1 avril 2021 et 3 juin 2021.
1 octobre 2020 (vidéos de la séance)
-
Élise Goujard (Institut de Mathématiques de Bordeaux),
Méandres en genre supérieur,.
Transparents.
Un méandre est la configuration topologique d'une droite et d'une courbe fermée simple dans le plan (la route et la rivière) qui s'intersectent transversalement, qu'on peut voir de façon (quasi) équivalente comme la configuration de deux courbes fermées simples transversales sur la sphère. Ce point de vue permet de définir les méandres de genre g comme les configurations topologiques de deux courbes fermées simples s'intersectant transversalement sur des surfaces compactes de genre g (ces méandres de genre supérieur ont été introduits par Di Francesco-Golinelli-Guitter). On définit également les méandres orientés qui correspondent au cas où les courbes sont orientées et elles s'intersectent toujours dans le même sens (ils n'existent qu'en genre supérieur). Les développements récents sur l'énumération des surfaces à petits carreaux en grand genre, et la correspondance entre surfaces à petits carreaux à un cylindre horizontal et un cylindre vertical avec les méandres, permettent d'énumérer les méandres dans deux cas
- à combinatoire fixée (nombre d'arcs minimaux fixé), énumération des méandres de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini
- énumération des méandres orientés de genre g quand le nombre d'intersections tend vers l'infini, et comportement asymptotique quand g tend vers l'infini.
-
Andrew Elvey-Price (CNRS, Université de Tours),
Counting lattice walks by winding angle,.
Transparents.
We count walks by winding angle around the origin on four different lattices. Our method uses a decomposition of each lattice, which allows us to write functional equations characterising generating functions for these walks. We then exactly solve these equations in terms of Jacobi theta functions, allowing us to extract asymptotic information about the associated counting sequences using methods popularised by Flajolet and Sedgewick. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.
3 décembre 2020 (vidéos de la séance)
-
Marni Mishna (Simon Fraser University),
The Kaleidoscopic Splendor of Lattice Walk Enumeration,.
This talk will examine the rich topic of lattice path enumeration. A very classic object of combinatorics, lattice walks withstand study from a variety of perspectives. Even the simple task of classifying the two dimensional walks restricted to the first quadrant has brought into play a surprising diversity of techniques from algebra to analysis to geometry. We will consider walks under a few different lenses. We will see how lattice walks arise in algebraic combinatorics and group theory, and the impact of classification. We will show that a geometric perspective can offer a visual intuition of the role of weighted steps in enumeration formulas. We will also consider some of the existing recent developments using elliptic curves to unravel where the future may lie.
-
Laurent Viennot (INRIA & IRIF),
A trip through hub labeling in graphs,.
Hub labeling is a simple method for coding distances in a graph. It work surprisingly well in road networks where it offers a very compact representation of travel times between any two points and thus allows very fast computation of shortest paths. We will see a graph property called skeleton dimension that explains such efficiency and that seems to fit with road networks. This method has been shown to work well also on various practical graphs. An intriguing problem in distributed computing resides in building such compact representation for sparse graphs in general. We will see that a family of sparse graphs requires almost quadratic space for any hub labeling. These graphs are connected to the Rusza-Szemerédi function counting induced matchings in dense graphs. We also relate the problem of finding more general distance labels for these graphs to the sum index problem in communication complexity, a second hint that representing distances with sub-quadratic space seems hard even in sparse graphs.
4 février 2021
-
Valentin Ovsienko (Laboratoire de Mathématiques de Reims),
Combinatorial and analytic properties of $q$-deformed real numbers.
I will explain a recent notion of $q$-deformed real numbers, and discuss its various combinatorial and analytic properties. A "$q$-deformed real" is a Laurent series in one variable, $q$, with integer coefficients. The subject is connected to different theories, such as knot invariants, continued fractions, and cluster algebras. I will formulate a challenging conjecture about the convergence of the series arising as $q$-deformed real numbers. (Here we understand $q$ as a complex variable.) The conjecture is proved in particular cases and concrete examples. In the most simple examples of $q$-Fibonacci and $q$-Pell numbers, the explicit formulas for the radius of convergence are very similar to certain formulas of Ramanujan. The talk is based on a joint work with Ludivine Leclere, Sophie Morier-Genoud and Alexander Veselov.
-
Ilse Fischer (Universität Wien),
Bijective proofs of alternating sign matrix theorems.
Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and alternating sign triangles, and their numbers are given by a simple product formula. For about 40 years now, combinatorialists have been trying to construct bijective proofs of these relations. We present the first bijective proof of the enumeration formula for alternating sign matrices and of the fact that alternating sign matrices are equinumerous with descending plane partitions. Our constructions rely on signed sets, sijections and related notions such as a generalization of the Garsia-Milne involution principle. The starting point for these constructions are known “computational” proofs, but the combinatorial point of view led to several drastic modifications. We also provide computer code where all of our constructions have been implemented. This is joint work with Matjaz Konvalinka.
1 avril 2021 (vidéos de la séance)
-
Mathilde Bouvel (CNRS, LORIA),
Limite en graphon des cographes aléatoires.
Transparents.
É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.
-
Stephen Melczer (University of Waterloo),
An Invitation to Analytic Combinatorics in Several Variables.
The field of analytic combinatorics in several variables (ACSV) examines the asymptotic behaviour of multidimensional sequences using analytic properties of their (multivariate) generating functions. In addition to the tools used in the more classical univariate setting, the methods of ACSV rely on advanced results from complex analysis in several variables, topology, and algebraic and differential geometry -- giving the field a reputation for powerful methods which can be difficult for new researchers to get a firm grasp on. This talk aims to "demystify" ACSV by surveying some of its main results, software implementations, and recent applications of the theory. In addition, we show how these multivariate techniques can solve previously open problems on the asymptotic behaviour of univariate sequences and provide a significant new approach to attacking the "connection problem" for the asymptotics of D-finite functions.
3 juin 2021
-
Charlotte Hardouin (Institut de Mathématiques de Toulouse),
Marches dans le quart plan et familles de courbes elliptiques.
La nature algébrique des séries génératrices des marches dans le quart-plan a connu de nombreuses approches: méthode du noyau, analyse des singularités, méthodes analytiques transcendantes, méthodes de guessing, invariants de Tutte et enfin théorie de Galois différentielle. Dans cet exposé, après avoir donné un bref historique sur les propriétés algébriques et différentielles de telles séries, je montrerai comment la théorie de Galois différentielle et la méthode des invariants de Tutte développée par Olivier Bernardi, Mireille Bousquet-Mélou et Kilian Raschel peuvent s'articuler afin d'aboutir à un algorithme qui associe à chaque modèle de marche à poids dans le quart-plan un ensemble de relations algébriques entre les poids garantissant l'existence d'une équation algébrique différentielle pour la série génératrice. Ceci est une collaboration avec Michael Singer (NCSU).
-
Kolja Knauer (Universitat Barcelona),
On sensitivity in Cayley graphs.
Recently, Huang proved the Sensitivity Conjecture, by showing that every set of more than half the vertices of the $d$-dimensional hypercube $Q_d$ induces a subgraph of maximum degree at least $\sqrt{d}$. This is tight by a result of Chung, F\"uredi, Graham, and Seymour. Huang asked whether similar results can be obtained for other highly symmetric graphs. In this lecture we study Huang's question on Cayley graphs of groups.
We show that high symmetry alone does not guarantee similar behavior and present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree $1$ on more than half the vertices. In particular, this refutes a conjecture of Potechin and Tsang, for which first counterexamples were shown recently by Lehner and Verret. The first family consists of dihedrants. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are $d$-regular containing an induced matching on a $\frac{d}{2d-1}$-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret.
On the positive side, we consider Cayley graphs of Coxeter groups, where a lower bound similar to Huang's can be shown. A generalization of the construction of Chung, Füredi, Graham, and Seymour shows that this bound is tight for products of Coxeter groups of type $\mathbf{A_n}$, $\mathbf{I_n}(2k+1)$, most exceptional cases and not far from optimal in general. Then, we show that also induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This yields more classes of Cayley graphs with properties similar to the ones provided by Huang's results. However, in contrast to Coxeter groups these graphs have no large subcubes.
Joint with Ignacio Garcia-Marco.