PQRS

P

• Arnau Padrol (IMJ, Paris 6),
  Tropical Catalan Subdivisions.
  29/09/2016.
  Transparents.

We revisit an ubiquitous associahedral triangulation, introduced by Gelfand, Graev and Postnikov in 1997, to provide geometric realizations of the v-Tamari lattice of Préville-Ratelle and Viennot as the dual of a triangulation of a polytope, as the dual of a mixed subdivision, and as the edge-graph of a polyhedral complex induced by an arrangement of tropical hyperplanes. The method generalizes to type B. 

This is joint work with Cesar Ceballos and Camilo Sarmiento.

• Konstantinos Panagiotou (LMU Munich),
  Catching the k-NAESAT Threshold.
  27/09/2012.

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions. To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation, which yields precise conjectures on the threshold values of many random CSPs. In this talk I will discuss a new Survey Propagation inspired method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously, and prove very accurate estimates for the k-NAESAT threshold; in particular, we verify the statistical mechanics conjecture for this problem.

This is joint work with Amin Coja-Oghlan.

• Hugo Parlier (Université de Fribourg, Suisse),
  Combinatorial moduli spaces.
  4/12/2016.

This talk will revolve around the general theme of combinatorial methods in the study of configuration spaces of surfaces. Classical moduli spaces describe conformal or isometry classes of certain surfaces: combinatorial moduli spaces describe discrete analogs of them.

A particular focus will be on flip graphs of triangular decompositions of surfaces where distance between surface triangulations is measured by how many flip transformations are needed to go from a triangulation to another. Flip graphs come up in a variety of contexts and, depending on the surface type, can either be finite or infinite graphs. A well studied example of a finite flip graph is when the surface is a polygon. However, once the surface has enough topology, flip graphs are infinite and as metric spaces turn out to be quasi-isometric to the underlying mapping class groups (groups of self homeomorphisms of the surface up to isotopy). Surface homeomorphisms act naturally on these graphs and the quotient finite graphs are a prime example of a combinatorial moduli space.

This talk will be about geometric aspects (and in particular the diameter) of flip graphs for different types of surfaces. The results I'll discuss are joint with a variety of authors including V. Disarlo, L. Guth, L. Pournin and R. Young.

• Aline Parreau (LIRIS, Université Lyon 1)
  Complexité algorithmique du jeu de domination Maker-Breaker sur les graphes.
  6/06/2024.

Dans cet exposé, nous expliquerons à travers l'exemple du jeu de domination Maker-Breaker dans les graphes comment être sûr de pouvoir construire une structure donnée face à un adversaire malveillant. Dans le jeu de domination dans les graphes, à chaque tour, Dominator choisit un sommet du graphe puis Staller lui interdit un sommet. A la fin, Dominator gagne si elle a obtenu un ensemble dominant avec ses sommets: c'est-à-dire si chaque sommet du graphe est à distance au plus 1 d'un sommet de Dominator.

Alors que les problèmes classiques de graphes sont très souvent dans la classe NP, savoir si Dominator peut gagner à tous les coups est un problème PSPACE-complet. Cela est en particulier dû au fait que décrire une stratégie pour l'un des joueurs ne peut se faire en temps polynomial en général. Nous verrons dans cet exposé des stratégies structurelles pour Dominator qui sont suffisantes pour certaines classes de graphes comme les graphes d'intervalles, les graphes planaires extérieures ou les graphes réguliers. Cela permet en particulier d'améliorer la complexité du problème dans ces classes de graphes : ainsi les graphes réguliers peuvent toujours être dominés par Dominator, déterminer qui gagne pour un graphe planaire extérieur est polynomial. Pour les graphes d'intervalles, nous obtenons que ce problème est dans NP en le ramenant à la recherche d'une structure particulière dans le graphe mais ne savons pas si cette recherche peut se faire en temps polynomial...

• Guillem Perarnau (Birmingham),
  A switching approach to random graphs with a fixed degree sequence.
  1/12/2014.

For a fixed degree sequence $D=(d_1,...,d_n)$, let $G(D)$ be a uniformly chosen (simple) graph on $ \{1,...,n\} $ where the vertex $i$ has degree $d_i$. The study of $G(D)$ is of special interest in order to model real-world networks that can be described by their degree sequence, such as scale-free networks. While many aspects of $G(D)$ have been extensively studied, most of the obtained results only hold provided that the degree sequence $D$ satisfies some technical conditions. 

