Seminars

On considère un modèle d'épidémie SIR (Susceptible-Infected-Removed) démarré avec un individu infecté dans une population contenant un grand nombre $n$ d'individus sains. Chaque individu guérit à taux $1$ et infecte chaque individu sain à taux $\lambda_n$. On encode tous les événements d'infection ayant eu lieu au cours de l'épidémie dans un arbre T_n. On s'intéresse à la hauteur de cet "arbre des infections" T_n, en particulier dans le régime $\lambda_n = \lambda / n$ pour $\lambda$ une constante plus grande que $1$, qui demande une analyse particulière. La hauteur asymptotique de l'arbre dans ce régime fait apparaître une transition de phase en $\lambda$ autour d'une valeur $\lambda_c\approx 1.80$. J'expliquerai les grandes étapes de la preuve et présenterai quelques outils qui permettent d'analyser le modèle: un lien avec les arbres récursifs gelés, ainsi que le contrôle précis du profil de ces arbres grâce à une famille de martingales.

Une triangulation d'un ensemble de points dans le plan euclidien est dite de Delaunay si chaque cercle circonscrit à un triangle ne contient aucun autre sommet de la triangulation. Son extension à des surfaces, ainsi que certains algorithmes permettant de la calculer, se heurte à des difficultés topologiques (genre de la surface) et géométriques (systole de la surface). Cet exposé introduira la notion de triangulation de Delaunay, et présentera des méthodes de calcul permettant de la calculer comme l'algorithme de flip ou de Bowyer-Watson. Nous nous focaliserons ensuite sur ce-dernier, en l'étendant d'abord au tore, puis aux surfaces hyperboliques, en passant par la surface de Bolza. Aucun prérequis en géométrie hyperbolique, topologie ou algorithmique n'est nécessaire pour suivre l'exposé. Title : Bowyer-Watson algorithm, from the euclidean plane to hyperbolic surfaces. A triangulation of a set of points in the Euclidean plane is called a Delaunay triangulation if the circumcircle of each triangle does not contain any other vertex of the triangulation. Its extension to surfaces, as well as certain algorithms for computing it, encounters topological difficulties (genus of the surface) and geometric difficulties (systole of the surface). This talk will introduce the concept of Delaunay triangulation and present key computational methods, including the flip algorithm and Bowyer-Watson algorithm. We will then focus specifically on the Bowyer-Watson algorithm, extending it first to the torus, then to hyperbolic surfaces, with particular attention to the Bolza surface. The presentation requires no prior knowledge of hyperbolic geometry, topology, or algorithmics.

Dans cet exposé, je parlerai des méthodes récentes développées par A. Elveis-Price, W. Fang, B. Louf et M. Walner pour déterminer les comportements asymptotiques des solutions de récurrences bivariées. Ces méthodes se basent sur une approche d'abord heuristique qui permet de déterminer la forme de l'asymptotique, puis dans un second temps on utilise des arguments issus des marches aléatoires dans le quart de plan pour obtenir des équivalents. On verra comment ces méthodes peuvent s'appliquer au cas des nombres de Hurwitz monotones, que l'on a étudié avec B. Louf et si le temps le permet, aux généralisations possibles.

Framing lattices were introduced very recently in [von Bell--Ceballos, 2025] and [Berggren--Serhiyenko, 2024] as a wide family of lattices containing many generalizations of the Tamari lattice and the weak order. They are associated to a directed acyclic graph, together with a framing, a choice of total orders on incoming and outgoing edges at each vertex. Such a choice of framing enables to decide whether two routes (maximal paths) are crossing. Framing lattices were then defined as an order on maximal collections of non crossing routes. In an ongoing work with Jonah Berggren, we introduce cornered cliques as a new combinatorial model for the elements of a framing lattice, with explicit bijections with maximal cliques. These enable us to provide cubical coordinates for all framing lattices, for which covering relations change only one coordinate, and comparison in the lattice corresponds to componentwise comparison. These specialize to the well-known bracket vectors for the Tamari lattice, and to an enhanced version of the Lehmer code for the weak order.

Low-discrepancy sequences are the best discrete approximations of the continuous uniform distribution. Two of the most classical constructions are the van der Corput sequence and the family of Kronecker sequences. Apart from their uniformity, their construction methods lead to very nice mathematical properties. In this talk, I will present some ways to use their regularity, first to tackle an old problem of Erdos and de Bruijn (1949) on lengths of consecutive segments, and then to obtain embeddings in translation surfaces.

