2014 – 2015

Le séminaire a eu lieu les jeudis 16 octobre 2014, 4 décembre 2014, 12 février 2015, 2 avril 2015, et 4 juin 2015.

16 octobre 2014

• Luigi Cantini (Laboratoire de Physique Théorique et Modélisation, Université de Cergy Pontoise),
  Inhomogenous Multispecies TASEP on a ring.
  Transparents.

I will report on some ongoing work about a multispecies version of the TASEP, a model which describes the stochastic evolution of a system of particles of different species (labeled by an integer) on a periodic oriented one dimensional lattice, where two neighboring particles exchange their position with a rate which depends on their species. For some choice of these rates the Markov matrix turns out to be integrable and for the same choice the (unnormalized) stationary probability is conjectured to show remarkable positivity and combinatorial properties. I will discuss how integrabilty leads to an interesting algebraic structure underlying this problem which allows to provide exact formulas for the stationary probability of some classes of configurations.

• Adeline Pierrot (Laboratoire de Recherche en Informatique, Université Paris-Sud),
  Trier des permutations avec des piles en série.
  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.

• Lauren K. Williams (Department of Mathematics, University of California, Berkeley),
  Combinatorics of positroids.

Positroids are a class of matroids which were studied extensively by Postnikov, in connection with the positive Grassmannian. In joint work with Federico Ardila and Felipe Rincon, we prove a structure theorem for positroids: each positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then freely placing the structure of a connected positroid on each of the blocks. This allows us to make a link with free probability. We also prove da Silva's 1987 conjecture that any positively oriented matroid is a positroid; that is, it can be realized by a set of vectors in a real vector space. It follows from this and an earlier topological result of the speaker that the positive matroid Grassmannian (or positive MacPhersonian) is homeomorphic to a closed ball.

4 décembre 2014

• Sylvie Corteel (Laboratoire d’Informatique Algorithmique: Fondements et Applications, CNRS),
  Diamants aztèques, Partitions pyramides, Pavages pentus, et Gares de triage.
  Transparents.

Je parlerai de modèles généraux de dimères (ou pavages) sur certains graphes planaires bipartis, dont l'énumération est exactement soluble. Ces modèles appelés «pavages pentus» (pour le réseau carré) et «graphes de gare de triage» (dans le cas général) généralisent à la fois le diamant aztèque, les partitions pyramides, et les partitions planes. Ils se reformulent en termes de modèles de particules, puis de «processus de Schur» via la correspondance Boson-Fermion.

Grâce à une approche par matrice de transfert et à la construction de nouveaux opérateurs de localisation, on obtient non seulement l'énumération mais aussi la matrice Kasteleyn inverse et les corrélations (déterminantales) entre les dimères.

Les deux articles sous-jacents sont communs avec Jérémie Bouttier et Guillaume Chapuy pour le premier, et avec ces deux auteur.e.s plus Cédric Boutillier et Sanjay Ramassamy pour le second.

• Nicolas Curien (Département de Mathématiques de l’Université Paris-Sud Orsay),
  Épluchage des cartes planaires et applications (On the peeling process of random maps).

The spatial Markov property of random planar maps is arguably one of the most useful properties of these random lattices. Roughly speaking, it says that after exploring a region of the map, the law of the remaining part only depends on the perimeter of the discovered region. It has been first heuristically used by Watabiki in the physics literature under the name of ``peeling process'' but was rigorously defined in 2003 by Angel in the case of the Uniform Infinite Planar Triangulation (UIPT). Since then, it has been used to derive information about the metric, (bernoulli and first passage) percolation, simple random walk and recently about the conformal structure of random planar maps. It is also at the core of the construction of "hyperbolic" random maps. In this talk, we will introduce smoothly the peeling process and present some of its main applications.

• 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.
  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.

12 février 2015

• Vincent Pilaud (Laboratoire d’Informatique de l’École polytechnique – LIX, CNRS),
  Réalisations géométriques des associaèdres de graphe.
  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.

• Maria Ronco (Institute of Mathematics and Physics, Universidad de Talca),
  Structures algébriques associées au associaèdres de graphes.
  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.

• Philipp Sprüssel (Institute of Optimization and Discrete Mathematics, TU Graz),
  Symmetries of plane triangulations.
  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.

2 avril 2015

• Dennis Stanton (University of Minnesota),
  Another $(q,t)$-world.
  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.

• Philippe Duchon (LABRI, Université de Bordeaux),
  Simulation combinatoire exacte de variables aléatoires continues.
  Transparents.

Quelles lois de probabilités continues peut-on simuler exactement si l'on s'interdit l'usage de fonctions transcendantes, voire, des opérations arithmétiques sur les nombres non entiers? On pourrait penser que de telles contraintes rendent à peu près tout impossible, mais il n'en est rien. En s'inspirant d'un déjà vieil algorithme pour la loi exponentielle, dû à John von Neumann, on montre que de nombreuses lois continues, incluant la loi normale, admettent des algorithmes de simulation exacte "purement combinatoires".

• Boris Adamczewski (Institut de Mathématiques de Marseille, CNRS),
  Congruences « à la Lucas » et indépendance algébrique de G-fonctions.

Les diagonales de fractions rationnelles forment une classe de fonctions analytiques se situant au confluent de plusieurs grands thèmes : la combinatoire énumérative, la théorie des équations différentielles, l'arithmétique, la géométrie algébrique et l'informatique théorique. Lorsque leurs coefficients sont des nombres rationnels, ces séries ont la propriété remarquable d'être algébriques modulo presque tout nombre premier p. Cette propriété implique l'existence de congruences générales satisfaites par leurs coefficients. Dans de nombreux cas, on obtient en fait des congruences bien plus spécifiques et bien connues des combinatoristes, du type de celles introduites par Lucas. J'expliquerai comment en déduire des résultats d'indépendance algébrique pour certaines familles de G-fonctions sans avoir recours à la théorie de Galois différentielle.

Il s'agit de travaux communs avec J. Bell et E. Delaygue.

4 juin 2015

• Imre Bárány (Hungarian Academy of Sciences),
  Tensors, colours, octahedra.

• Maciej Dołęga (LIAFA),
  When orientability makes difference ?.
  Transparents.

In this talk I am going to present two problems related to combinatorics of maps, which are graphs embedded into a surface. In both problems the main question is on combinatorics of non-orientable maps. While the first problem is already solved and the solution turns out to be independent of being orientable or not, the second problem is still open and I will discuss some partial results showing that orientable maps seem to be very different than non-orientable ones.

• Béatrice de Tillière (Laboratoire de Probabilités et Modèles Aléatoires, UPMC),
  Le Laplacien Z-invariant massique sur les graphes isoradiaux.
  Transparents.

Après avoir expliqué la notion de Z-invariance pour les modèles de mécanique statistique, nous introduisons une famille à un paramètre (dépendant du module elliptique) de Laplaciens massiques Z-invariants définis sur les graphes isoradiaux. Nous démontrons une formule explicite pour son inverse, la fonction de Green massique, qui a la propriété remarquable de ne dépendre que de la géométrie locale du graphe.  Nous expliquerons les conséquences de ce résultat pour le modèle des forêts couvrantes, en particulier la preuve d'une transition de phase d'ordre 2 avec le modèle des arbre couvrants
critiques sur les graphes isoradiaux, introduit par Kenyon. Finalement, nous considérons la courbe spectrale de ce Laplacien massique et montrons qu'il s'agit d'une courbe de Harnack de genre 1. 

Il s'agit d'un travail en collaboration avec Cédric Boutillier et Kilian Raschel.