In this talk we will introduce a new approach (based on the switching method) that allows us to study the random graph $G(D)$ imposing no conditions on $D$. Most notably, this approach provides a new criterion on the existence of a giant component in $G(D)$. Moreover, this method is also useful to determine whether there exists a percolation threshold in $G(D)$. 

The first part of this talk is joint work with F. Joos, D. Rautenbach and B. Reed, and the second part, with N. Fountoulakis and F. Joos.

• Adeline Pierrot (Laboratoire de Recherche en Informatique, Université Paris-Sud),
  Trier des permutations avec des piles en série.
  16/10/2014.
  Transparents.

Le tri par pile a été intruduit par Knuth dans les années 60 (voir le volume 1 de The Art of Computer Programming). Le problème de la caractérisation des permutations triables par une pile est le problème historique qui a amené à définir la notion de motif dans les permutations et de classe de permutations close par motifs exclus, domaines de recherche très actifs en combinatoire. Le tri par pile fut ensuite généralisé par Tarjan qui a introduit les réseaux de tri, et de très nombreuses variantes ont été étudiées par la suite.

Dans cet exposé, on s'intéressera en particulier au problème de savoir décider si une permutation donnée en entrée est triable par deux piles connectées en série (variante introduite par Knuth dans le volume 3 de The Art of Computer Programming). Dans la littérature existante, ce problème de décision est cité à de nombreuses reprises, et a été conjecturé à la fois comme étant NP-complet ou polynomial. La difficulté du problème réside dans le fait que l'on considère les deux piles en même temps, ce qui laisse une grande latitude de choix d'opérations possibles sur la permutation et donne un algorithme naïf exponentiel (contrairement à d'autres variantes qui sont plus restrictives).

En introduisant la notion de tri par sas (tri dans lequel tous les éléments doivent être entrés dans les piles avant que le premier élément puisse être écrit en sortie) et en utilisant une décomposition de la permutation, on résout ce problème resté longtemps ouvert en donnant un algorithme polynomial. Cet algorithme utilise de jolies méthodes combinatoires, notamment la notion de motif dans les permutations, ainsi qu'une bijection entre certains bi-coloriages d'une permutation et l'ensemble des tris par sas de la permutation.

• Vincent Pilaud (Laboratoire d’Informatique de l’École polytechnique – LIX, CNRS),
  Réalisations géométriques des associaèdres de graphe.
  12/02/2015.
  Transparents.

L'associaèdre est un polytope qui encode la combinatoire des dissections d'un polygone convexe. Il apparaît dans divers sujets combinatoires (treillis de Tamari et treillis Cambriens, diamètre de graphes de flips,...), géométriques (polytopes secondaires, permutaèdres généralisés,...) et algébriques (algèbres amassées, algèbre de Hopf des arbres binaires,...). On en connaît de nombreuses réalisations géométriques qui illustrent de riches propriétés combinatoires. Dans cet exposé, on présentera deux de ces réalisations (l'une due à F. Chapoton, S. Fomin et A. Zelevinsky et étendue par F. Santos, et l'autre due à J.-L. Loday et étendue par C. Hohlweg et C. Lange). On discutera ensuite la généralisation de ces constructions aux associaèdres de graphe. 

L'exposé est basé sur des travaux en commun avec C. Lange et T. Manneville.

• Vincent Pilaud (LIX)
  Treillis de réorientations acycliques et leurs treillis quotients.
  24/10/2022.
  Transparents.

Étant donné un graphe orienté acyclique D, on considère l’ensemble de ses réorientations acycliques, ordonnées par inclusion des ensembles d’arcs retournés. On obtient par  exemple un treillis booléen lorsque D est une forêt, et l’ordre faible lorsque D est un  tournoi. Nous caractériserons les graphes orientés acycliques D pour lesquels cet ordre est un treillis, et même un treillis semidistributif. Dans ce dernier cas, nous  présenterons un modèle combinatoire pour les sup irréductibles de ce treillis, et montrerons comment lire les représentations canoniques par sup et l’ordre de forçage sur les sup irréductibles pour manipuler les congruences et les quotients de ces treillis. Ceci amène naturellement à des généralisations graphiques des associaèdres, des permutarbrèdres, et plus généralement des quotientopes, construits à partir de polytopes de tessons graphiques.