On peut facilement plier une feuille de papier rectangulaire, afin de réaliser un cylindre droit : il suffit de plier la feuille en trois de manière à obtenir un prisme à section triangulaire. Mais qu'en est-il si l'on veut recoller les bords triangulaires de ce prisme pour réaliser un tore plat ? Nous verrons dans cet exposé que cela est toujours possible, ce quel que soit les polygones papiers de départ considérés, et les instructions de recollement choisis. Nous étudierons également la question suivante : est-il possible de réaliser tous les tores plats avec une combinatoire fixée ? Enfin, si le temps le permet, nous évoquerons la généralisation de ces questions à des surfaces polyédrales de genre 2, dites de translation.

Cette présentation plonge, en particulier, dans l'article https://arxiv.org/abs/2510.03177 avec Georg Loho et Arnau Padrol. Nous commencerons par une (longue) introduction aux déformations de polytopes. Un permutoèdre déformé (aussi appelé permutoèdre généralisé, ou fonction sous-modulaire) est un polytope dont toutes les arêtes ont pour direction $e_i - e_j$ pour certains $i \neq j$. L'ensemble des permutoèdres déformés vivant dans $\mathbb R^n$ forme un cône, le cône sous-modulaire. Nous proposons une construction "inductive" du cône sous-modulaire, en utilisant une opération nommée GP-sum : à partir de deux permutoèdres déformés dans $\mathbb R^n$, nous créons (bijectivement) un permutoèdre déformé dans $\mathbb R^{n+1}$. Munis de cette construction, nous créons de nouveaux rayons du cône sous-modulaire, c'est-à-dire de nouveaux permutoèdres déformés indécomposables (au sens de la somme de Minkowski). Cela nous permet d'améliorer les bornes connues sur le nombre de rayons du cône sous-modulaire, notamment en produisant $2^{2^n}$ rayons. Plus encore, nous étudions le f-vecteur du cône sous-modulaire, son nombre total de faces, et le nombre de ses faces simplicial, grâce à la nouvelle partition que cette construction inductive nous donne.

Même si trier une permutation aléatoire requiert n log(n) comparaisons en moyenne, il existe de nombreux cas d'usage où les tableaux que l'on souhaite trier ne sont pas des permutations aléatoires : soit ils contiennent de longues plages contiguës déjà triées, soit ils contiennent peu de valeurs distinctes. L'algorithme TimSort, utilisé en Java pour trier des tableaux d'objets composites, a été conçu spécifiquement pour être plus efficace sur de tels tableaux pré-triés. Nous découvrirons comment cet algorithme et ses variantes fonctionnent et pourquoi ils sont efficaces.

Geometric hitting set problems, in which we seek a smallest set of points that collectively hit a given set of ranges, are ubiquitous in computational geometry. Most often, the set is discrete and is given explicitly. We propose new variants of these problems, dealing with continuous families of convex polyhedra, and show that they capture decision versions of the two-level finite adaptability problem in robust optimization. We show that these problems can be solved in strongly polynomial time when the size of the hitting/covering set and the dimension of the polyhedra and the parameter space are constant. We also show that the hitting set problem can be solved in strongly quadratic time for one-parameter families of convex polyhedra in constant dimension. This leads to new tractability results for finite adaptability that are the first ones with so-called left-hand-side uncertainty, where the underlying problem is non-linear. Joint work with Jean Cardinal and Xavier Goaoc. Manuscript: https://arxiv.org/abs/2504.16642

Étant donné $n \in \mathbb{N}$ et $\mu \in \mathbb{R}$, un arbre de taille $n$ biaisé par la hauteur est un arbre planaire aléatoire $T_n$ à $n$ sommets dont la loi est donnée par $P(T_n = t ) \propto e^{-\mu h(t)}$, où $t$ est un arbre fixe à $n$ sommets, et $h(t)$ est la hauteur de $t$ . Dans cet exposé on va présenter quelques statistiques de ces arbres quand $\mu=\mu(n)$ est une suite à termes positifs dépendant de $n$: la limite d'échelle quand $\mu(n) \sim 1/ \sqrt{n}$, la hauteur ainsi que le comportement autour de la racine quand $0 \leq \mu(n) \ll n$. L'exposé est basé sur arXiv:2512.17747 en commun avec L. Addario-Berry, B. Corsini et N. Maitra.

Lattice walks confined in the first quadrant have been subject to an extended study for about a decade, showing a great variety of techniques to handle functional equations with catalytic variables. A work of Pierre Bonnet and Charlotte Hardouin of 2024 extended those tools in the context of the study of walks based upon models with arbitrarily large steps, allowing to effectively conduct a strategy devised by Bousquet-Mélou, Olivier Bernardi and Kilian Raschel of 2016, providing the algebraicity proofs of some models. In this talk, I show how these tools show the algebraicity of an infinite family of models of walks derived from the Gessel models.

