Le séminaire a eu lieu les jeudis 3 octobre 2019, 28 novembre 2019, 30 janvier 2020 (les autres séances sont annulées pour cause de pandémie).
3 octobre 2019
-
Éric Fusy (CNRS, École Polytechnique),
Intervalles de Tamari généralisés et cartes planaires orientées.
Transparents.
La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années, avec de riches propriétés énumératives. En particulier une construction due à Bernardi et Bonichon (s'appuyant sur les bois de Schnyder) établit une bijection entre intervalles de Tamari de taille n et triangulations à n sommets internes. Le treillis de Tamari a été récemment étendu par Préville-Ratelle et Viennot aux treillis dits de nu-Tamari, et dans ce contexte on parle d'intervalles de Tamari généralisés. Fang et Préville-Ratelle ont montré que les intervalles généralisés sont en bijection avec les cartes planaires non-séparables, par une approche bijective à base d'arbres étiquetés de parcours en profondeur. Nous montrerons ici deux autres approches bijectives. La première s'appuie sur les décompositions séparantes de quadrangulations et est une extension de la bijection de Bernardi et Bonichon. La seconde spécialise la bijection de Bernardi et Bonichon aux intervalles de Tamari dits synchronisés, qui s'identifient aux intervalles généralisés. Travaux en commun avec Abel Humbert.
-
Brigitte Vallée (CNRS, Université de Caen),
The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace.
Transparents.
The Depoissonisation process is central in various analyses of the AofA domain. I first recall the two possible paths that may be used in this process, namely the Depoissonisation path and the Rice path. The two paths are rarely described (for themselves) in the literature, and general methodological results are often difficult to isolate amongst particular results that are more directed towards various applications. The main results for the Depoissonisation path are scattered in at least five papers, with a chronological order which does not correspond to the logical order of the method. The Rice path is also almost always presented with a strong focus towards possible applications. It is often very easy to apply, but it needs a tameness condition, which appears a priori to be quite restrictive, and is not deeply studied in the literature. This explains why the Rice path is very often undervalued. Second, the two paths are not precisely compared, and the situation creates various "feelings": some people see the tools that are used in the two paths as quite different, and strongly prefer one of the two paths; some others think the two paths are almost the same, with just a change of vocabulary. It is thus useful to compare the two paths and the tools they use. I also "follow" this comparison on a precise problem, related to the analysis of tries. The talk also exhibits a new framework, of practical use, where the tameness condition of Rice path is proven to hold. This approach, perhaps of independent interest, deals with the inverse Laplace transform, which does not seem of classical use in this context. It performs very simple computations. This adds a new method to the Depoissonisation context and explains the title of the talk I then conclude that the Rice path is both of easy and practical use : even though (much?) less general than the Depoissonisation path, it is easier to apply.
-
Omid Amini (CNRS, École Polytechnique),
Logarithmic tree factorials.
To any rooted tree we associate a sequence of numbers that we call logarithmic factorials of the tree. This provides a generalization of the work of Manjul Bhargava to a combinatorial setting suitable for the study of questions around generalized factorials. The aim of the talk will be to present basic aspects of this framework with connections to algebra, number theory, and probability, and to discuss several open questions.
28 novembre 2019
-
Jérémie Bettinelli (CNRS, École Polytechnique),
Une bijection (améliorée) pour les cartes nonorientables.
Récemment, Chapuy et Dolega ont trouvé une bijection entre les quadrangulations biparties d'une surface nonorientable et les cartes à une face de la même surface, dont les sommets sont étiquetés. Cette bijection généralise la bijection de Chapuy, Marcus et Schaeffer qui se concentrait sur les surfaces orientables et qui généralisait la fameuse bijection de Cori, Vauquelin et Schaeffer entre les quadranguations planes et les arbres bien étiquetés. Au cours de cet exposé, nous allons un pas plus loin en présentant une bijection entre les cartes générales d'une surface nonorientable donnée et certaines cartes étiquetées à une face de la même surface. Cette bijection généralise à la fois la bijection de Chapuy et Dolega et celle de Bouttier, Di Francesco et Guitter pour les cartes planes générales. La version présentée ici a été améliorée par rapport à une ancienne version que nous avons pu présenter précédemment, au sens notamment où les objets codants sont aujourd'hui plus simples à décrire.
-
Peggy Cénac (Université de Bourgogne),
Chaînes de Markov à mémoire variable et marches aléatoires persistantes.
Cet exposé présentera une petite zoologie de chaînes de Markov à mémoire variable, avec des conditions d’existence et unicité de mesure invariante. Il sera ensuite question de marches aléatoires persistantes, construites à partir de chaînes de Markov à mémoire non bornée, où les longueurs de sauts de la marche ne sont pas forcément intégrables. Un critère de récurrence/transience s’exprimant en fonction des paramètres du modèle sera énoncé. Suivront plusieurs exemples illustrant le caractère instable du type de la marche lorsqu’on perturbe légèrement les paramètres. Les travaux décrits dans cet exposé sont le fruit de plusieurs collaboration avec B. Chauvin, F. Paccaut et N. Pouyanne ou B. de Loynes, A. Le Ny et Y. Offret et A. Rousselle.
-
Pierre-Guy Plamondon (Université Paris Sud),
L’associaèdre et le cone des réalisations polytopales d’un éventail de g-vecteurs de type fini.
L'étude des algèbres amassées fait naturellement apparaître un polytope omniprésent en algèbre et en combinatoire, soit l'associaèdre. Dans ce contexte, l'associaèdre est vu comme une réalisation polytopale d'un éventail simplicial : l'éventail des g-vecteurs d'une algèbre amassée. À partir d'un tel éventail simplicial, nous étudierons l'ensemble de ses réalisations polytopales. Cet ensemble, appelé "cône des types", peut être réalisé comme un cône polytopal. Nous verrons d'abord que si le cône des types est simplicial, alors il permet de décrire simplement toutes les réalisations polytopales de l'éventail de départ. Nous appliquerons ensuite cette observation aux algèbres amassées de type fini, où le problème se traduit par la recherche des relations linéaires minimales entre g-vecteurs. Nous retrouverons et généraliserons ainsi les réalisations polytopales de l'associaèdre obtenues par Arkani-Hamed, Bai, He et Yan, et par Bazier-Matte, Douville, Mousavand, Thomas et Yıldırım. Cet exposé traitera d'un travail en commun avec Arnau Padrol, Yann Palu et Vincent Pilaud.
30 janvier 2020
-
Cristina Toninelli (CNRS, Université Paris Dauphine),
Bootstrap percolation and kinetically constrained spin models: critical time scales.
Recent years have seen a great deal of progress in understanding the behavior of bootstrap percolation models, a particular class of monotone cellular automata. In the two dimensional lattice there is now a quite complete understanding of their evolution starting from a random initial condition, with a universality picture for their critical behavior. Much less is known for their non-monotone stochastic counterpart, namely kinetically constrained models (KCM). In KCM each vertex is resampled (independently) at rate one by tossing a p-coin iff it can be infected in the next step by the bootstrap model. In particular infection can also heal, hence the non-monotonicity. Besides the connection with bootstrap percolation, KCM have an interest in their own : when $p \to 0$ they display some of the most striking features of the liquid/glass transition, a major and still largely open problem in condensed matter physics. I will discuss some recent results on the characteristic time scales of KCM as $p \to 0$ and the connection with the critical behavior of the corresponding bootstrap models.
-
Xavier Goaoc (École des Mines de Nancy),
Compter et simuler les types d’ordres du plan.
Transparents.
Cet exposé introduira aux types d'ordres et aux chirotopes, des structures combinatoires d'origine géométrique qui sont encore mal comprises. Nous aborderons en particulier les questions de leur comptage et de leur génération aléatoire, deux questions actuellement mal comprises. L'exposé ne supposera pas de connaissance géométrique et présentera plusieurs problèmes ouverts.
-
Andrea Sportiello (CNRS, Université Paris 13),
Field-Theoretic approach to the Euclidean Random Assignment Problem.
Transparents.
Let $X = \{x_1, \ldots, x_n\}$ and $Y = \{y_1, \ldots, y_n\}$ be i.i.d. uniform random points on the unit $d$-dimensional torus. For $s$ a permutation in $S_n$, call $H(s;X,Y) = \sum_i |x_i-y_{s(i)}|^2$, call $H(X,Y) = \min_s H(s;X,Y)$, and $H(n)$ the average of $H(X,Y)$. How does $H(n)$ scale with $n$? It comes out that the most interesting case is $d=2$, for which the answer is (apparently) $H(n) \sim 1/(2 \pi) \log(n) + (\textrm{smaller terms})$
This result has been derived, non-rigorously, by Caracciolo and Sicuro, by methods of Theoretical Physics which in particular involve a linearisation of the "action", and the introduction of an "ultraviolet cut-off", and then proven by Ambrosio, Stra and Trevisan, with methods of functional analysis.
Our goal is to show that, if we insist in analysis the problem exactly (without linearisation), we end up with a peculiar perturbative series "a la Feynman", which shows a surprising combinatorial resummation of terms. As a result, this problem is a good illustration of the mechanisms behind regularisations and perturbative expansions in Quantum Field Theories.
Work in collaboration with S. Caracciolo, M.P. D'Achille and G. Sicuro.