Cet exposé est basé sur http://arxiv.org/abs/2111.12387.

• Carine Pivoteau (LIGM, Université Paris-Est Marne-la-Vallée),
  De bonnes prédictions valent bien quelques comparaisons.
  14/04/2016.
  Transparents.

La plupart des processeurs modernes sont très fortement parallélisés et utilisent des prédicteurs pour deviner la direction des branchements conditionnels dans les programmes, afin d'éviter de coûteux retards dans leur "pipeline". Nous proposons des variantes adaptées à ces prédicteurs pour deux algorithmes classiques: l’exponentiation rapide et la recherche dichotomique. En utilisant des arguments combinatoires et des résultats simples sur les chaînes de Markov, nous montrons que les améliorations proposées conduisent à moins d'erreurs de prédiction en moyenne, au prix d'un petit accroissement du nombre d'opérations basiques. Ces résultats théoriques sont confirmés par des tests en pratique qui montrent que nos algorithmes sont sensiblement plus rapides que les algorithmes standards, pour des types de données primitifs.

• 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.
  28/11/2019.

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.

• Viviane Pons (LRI, Université Paris Sud),
  Treillis et Algèbre de Hopf sur les relations binaires.
  21/9/2017.
  Transparents.

Nous expliquons comment des structures bien connues telles que l'ordre faible sur les permutations ou bien l'algèbre de Hopf de Malvenuto Reutenaurer peuvent être obtenues à partir de définitions très simples sur les relations binaires. Nous définissions tout d'abord un treillis et une algèbre de Hopf sur les relations binaires. A partir de ces deux objets, nous obtenons un treillis et une algèbre de Hopf sur les posets d'entiers. Nous voyons ensuite comment de nombreux objets combinatoires tels que les permutations ou les arbres binaires peuvent être représentés par des posets d'entiers ce qui nous amène à re-découvrir des structures algébriques bien connues ainsi qu'à en définir de nouvelles.

• Dominique Poulalhon (LIX, Ecole polytechnique),
  Preuve bijective de la formule d’Hurwitz.
  27/01/2012.
  Transparents.

En 1891, Hurwitz donne une formule dénombrant certains revêtements ramifiés de la sphère $S^2$ par elle-même, qui en termes combinatoires correspondent aux $m$-uplets de transpositions engendrant un sous-groupe transitif de $S_n$ et dont le produit est une permutation à $l = m-n+2$ cycles de longueurs fixées par une partition $\alpha_1,\ldots,\alpha_l$. Cette formule relativement simple fait entre autres intervenir les nombres d'arbres de Cayley à $\alpha_i$ sommets, mais aucune des démonstrations obtenues jusqu'à présent n'explique vraiment pourquoi ces termes apparaissent. Le parallèle avec les formules énumérant des familles de cartes planaires, qui font intervenir les nombres (d'arbres) de Catalan, est pourtant tentant. J'exposerai la preuve bijective obtenue récemment avec Enrica Duchi et Gilles Schaeffer, en montrant sa parenté avec les constructions bijectives obtenues précédemment pour les cartes planaires.

• Lionel Pournin (LIPN, Université Paris 13),
  Questions géométriques et combinatoires sur les polytopes en nombres entiers.
  4/04/2019.
  Transparents.

Plusieurs questions et résultats seront présentés sur les polytopes en nombres entiers de dimension $d$ contenus dans un hypercube de côté $k$. La première question abordée portera sur le plus grand diamètre possible pour leur graphe en fonction de $d$ et de $k$, et en particulier dans le cas des zonotopes primitifs. La deuxième question portera sur le nombre de sommets des zonotopes primitifs, qui apparait en physique théorique et en optimisation combinatoire. La troisième question sera celle de la structure des polytopes en nombre entiers en tant qu'ensemble. Les propriétés de connexité d'un graphe dont ils sont les sommets seront présentées et discutées.

Cet exposé repose sur des résultats obtenus en collaboration avec Antoine Deza (McMaster University), Rado Rakotonarivo (Université Paris 13) et Noriyoshi Sukegawa (Tokyo University of Science).