A record of a rooted Cayley tree is a node whose label is the largest along the unique path to the root. In this work, we find elegant functional equations relating the generating functions for records of rooted Cayley trees and for records of forests of rooted trees with the Cayley tree function, and explore the consequences of our results. This is join work with Adrián Lillo and Stefan Trandafir.

The "Minimum Matching Problem" consists in finding an independent edge set of minimum weight M*(G) in a given edge-weighted undirected graph G. If G is bipartite, we deal with the "Assignment Problem". We consider a version of the problem in which we take the union of the optimal matchings for various slightly-modified versions of the base graph: H_J(G)=Union_{U in J} M*(G_U). In this talk we will provide two families of theorems: (1) we prove that, in two distinct settings for the Assignment Problem, the graphs H_J, as well as certain associated graphs H'_J, are in fact spanning trees on the pertinent base graphs G and G'; (2) in the two settings above, if the weights of the graph edges are given by the p-th power of the Euclidean distance for points configurations on the plane, the tree H_J is non-crossing (that is, its natural embedding in the plane has no crossing edges) when p=1, and (more surprisingly) the associated tree H'_J is non-crossing when p=2. Our main motivation for investigating theorems of this form comes from (a family of) conjectures in Statistical Mechanics, that we will illustrate in future work: in the Random Euclidean Assignment Problem (i.e., when the points are chosen i.i.d. on a domain of the plane), for p=2, the two settings above give trees H'_J which are asymptotically distributed as the Uniform Spanning Tree with free and wired boundary conditions, in the two cases. In particular, suitable paths on the tree in the second setting are asymptotically distributed as a SLE at kappa=2. Work in collaboration with Sergio Caracciolo and Gabriele Sicuro

A 3-dimensional polytope (the convex hull of finitely many points) is said to be k-equiprojective if almost every planar projections is a k-gon where k is a fixed integer. Two characterisations were established respectively in 2008 by Masud Hasan and Anna Lubiw and in 2024 by Théophile Buffière and Lionel Pournin in the 3-dimensional case. I will present you a way to generalise the definition of equiprojectivity to d-dimensional polytopes, as well as the tools I built in order to generalise the two different characterisations.

Il est bien connu qu’un code linéaire non dégénéré de longueur n et de dimension k peut être associé à un ensemble de n points (avec multiplicités) dans un espace projectif de dimension k?1. Certaines propriétés des codes peuvent être interprétées géométriquement. Cette perspective relie les codes MDS aux problèmes impliquant des arcs dans les espaces projectifs (la fameuse conjecture MDS a été initialement formulée comme un problème de géométrie projective par Segre), les problèmes de recouvrement aux ensembles saturants, les codes minimaux aux ensembles bloquants forts, etc. Dans cette présentation, nous illustrerons certains résultats récents obtenus en utilisant cette approche géométrique pour les codes en métrique de Hamming et nous esquisserons à la fin comment cela peut être généralisé à d’autres métriques, telles que les métriques rang et somme-rang.

Algebraic shifting, introduced by Kalai in the 80's, is an operator that canonically associates a shifted complex to a given simplicial complex. The advantage of this operator is that it preserves many combinatorial, topological and algebraic properties of the starting complex and in doing so it translates the initial problem to a simpler instance. We show that among such properties is that of area rigidity, a generalization of graph rigidity, and that every triangulation of a surface with small genus is area rigid. For arbitrary surfaces we initiate a statistical study of the behavior of algebraic shifting, and in turn of area rigidity. We show that asymptotically almost surely the algebraic shifting of a random Delaunay triangulation of any given closed Riemannian surface is concentrated in a simplicial complex that depends only on the genus and the number of vertices. This talk is based on joint works with Eran Nevo and Yuval Peled.

A 2-dimensional mosaic floorplan is a partition of a rectangle by other rectangles with no empty rooms. These partitions (considered up to some deformations) are known to be in bijection with Baxter permutations. A d-permutation is a (d-1)-tuple of permutations. In this talk, I will present a work in collaboration with Nicolas Bonichon and Adrian Tanasa where we introduce the d-floorplans which generalise the mosaic floorplans to arbitrary dimensions. I will first present the construction of their generating tree for which the corresponding labels and rewriting rules appear to be significantly more involved in higher dimensions. Then, I will present a bijection between the 2^{d-1}-floorplans and d-permutations characterised by forbidden vincular patterns, generalizing the bijection with Baxter permutations in the case d=2. Finally, I will present some work in progress on the "segments" of the 2^{d-1}-floorplans which relate d-floorplans to another class of d-permutations.

