2015 – 2016

Le séminaire a eu lieu les jeudis 8 octobre 2015, 3 décembre 2015, 4 février 2016, 14 avril 2016, et 2 juin 2016.

8 octobre 2015

  • Frédéric Chyzak (INRIA Saclay),
    Explicit generating series for small-step walks in the quarter plane.
    Transparents.
Lattice walks occur frequently in discrete mathematics, statistical physics, probability theory, and operational research.  The algebraic properties of their enumeration generating series vary greatly according to the family of admissible steps chosen to define them: their generating series are sometimes rational, algebraic, or D-finite, or sometimes they possess no apparent equation.  This has recently motivated a large classification effort.  Interestingly, the equations involved often have degrees, orders, and sizes, making calculations an interesting challenge for computer algebra.

In this talk, we study nearest-neighbours walks on the square lattice, that is, models of walks on the square lattice, defined by a fixed step set that is a subset of the 8 non-zero vectors with coordinates 0 or ±1.  We concern ourselves with the counting of walks constrained to remain in the quarter plane, counted by length.  In the past, Bousquet-Mélou and Mishna showed that only 19 essentially different models of walks possess a non-algebraic D-finite generating series; the linear differential equations have then been guessed by Bostan and Kauers. In this work in progress, we give the first proof that these equations are satisfied by the corresponding generating series.  This allows to derive nice formulas for the generating series, expressed in terms of Gauss' hypergeometric series, to decide their algebraicity or transcendence.  This also gives hope to extract asymptotic formulas for the number of walks counted by lengths.

Based on work in progress with Alin Bostan, Mark van Hoeij, Manuel Kauers, and Lucien Pech.
  • Loïc Foissy (LPMA, Calais),
    Algèbre de Hopf des topologies finies et P-partitions.
    Transparents.
Stanley a introduit dans sa thèse l'ensemble des $P$-partitions attachées à un ensemble partiellement ordonné (poset) étiqueté $P$ et a donné une décomposition de cet ensemble indexée par les extensions linéaires de $P$. Cette décomposition peut se réécrire sous forme algébrique à l'aide d'un morphisme entre l'algèbre de Hopf des posets de Malvenuto et Reutenauer vers l'algèbre de Hopf des fonctions quasi-symétriques. Les topologies finies sont des objets plus généraux que les posets : nous les munissons d'une structure d'algèbre de Hopf et nous étendons les définitions de Stanley pour obtenir de nouveaux morphismes, ainsi qu'un isomorphisme entre le produits de battage et de quasi-battages sur les mots tassés.

Travail en collaboration avec Claudia Malvenuto et Frédéric Patras.
  • Michèle Soria (LIP6),
    Lois limites gaussiennes en Combinatoire Analytique.
    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...

3 décembre 2015

  • Timothy Budd (Université de Copenhague),
    The peeling process on random planar maps with loops.
    Transparents.
We consider random Boltzmann-distributed bipartite planar maps coupled to $O(n)$ loop models. Inspired by recent progress by Borot and Bouttier on nesting statistics, we show that the perimeter associated to a particular exploration process of such surfaces, the peeling process, can be conveniently described by conditioned random walks on the integers. The corresponding scaling limits in terms of positive self-similar Markov processes can be explicitly identified, and correspond to stable processes which are confined to the half-line with non-standard, but quite natural, boundary conditions. The self-similarity of these processes allows us to employ modern machinery to compute distributions of related exponential integrals, which can be given a natural interpretation in terms of the geometry of the random surfaces with loops.
  • Yann Bugeaud (IRMA, Strasbourg),
    Sur le développement décimal de $e$.
Il est fort probable que $e$, $\log 2$ et $\sqrt 2$ soient tous trois normaux en base $10$, c'est-à-dire que, pour tout entier $k$, tout bloc de $k$ chiffres $0, 1, … , 9$ apparaisse dans leur développement décimal avec la fréquence $1/10^k$. De tels résultats semblent cependant complètement hors de portée. Nous nous intéressons à des questions apparemment plus simples : nous prenons un point de vue de combinatoire des mots et, pour tout entier $b$, regardons le développement en base $b$ d'un nombre réel comme un mot infini sur l'alphabet $0, 1, ... , b-1$. Nous montrons que pour $e$, $\log(2016/2015)$ et tout nombre algébrique irrationnel (entre autres nombres classiques), ces mots infinis ne sont pas "trop simples", dans un sens précis. Aucune connaissance particulière n'est requise pour suivre l'exposé.
  • Jehanne Dousse (Université de Zürich),
    La méthode du cercle à deux variables.
    Transparents.
La méthode du cercle a été inventée par Hardy et Ramanujan pour calculer l'asymptotique de $p(n)$, le nombre de partitions d'un entier $n$. Plus généralement, elle permet de calculer l'asymptotique des fonctions dont la série génératrice est une forme modulaire.