R

• Arun Ram (Univ. Melbourne-Australie),
  Polytopes, shuffles, quivers and flags.
  3/01/2011.
  Transparents.

There are two geometries that show remarkable similarities: that of quiver varieties and that of affine flag varieties. By work of Braverman-Gaitsgory and Gaussent-Littelmann and Kashiwara-Saito and Kamnitzer-Baumann one sees the crystals, in the sense of Kashiwara, coming from both quivers and flags. In the picture of Leclerc-Geiss-Schroer one sees how elements of the shuffle algebra come from quiver varieties. In joint work with A. Ghitza and S. Kannan we are seeing shuffle elements coming from affine flag varieties. Following my recent joint work Ghitza and S. Kannan, I will explain the purely combinatorial approach for seeing the moment polytopes and the shuffle elements.

• Sanjay Ramassamy (IPhT)
  Integrable dynamics on polygons and the dimer integrable system
  08/02/2024.

On the one hand, several discrete-time dynamical systems on spaces of polygons have been shown in the last twenty years to be integrable. On the other hand, Goncharov and Kenyon introduced ten years ago an integrable system associated with the dimer model on bipartite graphs on the torus. Building upon the notion of triple crossing diagram maps (introduced in recent works of Affolter, Glick, Pylyavskyy and myself), I will describe a framework which encompasses both the geometric dynamics on polygons and the dimer integrable system. This framework makes it possible in particular to identify the conserved quantities of both systems. I will illustrate this paradigm on the example of the pentagram map.

This talk is based on joint works with Niklas Affolter (TU Berlin), Terrence George (UCLA), Max Glick (Google) and Pavlo Pylyavskyy (University of Minnesota).

• Kilian Raschel (LMPT, Tours),
  Marches aléatoires dans des cônes : exposants critiques.
  29/09/2016.
  Transparents.

Le modèle combinatoire des marches dans des cônes connaît actuellement un essor considérable. Dans cet exposé nous parlerons de marches à grands pas, en dimension quelconque et de marches avec des poids. Nous nous concentrerons sur les exposants critiques qui apparaissent dans les asymptotiques (1) des nombres d'excursions (marches reliant deux points fixés en un nombre donné de pas tout en restant dans un cône), et (2) des nombres de marches de longueur prescrite.
Nous présenterons les travaux fondateurs de Denisov et Wachtel répondant à (1) ainsi que des résultats partiels et des conjectures liés à (2). Nous évoquerons des énoncés nouveaux de non-D-finitude des séries génératrices de comptage. Il s'agit de résultats correspondant à des travaux en cours avec Julien Courtiel, Steve Melczer et Marni Mishna d'une part, Rodolphe Garbit et Sami Mustapha d'autre part.

• Vlady Ravelomanana (IRIF, Paris 7),
  Combinatorics of some tractable phase transitions.
  7/6/2018.

Several combinatorial structures are subject to phase transitions as one of their parameters increases when their sizes are large but fixed. Such structures include random CNF formulas (a SAT/UNSAT transition occurs from under to overconstrained instances) or random graphs (from sparse to dense instances some properties vanish). Determining the nature of a phase transition (sharp or coarse), locating it, determining a precise scaling window and better understanding the structure of the space of solutions turn out to be very interesting tasks. These challenges have aroused a lot of interest in different communities, namely mathematics, computer science and physics. In this talk, we will review various phase transitions of random graph properties or  $2$-CNF formulas, emphasizing the strengths (and limits?) of enumerative/analytic approaches.

• Andrew Rechnitzer (University of British Columbia, Vancouver),
  Trivial words in groups.
  6/06/2013.
  Transparents.

Random walks appear at the heart of many problems in mathematics. Perhaps one of the most famous questions is "What is the probability that a random walk returns to its starting point?"

For a random walk on the line or the square-grid, this question can be answered quite directly by recasting the problem as one of counting loops.
However on more complicated graphs the problem is far from trivial. In the setting of geometric group theory, this question is intimately tied to the problem of "amenability" and the number of trivial words. While amenability (and so the probability that a random walker returns) can be decided for many groups, it remains "very open" for Thompson's group $F$.