Information geometry is an interdisciplinary field that uses the tools of differential geometry to explore and analyze probability theory and statistics. It focuses on statistical manifolds, geometric spaces (Riemannian manifolds) whose points represent different probability distributions. This geometric perspective provides powerful insights into many fields among which information theory. In this talk, I will present basic ideas about how to connect geometry and statistics, in particular statistical manifolds and their Fisher metric. Finally, closer to my current research themes, a statistical approach is discussed through the introduction of dual affine connections associated with the metric on almost Kähler manifolds. This research is motivated by the Goldberg conjecture, which asserts that a compact symplectic manifold (M,w) endowed with an w-compatible Einstein metric is Kähler.

We consider the number of occurrences of subwords (non-consecutive sub-sequences) in a given word. We first define the notion of subword entropy of a given word that measures the maximal number of occurrences among all possible subwords. We then give upper and lower bounds of minimal subword entropy for words of fixed length in a fixed alphabet, and also showing that minimal subword entropy per letter has a limit value. A better upper bound of minimal subword entropy for a binary alphabet is then given by looking at certain families of periodic words. We also give some conjectures based on experimental observations.

In this talk I will introduce the framework of iterated grafting operators, an operator-based model for generating and analyzing combinatorial structures. This formalism naturally connects to partial differential equations and to the normal ordering problem in operator algebras, and provides powerful tools for enumeration. The combinatorial study of these objects was initiated by Blasiak and Flajolet in Philippe Flajolet's last article Combinatorial Models of Creation-Annihilation, but many aspects remain unexplored. I will then focus on two specific models of preferential attachment graphs that arise from this approach. For these models, I will explain how to extract asymptotics from the associated generating functions using analytic techniques. Finally, I will discuss bijective correspondences with these graphs and open perspectives for random generation.

We consider the 3-state Potts generating function $T(\nu, w)$ of planar triangulations; that is, the series in $\nu$ and $w$ counting planar triangulations with vertices coloured in $3$ colours, weighted by their size and by the number of monochromatic edges (variable $\nu$). This series was proved to be algebraic $15$ years ago: this follows from its link with the solution of a discrete differential equation (DDE), and from general algebraicity results on such equations. However, despite recent progresses on the effective solution of DDEs, the exact value of had remained unknown so far. We have determined at last this exact value, proving that $T(\nu, w)$ satisfies a polynomial equation of degree $11$ in $T$. From this we determine the critical value of $\nu$ and the associated exponent. Another approach, applied to the heavier case of general planar maps (still $3$-coloured) yields an equation of degree $22$. Joint work with Mireille Bousquet-Mélou (LaBRI, Bordeaux)

La complexité abélienne est un outil combinatoire qui calcule le nombre de vecteurs de Parikh de longueur donnée d'un mot infini. On appelle vecteur de Parikh d'un mot fini le vecteur formé par les nombres d'occurrences des lettres dans ce mot. Cette complexité a connu une étude intensive depuis son introduction formelle par Richomme et al en 2009. Dans cet exposé nous présenterons les fonctions de complexité de certains mots classiques (mots sturmiens, mots de Thue-Morse, mot de Tribonacci, ...) et quelques propriétés générales.

On étudie un processus d'apprentissage par renforcement, pour la recherche de plus courts chemins dans un graphe, dans lequel des fourmis partent d'un nid (aléatoire, N1 ou N2) et font une marche aléatoire (pondérée par les poids des arêtes) jusqu'à une source de nourriture F. À leur retour, elles renforcent les arêtes (en ajoutant 1 à leur poids) appartenant au chemin aller auquel on a enlevé les boucles inutiles. Ce modèle a déjà été étudié sur divers graphes dans le cas où le nid est déterministe, notamment les graphes séries-parallèles, mais aussi pour d'autres politiques de renforcements (articles de Kious, Mailler et Schapira). Nous étudions le cas à deux nids, dans des graphes obtenus en joignant trois graphes séries-parallèles pour former un triangle. On montre que les poids des arêtes (normalisés) convergent, vers des variables aléatoires nulles si et seulement si les arêtes associées n'appartiennent pas à un plus court chemin d'un sommet de {N1 , N2 , F } à un autre. Nous présenterons plusieurs outils utiles pour prouver cette convergence, notamment la comparaison avec des processus d'urnes, et quelques résultats sur les approximations stochastiques. La présentation se basera sur un travail en commun avec Cécile Mailler.