Dans cet exposé, nous présentons une nouvelle généralisation de la méthode du cercle qui permet de calculer l'asymptotique à deux variables de quantités dont les séries génératrices sont des formes de Jacobi ou de mock Jacobi. Nous montrons en particulier comment elle permet de donner une formule asymptotique pour le crank et le rang des partitions d'entiers, résolvant ainsi une conjecture de Dyson de 1989.

4 février 2016

  • Nathanaël Enriquez (Modal’X & LPMA, Université Paris X),
    Combinatoire des lignes convexes à sommets entiers dans le plan.
On se pose la question de l'asymptotique du nombre de lignes polygonales croissantes convexes à sommets entiers joignant l'origine au point de coordonnées $(n,n)$. Un équivalent logarithmique avait été trouvé indépendamment et par des méthodes différentes par Barany, Vershik et Sinai en 1996. Nous suivons l'approche de Sinai, qui introduit un modèle de physique statistique relatif à ce problème. Dans ce modèle, nous parvenons à donner une représentation intégrale de la fonction de partition faisant intervenir la fonction zeta. Nous en déduisons un véritable équivalent du nombre de lignes, mettant en jeu notamment les zéros de la fonction zeta.
  • Hugo Parlier (Université de Fribourg, Suisse),
    Combinatorial moduli spaces.
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.
  • Matthieu Josuat-Vergès (Université Paris-Est Marne-la-Vallée),
    Factorisations minimales de cycles, une série multivariée.
    Transparents.
Pour factoriser le long cycle $(1,2,...,n)$ en produit de transpositions dans le groupe symétrique, il faut au moins $n-1$ facteurs. Le nombre de factorisations est alors $n^{n-2}$, et ces factorisations sont dites minimales. Et si on compte les factorisations du long cycle en $k$ cycles de longueur fixées $(a_1,...,a_k)$, avec une condition de minimalité, le nombre est $n^{k-1}$. De nombreuses généralisations de ce genre de résultats existent, par exemple lorsqu'on factorise une permutation quelconque, et ces problèmes ont des interprétations géométriques (nombres de Hurwitz, cartes). Ici, nous montrons qu'on peut raffiner le résultat sur $n^{k-1}$, en considérant une série génératrice multivariée (au lieu d'un simple comptage), qui se factorise dans les polynômes multivariés.

Il s'agit d'un travail en collaboration avec Philippe Biane.

14 avril 2016

  • Justin Salez (LPMA, Université Paris VII),
    Phénomène de cutoff pour la marche aléatoire sur des grands digraphes aléatoires.
    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.
  • Carine Pivoteau (LIGM, Université Paris-Est Marne-la-Vallée),
    De bonnes prédictions valent bien quelques comparaisons.
    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.
  • Salvatore Stella (Dipartimento di Matematica, Universita La Sapienza),
    (Affine) generalized associahedra, root systems and cluster algebras.
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.

2 juin 2016

  • Lucas Gerin (CMAP, Ecole Polytechnique),
    Processus d’Hammersley discret et sous-suites croissante.
À la fin des années 60, Hammersley a introduit un processus à temps et espace continus pour étudier le comportement de la plus longue sous-suite croissante d’une permutation aléatoire uniforme. Plus récemment, deux variantes discrètes de ce processus ont été introduites, ces variantes comptent des objets semblables à des sous-suites croissantes. En étudiant les mesures stationnaires de ces processus nous revisitons et unifions ces résultats.

Travail en commun avec A.-L.Basdevant, N.Enriquez, J.-B.Gouéré.
  • Lenka Zdeborova (Institut de Physique Theorique, CEA/SACLAY),
    Clustering of sparse graphs: From phase transitions to optimal algorithms.
    Transparents.
A central problem in analyzing networks or graphs is partitioning them into modules or communities, i.e. groups with a statistically homogeneous pattern of connections to each other or to the rest of the network. A principled approach to address this problem is to fit the network on a stochastic block model, this task is, however, belongs to the class of very hard algorithmic problems. Still it can be reformulated as the equilibrium statistical mechanics of a particular mean field spin glass model. We apply the cavity method that is standard in studies of spin glasses and structural glasses and compute the associated phase diagram of the problem. We describe consequences of this result for algorithmic tractability of the clustering problem. Further, we take advantage of the insight gained by the analysis to introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. We show that the algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit.
  • Nicolas Thiéry (LRI, Université Paris 11),
    Nombre moyen de tresses dans les mots réduits et tableaux justifiés à droite.
    Transparents.
En 2005, Vic Reiner a démontré que, en moyenne, l'on peut appliquer exactement une relation de tresse non triviale à un mot réduit de l'élément le plus long du groupe symétrique. Nous donnons une preuve bijective du résultat analogue lorsque l'on se restreint à la classe de commutation du mot réduit lexicographiquement minimal. Cette bijection fait intervenir, via les empilements de pièces de Viennot, un énoncé équivalent sur les tableaux standards justifiés à droite, et les opérateurs de promotion sur ceux-ci. 

Travail commun avec Anne Schilling, Graham White et Nathan William.