In this work, we apply numerical and enumerative methods from statistical mechanics and combinatorics to the study of random walks on groups and so examine the amenability of Thompson's group.

This is work together with Murray Elder, Buks van Rensburg and Thomas Wong. No prior knowledge of group theory or statistical mechanics required...

• Baptiste Rognerud (IMJ-PRG)
  Un ordre partiel d’origine algébrique sur les tableaux de permutation.
  6/06/2024.

Les treillis de Tamari sont des ordres partiels particulièrement bien étudiés, qui apparaissent dans de nombreux domaines des mathématiques.En théorie des représentations ils apparaissent, par exemple, comme ensembles de modules basculants d'une certaine algèbre. Dans cet exposé nous allons brièvement introduire une famille de modules qui généralise les modules basculants. Ces modules sont en réalité très anciens, ils remontent essentiellement à Schur, mais de façon curieuse aucun résultat de classification n'a été obtenu avant nos travaux. Nous allons voir que dans un cas simple, cette classification fait intervenir de la combinatoire très sympathique de remplissages de diagrammes.
Il sera ensuite très naturel d'introduire une relation d'ordre sur ces objets et nous verrons que celle-ci généralise la relation d'ordre de Tamari. Informellement c'est un "ralentissement" de la rotation des arbres binaires. Dans la seconde partie de l'exposé, nous verrons que cette relation d'ordre possède d'excellentes propriétés : essentiellement toutes les propriétés de l'ordre de Tamari.
C'est un travail en commun avec Crawley-Boevey, Ma et Sauter et plus récemment avec Corteel et Jang.

• Dan Romik (University of California, Davis)
  A new proof of Viazovska’s modular form inequalities for sphere packing in dimension 8.

07/12/2023.
Transparents.

Maryna Viazovska in 2016 found a remarkable application of the theory of modular forms to a fundamental problem in geometry, obtaining a solution to the sphere packing problem in dimension 8 through an explicit construction of a so-called "magic function" that she defined in terms of classical functions, the Eisenstein series and Jacobi thetanull functions. The same method also led shortly afterwards to the solution of the sphere packing in dimension 24 by her and several collaborators. One component of Viazovska's proof consisted of proving a pair of inequalities satisfied by the modular forms she constructed. Viazovska gave a proof of these inequalities that relied in an essential way on computer calculations. In this talk I will present a new proof of Viazovska's inequalities that uses only elementary arguments that can be easily checked by a human.

• Maria Ronco (Institute of Mathematics and Physics, Universidad de Talca),
  Structures algébriques associées au associaèdres de graphes.
  12/02/2015.
  Transparents.

M. Carr et S. Devadoss ont associé à tout graphe simple $G$, à $n$ sommets, un polytope $K(G)$ de dimension $n-1$. On veut montrer comment construire une triangulation de $K(G)$ à partir de sous-graphes connexes de $G$, qui généralise la triangulation de l’associaèdre faite par J.-L. Loday. Nous allons aussi définir des structures algébriques associées aux associaèdres de graphes pour certaines familles de graphes, ainsi qu’un ordre sur l’ensemble de faces qui généralise l’ordre de Tamari.

• Juanjo Rué (U. Politècnica de Catalunya),
  Enumeration and asymptotic counting of 4-regular planar graphs.
  6/06/2019.

Enumeration of quadrangulations (or equivalently, 4-regular maps) has been known since Tutte's seminal works on map enumeration. However, the similar problem in the graph setting (namely, without a graph embedding) is more complex.

We present the first combinatorial scheme for counting labelled 4‐regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function of labelled 4‐regular planar graphs can be computed effectively as the solution of a system of equations, from which the coefficients can be extracted. As a byproduct, we also enumerate labelled 3‐connected 4‐regular planar graphs, and simple 4‐regular rooted maps. Finally, we can use techniques from complex analysis to obtain asymptotic estimates for the previous counting problems.

This talk is based on joint works with Marc Noy (UPC) and Clément Requilé (TUW).

S

• Justin Salez (LPMA, Université Paris VII),
  Phénomène de cutoff pour la marche aléatoire sur des grands digraphes aléatoires.
  14/04/2016.
  Transparents.