During the last 20 years, integrable hierarchies (KP/Toda) have proven to be a great source of recurrence formulas for maps of all kinds. However, most of those formulas still lack a bijective explication. In this talk, we provide a bijective proof for the planar case of Louf's formula, which counts bipartite planar maps with prescribed face degrees and arises from the Toda hierarchy. We actually show that his formula hides two simpler formulas, both of which can be rewritten as natural equations on trees using duality and Schaeffer's bijection for eulerian maps. The underlying bijection for trees can also be interpreted directly on bipartite maps as " slit-slide-sew " operations. As far as we know, this is the first bijection for a formula arising from an integrable hierarchy with infinitely many parameters.

Une séquence d'inversions (ou table d'inversions) est une suite finie d'entiers (s_1, ..., s_n) telle que chaque terme s_i vérifie 0 ? s_i < i. Dans cet exposé, je présenterai différentes manières de construire ces séquences, qui permettent de les compter lorsqu'elles évitent des motifs. Je parlerai en particulier de constructions par "arbre de génération" et de quelques généralisations possibles de cette approche. Enfin, je donnerai un bref aperçu d'un travail en cours qui montre l'algébricité des fonctions génératrices des séquences d'inversions évitant certains ensembles de motifs.

Resume: A marked surface S is a finite-type possibly non-orientable surface with finitely many marked points (P) on the boundary and in the interior. These surfaces have long been studied both from a combinatorial as well as a geometric perspective. When the Euler characteristic of S\P is negative, the surface admits a finite-area hyperbolic metric. Such surfaces are called crowned surfaces, because their boundaries resemble a crown with spikes. Associated to marked/crowned surfaces is a combinatorial and topological object called the arc complex. This is a simplicial complex generated by arcs whose endpoints lie on the marked points. The arc complex has been used to understand the geometry of the surface by various mathematicians like Penner, Harer, Bowditch, Epstein. The arc complex is almost always infinite. In this talk we will focus on four families of surfaces for which it is finite. We will discuss how the topology of this complex helps us to understand certain deformations of crowned surfaces that weakly increase the "distances between spikes". As a result we get the non-simple polytopal realisations of these finite simplicial complexes. This is based ont the joint work with François Guéritaud. https://arxiv.org/abs/2505.01285

** Warning ** : the seminar will take place at 1pm, as it is merged with the seminar of the complexity axis that usually take place during lunch time. This is a survey of research going back more than 60 years on the power of first order logic, along with various restrictions and extensions, to express the behavior of finite automata operating on strings over a finite alphabet. 'Restrictions and extensions' here means modifying the set of atomic formulas, bounding the quantifier depth, bounding the number of bound variables, etc. We want to be able to determine when a particular property (given in some other formalism, for example by a finite automaton) is expressible in the variant of first-order logic under study. When the atomic formulas are restricted in such a way that only regular languages can be defined, there is an intricate mathematical apparatus, based in the algebraic theory of finite semigroups, that provides very precise answers to these questions. This will be the subject of the first part of the talk. There are strong connections, known since the 1980's, between this theory and questions about the complexity of fixed depth circuit families whose gates have unbounded fan-in. This, along with a few other extensions (for example, to automata operating on trees) and some recent results and open probems, will be explored in the second part of the talk.

This talk focuses on classes of planar maps with a weight u>0 on certain components called *blocks*. In collaboration with Fleurat, we study the decomposition of generic planar maps into 2 -connected components, revealing a phase transition between the universality classes of maps (converging to the Brownian sphere) and plane trees (converging to the Brownian tree), depending on the value of u . We identify a new class with the stable tree of parameter 3/2 as the scaling limit in the critical case, and obtain precise results on block sizes in each phase. In a subsequent work, I show that it is possible to study many decomposition schemes along similar lines to shed light on a phase transition. I explain how to obtain enumerative results, block sizes and scaling limits for each phase. Finally, with Albenque and Fusy, we studied tree-rooted random planar maps decomposed into tree-rooted 2 -connected blocks, where a spanning tree is drawn simultaneously with the map. This model, which is of interest in theoretical physics, shows new behaviours. We determine the asymptotic behaviour of 2 -connected tree-rooted maps, reveal a phase transition, and study the properties of each phase.