Le cutoff est une transition de phase remarquable dans la convergence de certaines chaînes de Markov vers leur loi stationnaire: la distance à l'équilibre passe brutalement de 1 à 0 lorsque le nombre d'itérations approche une valeur critique appelée temps de mélange. Découvert dans le contexte du mélange de cartes (Aldous-Diaconis, 1986), ce phénomène est désormais rigoureusement établi pour de nombreuses chaînes réversibles. Dans cet exposé, nous considérons le cadre non-réversible des marches aléatoires sur des graphes dirigés, pour lesquelles la loi stationnaire elle-même est loin d'être comprise. Dans le régime où le nombre de sommets tend vers l'infini mais où les degrés restent bornés, nous établissons le phénomène de cutoff, déterminons le temps de mélange et montrons que le profil du cutoff approche une courbe limite simple et universelle. 

Il s'agit d'un travail en collaboration avec Charles Bordenave et Pietro Caputo.

• Bruno Salvy (INRIA-Rocquencourt),
  Preuves automatiques d’identités.
  26/05/2011.
  Transparents. Synthèse.

Depuis une vingtaine d'années, le calcul formel a beaucoup progressé dans l'algorithmisation des mathématiques. En particulier, quelques idées simples mais fécondes permettent maintenant de calculer automatiquement des sommes ou des intégrales de fonctions très diverses. Nous montrerons ces idées ainsi que des progrès récents qui permettent encore d'élargir la classe de fonctions manipulables algorithmiquement.

• Gilles Schaeffer (LIX, Ecole Polytechnique),
  Mots, chemins, arbres et cartes.
  2/12/2011.
  Transparents. Synthèse.

L'exploration d'un chemin permet d'en donner un codage par un mot. L'exploration d'un arbre plan permet d'en donner un codage par un chemin. L'exploration d'une carte planaire permet d'en donner un codage par un arbre.

Ces assertions couvrent plusieurs énoncés précis de bijections entre différentes familles de chemins, d'arbres et de cartes, donc certaines obtenues encore tout récemment. Ces bijections ont de multiples applications, de la génération aléatoire au dessin automatique de graphes, en passant par la conception de structures de données compactes et l'étude des distances dans les grandes cartes aléatoires.

Mon but sera cependant plutôt de montrer l'élégance de ces résultats et des formules qui en résultent. Ceci sera l'occasion de vanter quelques outils bijectifs classiques: mots bien parenthésés, lemme cyclique, parcours en largeur et en profondeur, orientations minimales.

• Gilles Schaeffer (LIX, Ecole Polytechnique)
  From catalytic to algebraic decompositions, bijectively.
  6/06/2024.

A celebrated result of Bousquet-Mélou and Jehanne states that under reasonable combinatorial hypotheses the solutions of polynomial equations with one catalytic variable are algebraic series. We give a combinatorial derivation of this result in the case of order one catalytic equations (those involving only one univariate unknown series), in the form of a recipe to derive systematically an algebraic decomposition or a bijection with a simply generated family of trees from an order one catalytic decomposition. 

Joint work with Enrica Duchi.

• Grégory Schehr (Laboratoire de Physique Théorique et Modèles Statistiques, CNRS),
  Points quasi-extrémaux d’une marche aléatoire et variations autour de l’algorithme (optimal) d’Odlyzko pour la recherche de son maximum..
  4/12/2014.
  Transparents.

Pour un marcheur aléatoire sur $\mathbb Z$ de $n$ pas, on considère le maximum de cette marche $x_\max$ (c'est-à-dire le site visité par le marcheur situé le plus à droite).

Dans cet exposé, on s'intéresse au nombre de fois que le marcheur a visité le site d'abscisse $(x_\max - r)$, dit site quasi-extrémal. Dans la limite d'un grand nombre de pas, $n \rightarrow \infty$, le nombre de visites de sites quasi-extrémaux peut s'exprimer en fonction du temps local au voisinage du maximum du mouvement Brownien (ou densité d'états proche du maximum). Je montrerai comment on peut calculer exactement la distribution de ce temps local en étudiant des fonctionnelles du maximum du mouvement Brownien. Cette méthode est très générale et permet en particulier d'étudier assez simplement les caractéristiques de l'algorithme d'Odlyzko pour la recherche du maximum d'une marche aléatoire.

Je considèrerai ensuite une extension de cet algorithme au cas d'un pont (marche aléatoire contrainte à revenir à l'origine après n pas), ce qui nous conduira naturellement à des généralisations de la distribution d'Airy, qui décrit les fluctuations de l'aire sous une excursion Brownienne.

• Piotr Śniady (TU Munich),
  Hydrodynamic limit of Robinson-Schensted algorithm.
  5/12/2013.
  Transparents.

We consider Robinson-Schensted-Knuth algorithm (RSK) applied to random input data and study the time-evolution of the insertion tableau. We show that in the appropriate scaling limit, this insertion tableau evolves like a deterministic, stationary flow of a non-compressible liquid. Joint work with Dan Romik

• Alan Sokal (New York University and University College London),
  Coefficientwise total positivity (via continued fractions) for some Hankel matrices of combinatorial polynomials.
  5/06/2014.
  Transparents.

A matrix $M$ of real numbers is called totally positive if every minor of $M$ is nonnegative;  I will call a matrix $M$ of polynomials (in some set of indeterminates) coefficientwise totally positive if every minor of $M$ is a polynomial with nonnegative coefficients. I will call a sequence $(a_k)_{k \ge 0}$ of real numbers (or polynomials) (coefficientwise) Hankel-totally positive if the Hankel matrix $H = (a_{i+j})_{i,j \ge 0}$ associated to $(a_k)$ is (coefficientwise) totally positive. The (coefficientwise) Hankel-total positivity of a sequence $(a_k)$ implies its (coefficientwise) log-convexity, but is much stronger.  (For sequences of real numbers, Hankel-total positivity is equivalent to being a Stieltjes moment sequence.)

I will point out a simple sufficient condition for the (coefficientwise) total positivity of a Hankel matrix, based on expanding the power series $\sum_{k=0}^\infty a_k t^k$ into a Stieltjes-type continued fraction.  As a consequence I can show that a number of sequences of polynomials arising in enumerative combinatorics are coefficientwise Hankel-totally positive; this approach also gives combinatorial interpretations of all the Hankel minors, and explicit formulae for the first few leading principal minors.

I conclude by giving some examples of sequences of combinatorial polynomials that appear empirically to be Hankel-totally positive but which cannot be handled by this continued-fraction approach. Foremost among these are the inversion enumerator for trees, $I_n(y)$, which is related to the generating polynomials $C_n(v)$ of connected graphs.

• Michèle Soria (LIP6),
  Lois limites gaussiennes en Combinatoire Analytique.
  8/10/2015.
  Transparents.

La combinatoire  analytique traite de l'énumération asymptotique de structures combinatoires via les singularités analytiques de leur séries génératrices. L'étude de paramètres d'une classe combinatoire est déterminée par une  série génératrice bivariée qui est une déformation de la série génératrice de la classe d'origine et l'on peut aussi, souvent, caractériser la distribution limite du paramètre via les déformations subies par les singularités.  On étudiera dans cet exposé différents schémas combinatoires-analytiques donnant lieu à des distributions limites gaussiennes, et leur application à des classes d'arbres, de graphes, de mots, de polynômes...

• Andrea Sportiello (Université de Milan et LIPN),
  Autour de la conjecture de Razumov-Stroganov.
  2/12/2011.
  Transparents. Synthèse.

Il existe trois familles de structures aléatoires, issues de la combinatoire énumerative et de la physique statistique : (1) Un modèle physique concernant la chaine de spins quantiques de type XXZ qui peut être formulée en termes de "boucles denses de type $O(1)$", sur un cylindre semi-infini. (2) Des objets combinatoires appelés Matrices à Signes Alternant (MSA), introduits par Robbins et Rumsey il y a 25 ans, qui peuvent être interpretés comme des configurations du modèle à six sommets, un modèle intégrable dans le sens de Baxter. (3) Un modèle de pavages d'un hexagone par des losanges, pavages qui peuvent également être interpretés comme des surfaces aléatoires en trois dimensions de type Partitions Planes (plus precisement, Partitions Planes Totalement Symétriques Auto-Complémentaires, PPTSAC).

Ces modèles s'énumèrent de la même manière (autrement dit, normalisation de la fonction d'onde sur la chaine XXZ longueur $n$ = #MSA sur un carré de taille $n$ = #PPTSAC sur un hexagone de taille $2n$), de plus certains dénombrements plus raffinés sont les mêmes. En particulier, les deux premiers modèles ont des dénombrements identiques quand on se restreint aux "classes de topologie" (structures de couplage), qui sont non-locales, et en nombre $\exp(~4^n)$. Cette propriété a été conjecturée par Razumov et Stroganov en 2001, et prouvée par Cantini et moi-même, en 2010. Deux ingrédients de la preuve sont l'analyse d'une chaîne de Markov à opérateurs dans une algèbre de Temperley-Lieb associée au modèle de boucles denses, et la généralisation d'une certaine bijection naturelle sur l'ensemble des MSA introduite par Wieland et appelée "gyration".

• Andrea Sportiello (CNRS, Université Paris 13),
  Field-Theoretic approach to the Euclidean Random Assignment Problem.
  30/01/2020.
  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.

• Andrea Sportiello (LIPN),
  Many new conjectures on Fully-Packed Loop configurations.
  25/11/2021.

The Razumov--Stroganov conjecture revolves around Fully-Packed Loop configurations (FPL) and the steady state of the dense O(1) loop model (O(1)DLM). In short, it states that the refined enumeration of FPL's according to the (black) link pattern is proportional to the aforementioned steady state. It exists in two main flavours: "dihedral" (ASM, HTASM, QTASM on one side, and the O(1)DLM on the cylinder on the other side), and "vertical" (VSASM, UASM, UUASM, OSASM, OOASM on one side, and the O(1)DLM on the strip on the other side). Together with L. Cantini, we gave two proofs (in 2010 and 2012) of the conjecture in the dihedral cases, but, despite the efforts of ourselves and others, the vertical case is still unsolved. 

We recently looked back at the FPL configurations pertinent to one of the unsolved cases, namely the UASM (ASM on a 2n x n rectangle with U-turn boundary conditions on one long side), and we had the idea of looking at the refinement according to the black and white link patterns, and the overall number of loops. This doesn't seem to help in understanding the Razumov--Stroganov conjecture, but leads to many more conjectures, suggesting the existence of a remarkable generalisation of Littlewood--Richardson coefficients, somewhat in the same spirit, but apparently by a completely different mechanism, to "FPL in a triangle" studied by P. Zinn-Justin, and by Ph. Nadeau.

Work in collaboration with L. Cantini.

• Philipp Sprüssel (Institute of Optimization and Discrete Mathematics, TU Graz),
  Symmetries of plane triangulations.
  12/02/2015.
  Transparents.

Random planar graphs have attained considerable attention in the recent years. Amongst well studied properties of random planar graphs are connectedness, degree distribution and maximum degree, and the containment of subgraphs.

However, like for the Erdös-Renyi random graph all the results are for labelled planar graphs. For unlabelled planar graphs, not even their asymptotic number on a given number of vertices is known. While this number is known for labelled planar graphs, it is not possible to derive the number of unlabelled planar graphs since an unlabelled planar graph can correspond to different numbers of labelled planar graphs due to symmetries of the graph.

Triangulations are the most basic class of planar graphs and a full description of their symmetries will open the way to the enumeration of unlabelled planar graphs. In this talk I will present a constructive decomposition of triangulations with respect to their symmetries that enables us to derive an enumeration of triangulations with certain symmetries in terms of generating functions and cycle index sums.

• Dennis Stanton (University of Minnesota),
  Another $(q,t)$-world.
  2/04/2015.
  Transparents.

I'll give a survey of past/recent results involving $q$-versions of partition theorem, invariant theory of $GL_n(F_q)$, factorizations, and the $(q,t)$-binomial.

• Salvatore Stella (Dipartimento di Matematica, Universita La Sapienza),
  (Affine) generalized associahedra, root systems and cluster algebras.
  14/04/2016.

Generalized Associahedra play a central role in the theory of cluster algebras of finite type. More precisely specific geometric realizations of the normal fan to a generalized associahedron in a suitable root lattice encode many structural properties of the corresponding algebra. Such realizations hinge upon a classical result describing the orbits roots under the action of Coxeter element.

Motivated by the desire to understand the structure of affine type cluster algebra, after having recalled all the necessary notions, we will present the affine version of this classical result. We will then use it to construct affine generalized associahedra.