Cet exposé se situe dans le cadre de la combinatoire des chemins sur réseau. On introduit ici une généralisation des chemins de Dyck (dits "avec trous d'air"), avant de se pencher sur diverses questions classiques à leur sujet : énumération, distributions de motifs, étude de sous-ensembles, etc. Ce faisant, des suites d'entiers positifs (connues dans la littérature) apparaissent naturellement. Dès que possible, on cherchera alors à relier les objets combinatoires décrits par ces suites aux chemins de Dyck avec trous d'air, à travers des bijections explicites. Les travaux présentés ont été effectués pendant mon doctorat, et correspondent à trois publications dont les co-auteurs sont Jean-Luc Baril, Sergey Kirgizov, Helmut Prodinger, et Vincent Vajnovszki.

A braid can be seen as an equivalence class of words, and choosing a unique word representing each braid helps computing braids, motivating the study of normal forms. In the standard braid monoid, two such normal forms are the Garside normal form, which cuts a braid into a sequence of small simple braids, and the alternating normal form, which consists of recursively splitting a braid into a sequence of braids using less strands. The Garside normal form has many useful properties, in particular forming a regular and automatic language, as well as having a simple local characterization. On the other hand, only the regularity of the alternating normal was known. I will describe a new local characterization of the alternating normal form, explicitly construct its minimal automaton, and give some intuitions regarding its automaticity.

A lattice (d,k)-polytope is the convex hull of a set of points in dimension d whose coordinates are integers ranging between 0 and k. We investigate the smallest possible distance between two disjoint lattice (d,k)-polytopes. This question arises in various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching lower and upper bounds for this distance and propose an algebraic model. Our formulation yields explicit formulas in dimensions 2 and 3, and allows for the computation of previously intractable values. Based on joint-work with Shmuel Onn (Technion), Sebastian Pokutta (Zuse Institute Berlin), and Lionel Pournin (Université Paris 13).

In this talk, I will present the main ideas from this paper: Online Prediction in Sub-linear Space, B. Peng and F. Zhang, SODA 2023 (best student paper award). It gives new low-space algorithms for the regret minimisation problem in learning theory. Precious little is required in the way of prerequisites, except that you be intelligent enough to be interested in this sort of thing. The talk will start from the basics (the experts problems), and then cover the new ideas to entend classical learning algorithms to work, approximately, with sub-linear space.

Pierre-Simon Laplace (1749-1827) is widely recognized for his monumental works, Théorie analytique des probabilités and Mécanique céleste. Augustin-Louis Cauchy (1789-1857), on the other hand, revolutionized classical operational analysis by formalizing it with a rigorous foundation, laying the groundwork for modern calculus and complex analysis. However, their contributions to the Stirling partition numbers remain largely overlooked in the combinatorial literature, a gap this talk aims to address. By examining their lesser-known work on Stirling partition numbers through a historical lens and integrating modern methodological perspectives, the presentation highlights the intersection of their insights with the combinatorial framework of Stirling numbers, offering new appreciation for their contributions to this area of mathematics. This research is based on ongoing joint work with Chong-Yi Li and Vytas Zacharovas.

Ces journées s'inscrivent dans le cadre de l'axe 3 (Physique mathématique, Physique Statistique, Combinatoire) de la fédération de recherche Math-STIC de l'Université Sorbonne Paris Nord, qui associe les laboratoires de mathématiques (LAGA), d'informatique (LIPN) et de traitement et transmission de l'information (L2TI). Les exposés auront lieu dans l'amphi Euler de l'Institut Galilée. Des repas (buffets) seront proposés le midi. L'inscription est gratuite mais obligatoire (avant le 20 septembre) pour faciliter l'organisation. Vendredi 4/10 Michael Drmota : The method of moments revisited with applications to planar maps The classical method of moments is used to prove limiting distributions by showing that properly centralized and/or scaled moments of a random variable converge to the corresponding moments of the limit. However, it is not always easy to obtain precise asymptotics for centralized moments - for example for proving a central limit theorem - due to "heavy cancellations". The main goal of this talk is to show some applications to random planar maps of a method of moments by Gao and Wormald that proves a central limit theorem without centralized moments. This is joint work with Eva-Maria Hainzl and Nick Wormald. Alice Contat : Parking on Cayley trees & Frozen Erdös-Rényi Consider a uniform rooted Cayley tree T_n with n vertices and let m cars arrive sequentially, independently, and uniformly on its vertices. Each car tries to park on its arrival node, and if the spot is already occupied, it drives towards the root of the tree and parks as soon as possible. Using combinatorial enumeration, Lackner & Panholzer established a phase transition for this process when m is approximately n/2 . We couple this model with a variation of the classical Erdös-Rényi random graph process. This enables us to describe completely the phase transition for the size of the components of parked cars using a modification of the standard multiplicative coalescent which we named the frozen multiplicative coalescent. The talk is based on joint work with Nicolas Curien. Andrew Elvey Price : Classification of D-finite walks in the quarter plane via elliptic functions Given a set of small steps, we consider the three variable generating function counting walks in the quarter plane using these steps. Since the seminal paper by Bousquet-Mélou and Mishna, the problem of characterising the generating function into the hierarchy Algebraic < D-finite < D-algebraic has received a lot of attention. For unweighted walks this characterisation is complete, however the existing proof of D-finiteness does not generalise to unweighted walks. In this talk I will describe our new proof that the generating function is D-finite in each variable if and only if the group of the walk is finite. This result applies to any weighted model is based on the elliptic function method. This is joint work with Thomas Dreyfus and Kilian Raschel. Enrica Duchi : TBA Quentin Berger : FK-percolation and Recursions on Galton-Watson Trees Some statistical mechanics models on trees may sometimes reduce to the study of some "simple" tree recursion; this is for instance the case for the FK-percolation model. It turns out that when the recursion is concave, we can compare this tree recursion to the one verified by (possibly non-linear) resistive networks. I will present a recent work with Irene Ayuso Ventura (Créteil), in which we obtain precise estimates on the asymptotic behaviour of non-linear conductances of Galton-Watson tree, also deriving some information on the FK-percolation model on random trees.

Ces journées s'inscrivent dans le cadre de l'axe 3 (Physique mathématique, Physique Statistique, Combinatoire) de la fédération de recherche Math-STIC de l'Université Sorbonne Paris Nord, qui associe les laboratoires de mathématiques (LAGA), d'informatique (LIPN) et de traitement et transmission de l'information (L2TI). Les exposés auront lieu dans l'amphi Euler de l'Institut Galilée. Des repas (buffets) seront proposés le midi. L'inscription est gratuite mais obligatoire (avant le 20 septembre) pour faciliter l'organisation. Jeudi 3/10 Mireille Bousquet-Mélou : Combinatorics of 3-coloured quadrangulations This talk deals with the enumeration of (planar) maps equipped with a proper 3-colouring of their vertices. The case of triangulations is well-understood, with an algebraic generating function and bijective solutions. The case of general planar maps is still algebraic, but the combinatorial explanations for that are missing. We will focus on quadrangulations, for which algebraicity is lost. We will see that this problem admits several interesting reformulations (in terms of orientations, of height functions...), which suggest to record in the enumeration other statistics, beyond the edge number. We will present solutions for some bivariate problems, obtained in collaboration with Andrew Elvey Price (Tours). Mingkun Liu : Length spectra of random metric maps: a Teichmüller theory approach In this talk, I will first discuss short closed geodesics on a random hyperbolic surface of large genus, and we will see that the lengths of these geodesics are distributed in exactly the same way as those of the short cycles in a big random map (following the work of Mirzakhani­­-Petri and Janson-Louf). Next, I will present a joint work with Simon Barazer and Alessandro Giacchetto, where we study random maps of large genus with a Teichmüller theory approach. Armand Riera : TBA Meltem Ünel : TBA Baptiste Louf : Counting with random walks We are interested in an enumerative problem, namely counting geometric objects called combinatorial maps, which can be parametrized by two numbers: their size, and a topological parameter called the genus. We are interested in an asymptotic estimation of the number of these objects when both the size and the genus go to infinity. While enumeration in one parameter is a very well studied topic with many powerful tools available, this problem is a case of bivariate enumeration, is a rather new topic with very few results known at the moment. Our method consists in studying a recurrence formula for these maps and modeling it by a random walk, forgetting completely about the combinatorics of the model. This is a work in progress with Andrew Elvey-Price, Wenjie Fang and Michael Wallner.

Machine learning theoretical models very often assume a dataset obtained from a Gaussian distribution, or from a Gaussian mixture. The possible limitations of such a Gaussian assumption have been recently object of investigation, and theoretically characterization, leading to a number of "Gaussian universality" results. In this talk I will present an analytical treatment of the performance in high dimensions of simple architectures on heavy-tailed distributed datasets, showing that even simple generalized linear models exhibit a striking dependence on non-Gaussian features in both classification and regression tasks.

talk for the students, EUR Math&CS

Les fonctions G et les fonctions E sont des séries entières à coefficients algébriques qui sont solution d'une équation différentielle et satisfont à des conditions de croissance de nature arithmétique. Elles correspondent aux fonctions holonomes/D-finies qui apparaissent dans de nombreux problèmes en combinatoire, probabilité, physique. Elles ont été introduites dans le mémoire de Siegel sur les applications de l'approximation diophantienne en 1929, dans le but de généraliser les résultats de transcendence pour les valeurs de la fonction exponentielle en des arguments algébriques. Je survolerai de façon accessible quelques progrès récents, voire très récents, et moins récents sur les fonctions G et les fonctions E, en mettant l'accent sur deux questions : quelle est la structure de leurs équations différentielles ? quelle place occupent les fonctions hypergéométriques parmi elles ?

The Laguerre polynomials are a family of orthogonal polynomials which have been well-studied in combinatorics. The coefficients of these polynomials enumerate a certain family of graphs which have been called Laguerre digraphs or Laguerre configurations. The polynomial sequence has a well-known Stieltjes moment representation, i.e., these polynomials can be expressed as the sequence of moments of a certain measure supported on the positive real-axis. It is known that a sequence is a Stieltjes moment sequence if and only if its Hankel matrix is totally positive. A natural question is to ask if the Hankel matrix is also coefficientwise totally positive. We will address this question in this talk. We will begin by stating the main theorem which will not require any prerequisites. We then motivate this result; we first state the equivalence between Stieltjes moment sequences and the total positivity of Hankel matrices, then we mention how this theory has been extended coefficientwise. We introduce the production-matrix method which is a powerful tool to prove total positivity. Finally, we sketch a proof of our main theorem.

Lecture 3: Popular assignments and extensions. This talk will be on popular matchings in the one-sided preferences model. Popular matchings need not always exist in this model and there is a simple combinatorial algorithm to decide if one exists. We will see an LP-duality inspired algorithm for the more general problem of deciding if a popular assignment (i.e., a popular maximum-matching) exists or not. This algorithm can be generalized to solve the popular common base problem in the intersection of two matroids where one matroid is the partition matroid, this implies the popular arborescence problem (relevant in liquid democracy) can be solved efficiently. This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/.

Lecture 2: Popular matchings and optimality. In this talk we will consider algorithms for finding optimal popular matchings. While it is easy to find max-size popular matchings, it is NP-hard to find a min-cost popular matching. This motivates us to relax popularity to a weaker notion called "quasi-popularity". Describing the popular and quasi-popular matching polytopes is hard, but there is an easy-to-describe integral polytope sandwiched between these two hard ones. So we can efficiently find a quasi-popular matching of cost at most that of a min-cost popular matching. This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/.

The arc complex is a pure flag simplicial complex associated to a finite-type topological surface with marked points. It was discovered by Harvey and used by geometers like Harer, Penner, Bowditch, Epstein to study geometric properties of hyperbolic surfaces, their Teichmüller spaces and their mapping class groups. The arc complex is also a subcomplex of the cluster complex of a cluster algebra, defined by Fomin-Zelevinksy. For most of the surfaces, the arc complex is locally non-compact. In this talk, I will discuss about the simplicial topology of the arc complex in the finite cases. In particular, I will focus on the shellability (analogous to simply-connectedness) and collapsibility (analogous to contractibility) of these finite complexes and prove that they are closed combinatorial balls. Related articles: https://arxiv.org/abs/2402.10530, https://arxiv.org/abs/2306.06695

Lecture 1, Introduction to popular matchings. The problem of computing a stable matching in a bipartite graph is an old and well-studied problem. Gale and Shapley showed in 1962 that such a matching always exists and can be efficiently computed. This is a classical result in algorithms with many applications in economics and computer science. Stability is a strong and rather restrictive notion. This series of talks will be on a relaxation of stability called "popularity". In the first talk we will see simple and efficient algorithms for some popular matching problems. No background in algorithms or matching theory will be assumed. This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/.

Nous discuterons de la limite de faible intensité des tessellations de Poisson--Voronoï sur les espaces hyperboliques, alias tessellations idéales de Poisson--Voronoï (IPVT de l'anglais). En particulier, nous verrons comment une simple description poissonnienne de la cellule qui contient l'origine de l'espace hyperbolique (cellule zéro) permet d'étudier des propriétés fines des tuiles de l'IPVT. L'exposé présentera des impressions en 3D de réalisations de la cellule zéro de l'IPVT de l'espace hyperbolique tridimensionnel dans le modèle de la boule de Poincaré. Travail en collaboration avec Nicolas Curien, Nathanaël Enriquez, Russell Lyons et Meltem Ünel. Pour en savoir plus sur les bijoux : https://matteodachille.github.io/ipvt