Voici la liste alphabétique des anciens orateurs au séminaire avec, lorsque ceux-ci sont disponibles, leurs transparents et la synthèse de l'exposé.

  • Boris Adamczewski (Institut de Mathématiques de Marseille, CNRS), Congruences "à la Lucas" et indépendance algébrique de G-fonctions, 2/04/2015
    .

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.

  • Marie Albenque (Laboratoire d'Informatique de l'École Polytechnique), Bijections entre cartes planaires et arbres bourgeonnants, 6/02/2014
    , Transparents.

Les arbres bourgeonnants sont des arbres portant des décorations qui permettent de leur associer une carte planaire. Trouver des bijections entre des familles de cartes et d'arbres bourgeonnants fournit un outil précieux dans l'étude des cartes planaires; cela permet en effet de ramener l'étude de la carte à celle de l'arbre associé, souvent plus simple.
De nombreuses bijections ont été obtenues ces 15 dernières années et dans cet exposé je présenterai un schéma général qui, en se spécialisant, permet d'obtenir beaucoup de ces constructions comme des cas particuliers ainsi que de nouvelles constructions. Ce résultat s'inscrit dans la lignée de travaux par Bernardi et Fusy et qui visent à unifier les bijections existantes entre cartes et arbres.
Une question fondamentale, encore largement ouverte, est maintenant de comprendre comment les distances entre deux sommets de la carte peuvent être retrouvées à partir de l'arbre bourgeonnant. J'expliquerai comment cette question peut être résolue dans le cas des triangulations simples.
Cet exposé repose sur des travaux avec Louigi Addario-Berry et Dominique Poulalhon

  • Federico Ardila (SFSU USA), Arithmetic Tutte polynomials of classical Coxeter groups, 28/03/2013
    .

Arithmetic Tutte polynomials of classical Coxeter groups The Tutte polynomial is a very important combinatorial invariant of an arrangement of hyperplanes. It encodes a great amount of enumerative, topological, and algebraic information about the arrangement - whether the underlying vector space is real, complex, or finite. The arithmetic Tutte polynomial, introduced by Moci in 2009, plays the analogous role for toric arrangements. We introduce a "finite field method" for computing arithmetic Tutte polynomials, and use it to compute these polynomials for the classical Coxeter groups. The talk will not assume previous knowledge of the subject.
Joint work with Federico Castillo (Los Andes / UC Davis) and Mike Henley (SFSU).

  • Imre Bárány (Hungarian Academy of Sciences), Tensors, colours, octahedra, 4/06/2015
    .
  • Frédérique Bassino (LIPN, Paris Nord), Enumération asymptotique d'automates finis, 24/05/2012
    , Transparents.

Cet exposé portera sur l'énumération d'automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l'ensemble respectivement des états initiaux et des états terminaux). Nous présenterons les résultats obtenus depuis la fin des années 70 concernant l'énumération des automates détermnistes et accessibles, i.e. dans lesquels tout état peut-être atteint par un chemin partant de l'unique état initial. Nous déterminerons ensuite précisément la proportion asymptotique d'automates minimaux parmi les automates déterministes accessibles et complets. Toutes ces estimations peuvent être obtenue grâce à une interprétation combinatoire des propriétés structurelles des automates et des bijections pour se ramener à l'étude combinatoire de tableaux particuliers.

  • Michel Bauer (IPHT CEA/DSM), Variables échangeables, martingales et mesures non-destructives en mécanique quantique, 27/09/2012
    , Synthèse.

Plus de 80 ans après la découverte des lois de la mécanique quantique, celles-ci continuent de susciter l'étonnement. La notion de mesure en particulier, reste très mystérieuse. Des expériences récentes très simples et belles, que nous décrirons brièvement, permettent de lever légèrement un coin du voile. Après avoir présenté, pour des non-physiciens, les notions de base de la mécanique quantique, nous montrerons pourquoi l'interprétation de ces expériences est étroitement liée à la théorie des variables échangeables, au théorème de de Finetti et au théorème de convergence des martingales.

  • François Bergeron (UQAM Montréal), Combinatoire de Catalan et espaces de polynômes harmoniques diagonaux, 2/12/2011
    , Transparents, Synthèse.

Au cours des vingt dernières années, l'étude des espaces de polynômes harmoniques diagonaux a mené à une étude fine de la combinatoire des fonctions de stationnement (parking functions), et de paramètres sur celles-ci. Nous allons présenter certains de ces développements, avec des extensions qui font intervenir l'ordre de Tamari ainsi que ses extensions aux cas de chemins de Dyck généralisés. Nous conclurons en abordant de nouveaux problèmes combinatoires soulevés par cette étude.

  • Valerie Berthé (LIAFA), Dynamique euclidienne : une approche symbolique, 31/01/2013
    , Transparents.

La transformation de Gauss (qui sous-tend le développement en fraction continue) a été très efficacement étudiée par Baladi-Vallée sous l'angle de l'analyse dynamique d'algorithmes. Le but de cet exposé est de montrer comment revisiter les résultats obtenus dans ce contexte sous l'angle de la dynamique symbolique.

  • Philippe Biane (IGM,MLV), Polynômes orthogonaux et équations de Painlevé discrètes, 7/10/2011
    , Transparents, Synthèse.

Les polynômes orthogonaux ont de riches propriétés combinatoires. Dans cet exposé je considérerai des polynômes orthogonaux sur le cercle unité, proches de ceux d'Askey-Wilson mais qui ne s'y ramènent pas. Les coefficients de leurs relations de récurrence ne sont pas donnés par une formule explicite mais sont déterminés par une autre relation de récurrence qui est en fait une équation de Painlevé discrète (j'expliquerai dans l'exposé ce que sont les équations de Painlevé). Cette équation de récurrence provient d'une structure géométrique remarquable qui fait intervenir les systèmes de racines affines $D_5$ et $A_3$, plongés de façon orthogonale dans $E_8$.

  • Gaetan Borot (Max Planck Institute for Mathematics, Bonn), The ABCD of topological recursion, 30/3/2017
    .

I will give a short introduction to the formalism of topological recursion, which has been simplified and generalised by a recent proposal by Kontsevich and Soibelman: no geometry is necessary to present it, only algebra and combinatorics. The initial data is now a collection (L_i)_i of differential operators in many variables, which are atmost quadratic in derivatives and satisfy Lie algebra commutation relations. The topological recursion then produces the Taylor coefficients of the common solution to the equations {L_i Z = 0}_{i}. For the simplest initial data, Z just counts trivalent graphs with certain conditions, and can be exactly computed in terms of Whittaker functions. In general, the topological recursion appears as a sum over these graphs.
In fact, finding initial data is not a priori an easy task ! I will present 3 classes of initial data, respectively obtained from the data of a Frobenius algebra, of a non-commutative Frobenius algebra, and of the vector space of formal series with coefficients in a Frobenius algebra. This third class of examples contains the topological recursion from the former Eynard and Orantin perspective -- so, I will review some already known applications of topological recursion to various problems of enumerative geometry, in light of Kontsevich-Soibelman approach, which is hopefully combinatoralist-friendly.
If time permits I will pose and motivate open questions about large genus asymptotics.
Based on joint work with J.E. Andersen, L. Chekhov and N. Orantin.

  • Alin Bostan (SpecFun, INRIA Saclay), Computer Algebra for Lattice Path Combinatorics, 28/03/2013
    , Transparents, Synthèse.

Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra methods have been used to explore and solve a number of difficult questions related to lattice walks. In this talk, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

  • Mireille Bousquet-Mélou (LABRI, Bordeaux), Sur les chemins auto-évitants, 7/10/2011
    , Transparents.

Un chemin auto-évitant sur un réseau de dimension $d$ est une marche qui ne visite jamais deux fois le même sommet. Ces objets naturels sont étudiés en combinatoire, en probabilités, et en physique statistique, mais leurs propriétés sont mal connues, surtout en petite dimension $(d=2,3)$. On présentera d'abord une courte synthèse des résultats et conjectures existants — remarquables pour la dimension 2. Puis on discutera de la recherche de familles exactement résolubles de tels chemins.

  • Jérémie Bouttier (IPHT, CEA et LIAFA, CNRS et Université Paris Diderot), Des boucles sur les cartes aléatoires, 20/10/2011
    , Transparents.

Introduit en physique statistique, le modèle $O(n)$ peut être formulé en termes de boucles évitantes (ou cycles disjoints) sur un graphe, $n$ jouant le rôle d'un poids par boucle. Ce modèle a été naturellement considéré sur les cartes aléatoires et, dans certains cas, "résolu" à l'aide d'intégrales matricielles. Nous proposons ici une nouvelle approche combinatoire à ce modèle. Le problème combinatoire consiste à énumérer les cartes planaires munies d'une configuration de boucles évitantes. A une telle carte, l'opération consistant à effacer toutes les boucles et leurs intérieurs associe une autre carte, sans boucles mais à "trous". Cette opération n'est bien sûr pas bijective, mais donne une décomposition qui se traduit par des relations de substitutions entre séries génératrices, que nous pouvons résoudre explicitement dans certains cas. En termes probabilistes, notre décomposition établit un lien entre le modèle $O(n)$ et le modèle des "cartes stables" introduit par Le Gall et Miermont.
Travail en collaboration avec G. Borot et E. Guitter.

  • Cédric Boutillier (LPMA, Paris 6), The Z-invariant Ising model on isoradial graphs, 30/3/2017
    , Transparents.

The Ising model is a mathematical model for ferromagnetism in which spins are located at vertices of a graph. For a large class of embedded planar graphs, called isoradial graphs, local weights for this model can be found so that an integrability condition (the Yang-Baxter relation) is satisfied. The model is then said to be Z-invariant.
In a joint work with Béatrice de Tilière (Créteil) and Kilian Raschel (Tours), we study the Z-invariant Ising model on infinite isoradial graphs. We show that certain probabilistic quantities have a local expression in terms of the geometry of the embedding of the graph. Our main tool is Fisher's bijection between the Ising model and a dimer model on a decorated graph. We will discuss the properties of this model in connection with the geometry of an algebraic curbe naturally associated to the dimer model.

  • Mathilde Bouvel (Université de Zurich), "Operators of equivalent sorting power, and related Wilf-equivalences", 5/12/2013
    , Transparents.

Permutation patterns and permutation classes (defined by the avoidance of a set of patterns) have been first introduced in the seventies, in connection with the analysis of sorting devices and partial sorting algorithm. Enumerative combinatorics soon became interested in the study of permutation classes, and many so-called Wilf-equivalences have been proved. Two permutation classes (or two sets of excluded patterns that characterize them) are said Wilf-equivalent when they are enumerated by the same sequence.

In this talk, I will start with a (biased) panorama of these early results on permutation classes, and present new results obtained first with Olivier Guibert (LaBRI, Bordeaux) and then with Michael Albert (Univ. Otago, New Zealand). The main point of this work is the study of some partial sorting operators. But it has unexpected enumerative consequences, as our study allows us to deduce families of Wilf-equivalences.

  • Nicolas Broutin (INRIA Rocquencourt), Recherches partiellement spécifiées dans les arbres multidimensionnels, 20/10/2011
    , Transparents.

Nous considérons la recherche d'éléments dans des structures de données multidimensionnelles (quad trees, k-d trees), en particulier lorsque certaines coordonnées ne sont pas spécifiées (partial match query). Nous supposons que les données consistent en un ensemble de points uniformes dans le carré unité. Pour ce modèle, dans une structure contenant $n$ points, Flajolet et Puech ont montré que le nombre de noeuds $C_n(U)$ à visiter pour répondre à une requête demandant l'ensemble des données dont la première coordonnée est $x=U$ est tel que $E[C_n]\sim \kappa n^{\beta}$, où $\kappa$ et $\beta$ sont des constantes explicites. Nous développons une approche basée sur l'analyse des coûts $C_n(s)$ pour des requêtes à $x=s$ fixé. Nous donnons en particulier des estimations précises de la variance et de la distribution limite de $C_n(s)$ lorsque $n\to\infty$. Nos résultats permettent de décrire un processus limite pour $C_n(s)$ lorsque $s$ varie dans $(0,1)$. Nous en déduisons par exemple que le coût de la pire requête est aussi de la forme $\kappa' n^{\beta}$, pour la puissance $\beta$ que précédemment.
Travail en collaboration avec Ralph Neininger et Henning Sulzbach.

  • Timothy Budd (Université de Copenhague), The peeling process on random planar maps with loops, 3/12/2015
    , 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$, 3/12/2015
    .

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

  • Luigi Cantini (Laboratoire de Physique Théorique et Modélisation, Université de Cergy Pontoise), Inhomogenous Multispecies TASEP on a ring, 16/10/2014
    , 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.

  • Pierre Cartier (IHES), Algèbres de Hopf combinatoires, 26/5/2011
    , Synthèse.

Les opérations de contraction et d'insertion dans les graphes — selon la prédiction de G.-C. Rota — conduisent à des algèbres de Hopf. On décrira deux exemples principaux, liés aux diagrammes de Feynman et à la monodromie d'équations différentielles. On explicitera les théorèmes de structure sous-jacents.

  • Guillaume Chapuy (LIAFA, CNRS), Une formule pour compter les cartes de genre positif, 3/04/2014
    , Transparents.

Je parlerai de cartes, qui sont des graphes dessinés sur des surfaces orientables. L'énumération de ces objets est un domaine très riche qui a fait l'objet de nombreux travaux. Je donnerai une formule extrêmement simple, apparemment nouvelle, obtenue récemment avec Sean Carrell (Waterloo) permettant d'énumérer les cartes orientables par le genre et le nombre d'arêtes. Cette formule repose sur le fait «classique» que les séries génératrices multivariées de cartes et objets apparentés sont des tau-fonctions de la hiérarchie KP. J'essaierai de dédramatiser un peu cet énoncé en donnant une idée brève de la combinatoire algébrique sur laquelle il repose. Puis je tenterai de montrer comment obtenir une formule toute simple à partir de là dans le cas des cartes générales. Si le temps le permet je tenterai de mettre ce résultat en perspective en le comparant avec ce que l'on peut dire via d'autres approches, bijectives ou à base d'équations de Tutte/boucles. Bien que notre formule soit de saveur très combinatoire, je ne parlerai pas de son interprétation bijective, car je ne la connais pas!

  • Philippe Chassaing (IECN), The height of the Lyndon tree, 31/01/2013
    , Transparents, Synthèse.

We consider the set $L_n$ of n-letters long Lyndon words on the alphabet $\{0,1\}$. For a random uniform element $l_n$ of the set $L_n$, the binary tree obtained by successive standard factorization of $l_n$ and of the factors produced by these factorization is the Lyndon tree of $l_n$. We prove that the height $H_n$ of the Lyndon tree of $l_n$ satisfies $\lim_n (H_n/ \ln n) = \Delta$, in which the constant $\Delta$ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers ($\Delta \approx 5.091\ldots$). The convergence is the convergence in probability of random variables.
Joint work with Lucas Mercier.

  • Frédéric Chapoton (Institut Camille Jordan - ICJ, CNRS), Combinatoire des couplages et des ensembles indépendants dans les arbres, 3/02/2014
    , Transparents.

En théorie des graphes, les notions de couplage et d'ensemble indépendant sont très classiques et fondamentales. Dans cet exposé, je présenterai une description élégante (due à Zito et Bauer-Coulomb) de ce qui se passe dans les arbres, qui fait intervenir un tri-coloriage canonique des sommets. Il sera notamment question de diagrammes de Feynman, et d'une relation amusante entre le principe de dissymétrie et le Lagrangien d'une théorie quantique des champs. On esquissera aussi une relation avec la géométrie de certaines variétés.

  • Brigitte Chauvin (Université de Versailles), Des Arbres dans les Urnes de Pólya et réciproquement, 6/12/2012
    , Synthèse.

Les urnes de Pólya se prêtent à de nombreuses approches : par combinatoire analytique, on obtient une description exacte de la composition de l'urne à un instant $n$ fini. C'est plutôt une description par tranche. Quand les systèmes différentiels obtenus se résolvent, c'est magique.
La vision probabiliste conduit plutôt à des résultats sur le comportement global limite de l'urne quand $n$ tend vers l'infini. Nous verrons qu'une transition de phase existe, entre les « petites urnes » à asymptotique Gaussienne et les «grandes urnes», pour lesquelles l'asymptotique du vecteur composition de l'urne fait apparaître une variable aléatoire limite $W$ dont la loi est non classique. L'étude probabiliste repose sur la mise en évidence de la structure arborescente de l'évolution de l'urne. Un raisonnement de type «diviser pour régner» conduit à écrire des équations de point fixe en loi pour $W$, qui ont un intérêt en elles-mêmes et qui donnent des indications sur $W$ (densité, moments) et aussi des conjectures. Enfin plonger l'urne en temps continu produit un processus de branchement dont les agréables propriétés d'indépendance conduisent à d'autres équations de point fixe en loi, pas tout à fait les mêmes qu'en temps discret. Lorsqu'on traduit ces équations sur la transformée de Fourier de $W$, le système différentiel obtenu se résout, faisant avancer la compréhension de $W$.
Travail commun avec Quansheng Liu, Cécile Mailler et Nicolas Pouyanne.

  • Frédéric Chyzak (INRIA Saclay), Explicit generating series for small-step walks in the quarter plane, 8/10/2015
    , 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.

  • Julien Clément (GREYC, Caen), Trier des clés: une analyse en moyenne du nombre de comparaisons de symboles, 29/03/2012
    .

On aborde classiquement l'analyse en moyenne d'algorithmes en s'intéressant à la complexité mesurée en nombre de comparaisons. On a alors des résultats de complexité du type "tel algorithme est en $O(n \log n)$ en moyenne" (par exemple Quicksort pour citer un des plus connus). Ces affirmations se basent sur des hypothèses spécifiques -- que les comparaisons entre les données (ou clés), pour les deux premiers, et les comparaisons entre symboles pour le troisième ont un coût unitaire -- et elles ont le mérite évident de présenter un tableau facile à assimiler de la complexité des algorithmes de tri. Cependant, ces hypothèses simplificatrices sont de fait discutables: elles ne permettent pas de comparer précisément les avantages et inconvénients d'algorithmes reposant sur des principes différents (i.e., ceux qui comparent les clés et ceux qui utilisent une représentation sous forme de suite de symboles) d'une manière qui soit totalement satisfaisante à la fois du point de vue de la théorie de l'information et du point de vue algorithmique. En effet, d'abord le calcul n'est pas vu à son niveau le plus fondamental, c'est-à-dire, par la manipulation de symboles élémentaires tels que le bit, l'octet, le caractère ou le mot-machine. De plus les analyses simplifiées ne sont pas toujours informatives dans beaucoup d'applications (bases de données ou traitement de la langue naturelle), où l'information est de nature hautement 'non atomique' , au sens qu'elle ne se réduit pas à un seul mot-machine. J'exposerai à l'aide de plusieurs exemples d'algorithmes de tri une méthode qui permet d'analyser en moyenne le nombre de comparaisons de symboles. Les clés à trier sont vues comme des séquences de symboles produit par un modèle de source général. Pour des sources particulières (comme les sources sans mémoire) on accède à une analyse fine (avec le calcul de constantes explicites...) de certains de ces algorithmes de tri.
En collaboration avec Brigitte Vallée, Thu Hien Nguyen-Thi (et initié avec Philippe Flajolet).

  • Eric Colin de Verdière (CNRS, ENS), Théorèmes à la Helly, motifs d'intersections et combinatoire topologique, 3/10/2013
    , Transparents.

Le théorème de Helly (1923) énonce une propriété des motifs d'intersections des familles (finies) de convexes de $R^d$: Pour vérifier qu'une telle famille est d'intersection non vide, il suffit de vérifier que chaque sous-famille de taille au plus $d+1$ est d'intersection non vide.
On peut représenter combinatoirement les motifs d'intersections d'une famille quelconque d'ensembles à l'aide d'un complexe simplicial, son _nerf_. Le théorème du nerf en combinatoire topologique permet de montrer une version topologique du théorème de Helly.
Je décrirai une généralisation de ce dernier résultat à des familles d'objets non connexes de $R^d$, qui repose sur une variante de la notion de nerf et sur une extension d'un théorème de projection dû à Kalai et Meshulam, et des applications en géométrie combinatoire.
Travail en commun avec Grégory Ginot et Xavier Goaoc.

  • Filippo Colomo (Istituto Nazionale di Fisica Nucleare, Firenze), Limit shapes of large Alternating Sign Matrices, 3/04/2014
    , Transparents.

Alternating Sign Matrices (ASMs) are square matrices satisfying the following conditions: a) possible entries are 0,1,-1; b) non-zero entries alternate in sign along each row and column; c) the sum of entries of any fiven row or column is equal to 1. In the limit of large dimensions ASMs are known to develop a limit shape, with the appearance of four corner regions containing only 0's, and sharply separated from a central and approximately circular region, containing also non-zero entries. The original derivation of an analytic expression for the curve describing the limit shape is reviewed. The corresponding expression for the case of weighted enumerations of ASMs is provided as well. An alternative derivation is discussed, which allows for extension of the above results to ASMs of generic shape (more precisely, to generic shape subregions of the square lattice graph, with an entry associated to each vertex, and all entries satisfying ASMs'conditions).

Joint works with Andrei Pronko, Paul Zinn-Justin, Andrea Sportiello

  • Robert Cori (Labri-Bordeaux), Développements récents dans le modèle combinatoire du tas de sable sur un graphe, 3/11/2011
    , Transparents, Synthèse.

Dans le modèle combinatoire du tas de sable on affecte à chaque sommet d'un graphe un entier positif ou nul censé représenter un nombre de grains situés sur le sommet en question. Une règle d'éboulement permet de faire passer des grains d'un sommet à ses voisins. Deux généralisations du modèle avec l'affectation d'entiers pouvant être négatifs ont été considérées par différents auteurs. La première peut être interprétée par des particules et anti-particules qui se détruisent mutuellement lors d'un éboulement. La seconde comme des soldes de comptes en banque qui peuvent être redistribués aux voisins ou bien faire l'objet d'un versement collectif. Il sera question dans cet exposé de résultats récents obtenus dans le cadre de ces deux modèles et en particulier d'un article de M. Baker et S. Norine dans Advances in Mathematics datant de 2007 et intitulé Riemann-Roch and Abel-Jacobi theory on a finite graph qui a particulièrement interessé l'orateur.

  • Sylvie Corteel (Laboratoire d'Informatique Algorithmique: Fondements et Applications, CNRS), Diamants aztèques, Partitions pyramides, Pavages pentus, et Gares de triage, 4/12/2014
    , 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), 4/12/2014
    .

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.

  • Patrick Dehornoy (Université de Caen), Combinatoire des tresses et des structures de Garside, 27/09/2012
    , Transparents.

On passera en revue quelques problèmes combinatoires mettant en jeu les groupes de tresses et, plus généralement, les structures de Garside dont ils fournissent des exemples. Le point commun unificateur est l'existence pour les éléments des structures considérées d'un certain type de forme normale définie par des conditions locales et, de ce fait, liée à un automate et à une série rationnelle. Si le temps le permet, on mentionnera une application à des résultats de non-prouvabilité un peu paradoxaux.

  • Philippe Di Francesco (IPhT-CEA Saclay), The proof of the ASM-DPP conjecture, 7/04/2011
    , Transparents.

We prove a 28-years old conjecture by Mills-Robbins-Rumsey (1983) relating some refined enumerations of Alternating Sign Matrices (ASM) and Descending Plane Partitions (DPP). These are performed by reformulating the enumeration problems in terms of statistical models, namely the 6Vertex model for ASMs and Rhombus tilings/Dimers or Lattice Paths for DPPs. The conjecture then boils down to a determinant identity, which is proved by use of generating function techniques. Remarkably, the main player is the transfer matrix for discrete 1+1-dimensional Lorentzian quantum gravity, which generates random Lorentzian triangulations of the two-dimensional space-time.
This is joint work with Roger Behrend and Paul Zinn-Justin.

  • Maciej Dołęga (LIAFA), When orientability makes difference ?, 4/06/2015
    , 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.

  • Jehanne Dousse (Université de Zürich), La méthode du cercle à deux variables, 3/12/2015
    , 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.

  • Philippe Duchon (LABRI, Université de Bordeaux), Simulation combinatoire exacte de variables aléatoires continues, 2/04/2015
    , 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".

  • Philippe Dumas (SpecFun, INRIA Saclay), Asymptotics of linear divide-and-conquer recurrences, 6/06/2013
    , Transparents, Synthèse.

Asymptotics of divide-and-conquer recurrences is usually dealt either with elementary inequalities or with sophisticated methods coming from analytic number theory. We propose a new approach based on linear algebra. The method is rather simple but able to catch the subtle oscillations arising in the context, as does the analytic approach. It is restricted to a class of divide-and-conquer sequences, namely the sequences rational with respect to a numeration system. This family is as basic as the classical rational sequences for the usual linear recurrences.

  • Nathanaël Enriquez (Modal'X & LPMA, Université Paris X), Combinatoire des lignes convexes à sommets entiers dans le plan, 4/02/2016
    .

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.

  • Valentin Féray (Institut für Mathematik, Universität Zürich), Une formule d'équerre avec des paramètres bi-indicés pour les arbres croissants, 3/10/2013
    , Transparents.

Les formules d'équerre permettent d'énumérer les extensions linéaires de certaines familles d'ensembles ordonnés (arbres, tableaux de Young). En appliquant des bijections classiques, elles impliquent des identités combinatoires surprenantes, appelées formules sommatoires d'équerre. De nombreuses variantes et généralisations sont apparues dans la littérature ces dernières années.

Dans cet exposé, nous présenterons une nouvelle formule sommatoire d'équerre pour les arbres croissants. Pour des arbres de taille $r$, elle contient $O(r^2)$ paramètres alors que les formules connues n'en ont qu'un nombre fixé. Le membre de droite de notre formule est un produit de facteurs de degré 1 ou 2. La preuve est bijective, et fait apparaître une opération de recollement d'arbres croissants.
Travail en collaboration avec Ian Goulden (Waterloo) et Alain Lascoux (Marne-La-Vallée)

  • Philippe Flajolet (Inria Rocquencourt), L'analyse en hauteur des arbres, 7/10/2011
    , Transparents, Synthèse.

Quantifier la distribution de la hauteur d'un arbre est un problème de base partagé par les probabilistes et les combinatoriciens. D'un point de vue probabiliste, d'intéressantes connexions ont été établies avec le mouvement Brownien, les processus de branchement, et le modèle dit "de l'arbre continu" (CRT). L'objectif de cet exposé est une présentation synthétique de méthodes asymptotiques fondées sur l'analyse complexe et la combinatoire analytique: ces méthodes analytiques ont en effet permis d'obtenir une caractérisation très complète de la hauteur dans les principales familles d'arbres combinatoires (arbres de Catalan, binaires ou généraux ; arbres d'Otter). Lois limites locales ou centrales, convergence de moments et bornes de grandes déviations en résultent. On croisera au passage l'ensemble de Mandelbrot, les transformations de fonctions elliptiques théta, ainsi que la théorie élémentaire de l'itération analytique.
Présentation fondée notamment sur des travaux commun avec Broutin, Gao, Odlyzko, et Richmond.

  • Loïc Foissy (LPMA, Calais), Algèbre de Hopf des topologies finies et P-partitions, 8/10/2015
    , 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.

  • Eric Fusy (LIX), Bijections autour des bois de Schnyder, 31/01/2013
    , Transparents, Synthèse.

Les bois de Schnyder sont des structures combinatoires sur les triangulations planaires (aussi graphes planaires maximaux), introduites à l'origine par Schnyder pour fournir un nouveau critère de planarité. Ces structures se sont avérées également très pertinentes d'un point de vue algorithmique et elles bénéficient d'une riche combinatoire bijective que nous survoleront ici, ainsi que des généralisations à d'autres classes de graphes.
Basé sur des travaux avec Olivier Bernardi, Dominique Poulalhon, et Gilles Schaeffer.

  • Lucas Gerin (CMAP, Ecole Polytechnique), Processus d’Hammersley discret et sous-suites croissante, 2/06/2016
    .

À 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é.

  • Christina Goldschmidt (Oxford), Parking on a tree, 1/12/2014
    .

Consider the following particle system. We are given a uniform random rooted tree on vertices labelled by $ [n]=\{1,2,...,n\} $, with edges directed towards the root. Each node of the tree has space for a single particle (we think of them as cars). A number $m \le n$ of cars arrives one by one, and car $i$ wishes to park at node $S_i$, $1 \le i \le m$, where $S_1, S_2, \ldots, S_m$ are i.i.d. uniform random variables on $ [n] $. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until the first time it encounters an empty space, in which case it parks there; otherwise, it leaves the tree. Let $A_{n,m}$ denote the event that all $m$ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Set $m = [\alpha n]$. Then if $\alpha \le 1/2$, $P(A_{n,[\alpha n]}) \to \sqrt{1-2\alpha}/(1-\alpha)$, whereas if $\alpha > 1/2$ we have $P(A_{n,[\alpha n]}) \to 0$. (In fact, they proved more precise asymptotics in $n$ for $\alpha \ge 1/2$.) In this talk, I will give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method.
Based on joint work in progress with Michal Przykucki (Oxford).

  • Vadim Gorin (MIT), Boundaries of branching graphs through stochastic monotonicity, 2/2/2017
    .

The problem of identifying all harmonic functions on a given directed graded graph has many faces depending on the graph specification. Advanced examples include classifications of random exchangeable sequences, of finite factor representations for infinite-dimensional symmetric and unitary groups, of Gibbs measures on lozenge tilings, of Macdonald-positive homomorphisms from the algebra of symmetric functions. I will present a recent approach to such problems based on a combination of the ideas of monotonicity and the Law of Large Numbers.

  • Emmanuel Guitter (CEA Saclay), Énumération des cartes planaires irréductibles par découpage géodésique, 6/06/2013
    , Transparents.

Une carte $d$-irréductible est une carte dont tous les cycles ont une longueur au moins égale à $d$, et dont tous les cycles de longueur exactement $d$ sont des bords de faces. Je montrerai comment une technique éprouvée d'énumération des cartes, le découpage géodésique, peut être adaptée avec succès au cas des cartes $d$-irréductibles. Les briques élémentaires obtenues par découpage, les "slices", ont elles-mêmes une structure récursive, induisant un codage naturel des cartes $d$-irréductibles par des arbres.
Cet exposé décrit un travail en commun avec J. Bouttier.

  • Florent Hivert (LITIS-Rouen), Autour de la Formule des équerres pour les arbres, 7/04/2011
    , Transparents.

Soit $T$ un arbre binaire à $n$ noeuds. On s'intéresse au nombre d'étiquetages décroissants de $T$ par les entiers de $1$ à $n$, chaque entier apparaissant une fois et une seule. La formule des équerres pour les arbres, exprime le nombre de ces étiquetages comme le quotient de $n!$ par le produit du nombre de noeud de chacun des sous-arbres. Il est frappant de remarquer que cette formule très simple à prouver par récurrence admet un grand nombre de raffinement et de multiples facettes. Nous présenterons les liens avec la résolution de certaines équations fonctionnelles, la combinatoire du produit de mélange et le calcul dendriforme ainsi que quelques identités sur les fractions rationnelles.

  • Christophe Hohlweg (LaCIM, Université du Québec à Montréal), Ordre faible et cône imaginaire dans les groupes de Coxeter infinis, 3/04/2014
    , Transparents.

L'ordre faible est un outil combinatoire intimement liée à l'étude des mots réduits dans les groupes de Coxeter. Dans les groupes de Coxeter finis, c'est un treillis qui oriente le graphe sommets/arêtes du permutaèdre et qui donne un cadre naturel pour construire les associaèdres généralisées (via les treillis Cambrien de N. Reading). Lors cet exposé, nous allons discuter une conjecture de Matthew Dyer qui propose une généralisation de l'ordre faible et des mots réduits aux groupes de Coxeter infinis. Il sera notamment question de la relation entre les limites des racines et le pavage de leur enveloppe convexe, des ensembles biclos et d'ensemble d'inversions de mots réduits infinis.

Partiellement basé sur des travaux communs avec M. Dyer, JP Labbé et V. Ripoll

  • Matthieu Josuat-Vergès (Université Paris-Est Marne-la-Vallée), Factorisations minimales de cycles, une série multivariée, 4/02/2016
    , 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.

  • Rinat Kedem (University of Illinois at Urbana-Champaign), T-systems and discrete integrable systems, 30/3/2017
    , Transparents.

The T-system for type A is a restricted octahedron relation, which first appeared in the context of quantum integrable spin chains with quantum affine algebra symmetries in the 80's. It has many beautiful combinatorial properties and applications, such as Frieze patterns, pentagram maps and Zamolodchikov periodicity. As a cluster algebra, it also admits a quantization. In this talk, I'll demonstrate some of the manifestations of the integrability of this system and explain the combinatorial solutions in the classical and quantum case. This talk is based on joint work with Philippe Di Francesco.

  • Bernhard Keller (IMJ, Université Paris Diderot), Mutation des carquois et identités dilogarithmiques quantiques, 20/10/2011
    .

Dans cet exposé, nous commencerons par présenter une opération élémentaire sur les graphes orientés (les carquois) : la mutation. Cette opération est apparue en physique dans la dualité de Seiberg dans les années 90 et en mathématiques dans la définition des algèbres amassées (cluster algebras) par Fomin-Zelevinsky en 2002. A des suites de mutations, nous associerons des produits de certaines séries formelles non commutatives : les (exponentielles de) dilogarithmes quantiques. Il s'avère que ces produits, construits de facon élémentaire, sont reliés aux "invariants de Donaldson-Thomas raffinés" introduits récemment par Joyce, Kontsevich-Soibelman et d'autres.

  • Christian Krattenthaler (Wien Universitat), Crible cyclique pour des partitions non-croisées généralisées associées aux groupes de réflection complexes, 24/05/2012
    , Transparents, Synthèse.

Le crible cyclique est un phénomène énumeratif énoncé par Reiner, Stanton et White. Bessis et Reiner ont proposé deux conjectures sur des phénomènes de crible cyclique pour les partitions non-croisées généralisées associées aux groupes de réflection complexes de Armstrong et Bessis. Je commencerai en expliquant ce qu'est le crible cyclique et les partitions non-croisées généralisées, et ensuite j'exposerai les idées principales d'une démonstration de ces deux conjectures.
Ce travail a été effectué en partie avec Thomas Müller.

  • Greg Kuperberg (UC Davis), Quantum graph theory, 2/2/2017
    .

Classical error correction can be interpreted as the theory of independent sets on graphs. There is an analogous notion of a quantum graph, which is implied in quantum error correction work and has been defined in greater generality by the author and Nik Weaver. I will discuss quantum graphs and the related concept of quantum metric spaces. One pair of interesting results is that there is a version of Brooks' theorem for the independence number of a quantum graph, but not the chromatic number.

  • Marc Lelarge (INRIA, DI ENS), Law of large numbers for matchings, extension and applications, 28/03/2013
    , Transparents, Synthèse.

The fact that global properties of matchings can be read from local properties of the underlying graph has been rediscovered many times in statistical physics, combinatorics, group theory and computer science. I will present a probabilistic approach allowing to derive law of large numbers. I will show how it extends previous results in several directions and describe some algorithmic applications.
Joint work with Charles Bordenave, Justin Salez, Mathieu Leconte, Laurent Massoulié, Hang Zhou.

  • Kirone Mallick (IPhT, Orsay), Fluctuations du courant dans le modèle d'exclusion et Processus de croissance, 29/02/2012
    , Transparents.

Le processus d'exclusion asymétrique (ASEP) fournit une représentation microscopique des phénomènes de transport unidimensionnel. Il possède des propriétés physiques et mathématiques remarquables, qui en font un paradigme de la mécanique statistique. Son étude a connu un grand essor après une contribution fondamentale de Derrida, Evans, Hakim et Pasquier (1993), qui utilisèrent des algèbres quadratiques pour représenter les poids des configurations microscopiques du système~: cette `technique matricielle' a ouvert la voie à une interprétation combinatoire de ces poids en termes d'arbres, de chemins ou de tableaux. Nous commencerons par un rappel général des propriétés d'ASEP et de sa pertinence pour la physique statistique hors d'équilibre. Ensuite, nous expliquerons comment la méthode algèbrique peut être étendue pour calculer la fonction de grande déviation du courant, une observable très importante du point de vue de la physique. Nos résultats impliquent des produits tensoriels d'algèbres quadratiques et sont une nouvelle fois de type combinatoire~: ils sont exacts pour toutes les tailles du système. Dans la derniere partie de l'exposé, nous présenterons une généralisation bidimensionnelle du processus d'exclusion, qui permet de représenter la forme limite d'un cristal cubique en croissance.

  • Jean-Francois Marckert (LABRI, Bordeaux), Animaux dirigés, systèmes quadratiques et systèmes de réécritures, 27/01/2012
    , Synthèse.

Un animal dirigé $A$ sur le réseau carré est une partie de $\mathbb{N}^2$ contenant l'origine 0, et telle que chaque point de A peut-être atteint depuis 0 en restant à l'intérieur de $A$, uniquement par des pas $(0,1)$ ou $(1,0)$. Le cardinal de $A$ s'appelle l'aire de $A$, et l'ensemble des sommets de $\mathbb{N}^2$ que l'on peut ajouter à $A$ sans lui faire perdre sa qualité d'animal dirigé (AD), s'appelle le périmètre de $A$. On s'intéresse à la question du calcul de la série génératrice $G(x, y)$ des AD sur réseau carré selon l'aire et le périmètre. Il s'agit d'une question centrale dans l'étude des AD, très directement liée au problème de la percolation dirigée, pour lequel le seuil critique, qui est $\sup \{ p : G( p, 1-p) = 1 \}$, est inconnu (alors qu'il existe de nombreuses méthodes pour calculer $G(x,1)$). Dans cet exposé, nous montrons l'équivalence entre le calcul de $G$ et le calcul d'une solution à un système quadratique dont les inconnues sont des matrices (équations relativement proches de celles apparaissant pour le TASEP). Incapable de résoudre ce problème, nous montrons que des matrices infinies obtenues comme point fixe d'un système de type "système de réécriture", sont "solutions naturelles" de ce problème quadratique. Trouver un vecteur propre pour l'une d'elle, devrait permettre de calculer $G$...

  • Marc Mézard (LPTMS, Paris Sud), Une approche probabiliste au problème d'acquisition comprimée (compressed sensing), 24/05/2012
    , Transparents.

L'acquisition comprimée est une évolution majeure de ces dernières années en ce qui concerne l'acquisition de signaux et le traitement de l'information. Le problème majeur posé par l'acquisition comprimée est celui de la reconstruction d'un signal parcimonieux à partir d'un nombre de mesures inférieur au nombre d'inconnues. En utilisant des concepts de physique statistique, nous avons récemment introduit une nouvelle procédure qui permet de réaliser cette reconstruction parfaitement dans une vaste gamme de taux de mesure. Cette procédure permet en fait d'atteindre la performance optimale, c'est à dire de n'utiliser qu'un nombre de mesures égal au nombre de composants non nulles du signal. Elle est basée sur une approche probabiliste de la reconstruction, un algorithme de passage de messages, et une structuration de la matrice de mesures, fondée sur des principes de la théorie de nucléation des cristaux en physique statistique. L'implémentation numérique de cette nouvelle approche montre une amélioration remarquable des performances, par rapport aux algorithmes habituels fondés sur une minimisation de norme $L_1$. Cet exposé est basé sur des travaux en collaboration avec Florent Krzakala, Francois Sausset, Yifan Sun, et Lenka Zdeborova, voir l'article : Phys. Rev. X 2, 021005 (2012) [18 pages], disponible en open access sur http://prx.aps.org/abstract/PRX/v2/i2/e021005

  • Marni Mishna (Simon Fraser University), D-finite by design, 06/12/2012
    .

D-finite functions satisfy linear differential equations with polynomial coefficients. As innocuous as that might sound, they have been a rich treasure trove for number theorists, computer algebraists, and combinatorialists. Despite deep investigations from several different angles, they still hold many mysteries. For example, Gilles Christol conjectured over 20 years ago that all D-finite globally bounded functions are diagonals of rational functions. This would imply that combinatorial classes with D-finite generating functions are very structured, but yet we have no firm grasp on the anatomy of such classes. This talk will examine the hypothesis using recent developments in lattice path enumeration, in particular the orbit sum variant of the kernel method, amongst other combinatorial evidence. We will also look at the flip side, and describe some techniques to prove that generating functions are not D-finite.

  • Sophie Morier-Genoud (IMJ, Paris 6), Cônes tangents aux variétés de Schubert, 29/09/2016
    .

Les variétés de Schubert, objets classiques en théorie des représentations, ont une géométrie et combinatoire très riches. Ces variétés admettent très souvent des singularités au point origine (commun à toutes les variétés). Le cône tangent à une variété au point origine, i.e. l'ensemble des vecteurs tangents à l'origine, donne une caractéristique de la singularité. Cette caractéristique est plus précise que celle donnée par l'espace tangent. Cependant les cônes sont bien moins étudiés et compris que les espaces tangents. Dans cet exposé nous rappellerons les notions élémentaires liées aux variétés de drapeaux et aux variétés de Schubert, puis nous formulerons un critère combinatoire pour que deux variétés de Schubert admettent le même cône tangent.
"Travail en commun avec D. Fuchs, A. Kirillov, V. Ovsienko."

  • Philippe Nadeau (CNRS, Institut Camille Jordan), Éléments pleinement commutatifs dans les groupes de Coxeter, 3/10/2013
    , Transparents, Synthèse.

Dans un groupe de Coxeter, les éléments ont une représentation par certains ensembles de mots liés entre eux par des relations. Un élément $w$ est dit pleinement commutatif (PC) si, étant donné deux mots de longueur minimale représentant $w$, il existe toujours une série de commutations de lettres adjacentes pour passer de l'un à l'autre. Ces éléments sont importants car ils indicent une base des algèbres de Temperley-Lieb généralisées; ils interviennent également en connexion avec les représentations d'algèbres de Hecke.
Dans cet exposé, nous nous intéresserons à la combinatoire des éléments PC. Nous les caractériserons précisément pour chaque groupe de Coxeter fini ou affine. Dans ce dernier cas, la suite énumérant les éléments PC selon leur longueur s'avère être ultimement périodique; on donnera la taille de la pré-période et la période minimale de cette suite, et on expliquera comment calculer sa série génératrice. Dans le cas d'un groupe de Coxeter général, on montrera que cette série est toujours rationnelle, via l'utilisation d'automates finis.
Basé en partie sur des travaux communs avec Riccardo Biagioli et Frédéric Jouhet.

  • Markus Nebel (TU Kaiserslautern), "Java 7's Dual Pivot Quicksort -- Analysis and Engineering", 5/12/2013
    , Transparents.

Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the formerly used classic Quicksort. Surprisingly, the improvement was achieved by using a dual pivot approach, an idea that was considered not promising by several theoretical studies in the past. In this talk, we identify the reason for this unexpected success. Moreover, we present the first precise average case analysis of the new algorithm showing e. g. that a random permutation of length n is sorted using $1.9n \ln n - 2.46n + O(\ln n)$ key comparisons and $0.6n \ln n + 0.08n + O(\ln n)$ swaps. Our analysis reveales a highly asymmetric nature of the algorithm. This suggest that asymmetric pivot choices are preferable to symmetric ones. From a theoretical point of view, this should allow us to improve on the current implementation in Oracle's Java 7 runtime library. We present results derived by means of our tool MaLiJAn to confirm this for asymptotic combinatorial cost measures such as the total number of executed instructions (Java bytecodes). However, the observed running times show converse behavior. With the support of data provided by MaLiJAn we are able to identify the profiling capabilities of Oracle's just-in-time compiler to be responsible for this unexpected outcome.

  • Cyril Nicaud (IGM-MlV), Combinatoire des automates, 7/04/2011
    , Transparents, Synthèse.

Dans cet exposé je présenterai les automates en tant qu'objets combinatoires. On s'intéressera à des problèmes d'énumération et de génération aléatoire, en utilisant des techniques de combinatoire analytique et de combinatoire bijective. La motivation de ces travaux est de faire de l'analyse d'algorithmes en théorie des langages, mais je me concentrerai dans cet exposé sur la combinatoire qui est derrière ces objets. Il s'agit de différents travaux réalisés avec F. Bassino, J. David, D. Gouyou-Beauchamps, P.-C. Héam, A. Martino, E. Ventura, S. Schmitz et P. Weil.

  • Jonathan Novak (Department of Mathematics, Massachusetts Institute of Technology), Lozenge tilings of sawtooth domains near a turning point, 5/06/2014
    , Transparents.

Random tilings of planar regions by three types of tiles known as "lozenges" have been heavily investigated over the past decade, partly due to their intrinsic appeal and partly due to their status as an especially tractable class of random surface models. There are many connections between lozenge tilings and the representation theory of the classical groups, and consequently representation-theoretic techniques can sometimes be used to effectively answer natural probabilistic questions about tilings. I will discuss tilings of a particular class of regions called "sawtooth domains" for which the relation to representation theory is particularly clear, and focus on the behaviour of a uniformly random tiling of a large sawtooth domain near a "turning point." As recently observed by Gorin and Panova, understanding the asymptotic joint distribution of tiles of one type in this regime comes down to understanding the asymptotics of the Harish-Chandra-Itzykson-Zuber integral in a certain scaling limit. There is a robust combinatorial model for the HCIZ integral which allows to analyze the required asymptotics at a very fine level of detail, and in particular extract a certain limit law. If time permits, I will explain how the techniques discussed can be modified to deal with tilings exhibiting certain additional symmetries.

  • Jean-Christophe Novelli (LIGM, Marne-la-Vallée), Promenade autour de l'inversion de Lagrange, 1/12/2014
    .

Cet exposé présentera des travaux récents ayant tous des liens profonds avec l'inversion de Lagrange, notamment des calculs dans les opérades dendriformes, des résultats sur les probabilités libres et encore d'autres composantes de la combinatoire algébrique et bijective.
Travaux en commun avec Matthieu Josuat-Vergès, Frédéric Menous et Jean-Yves Thibon.

  • Marc Noy (Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya), Random planar graphs with given minimum degree, 5/06/2014
    .

We determine the asymptotic growth of planar graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the 2-core of a random planar graph is of order $c \log(n)$ for an explicit constant $c$. These results provide new information on the structure of random planar graphs.
Joint work with Lander Ramos.

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

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

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

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

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

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.

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

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

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

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

  • 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

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

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

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

  • Jean-Yves Thibon (LIGM, Marne-la-Vallée), Réalisations polynomiales d'algèbres de Hopf combinatoires, 27/01/2012
    , Transparents, Synthèse.

L'idée d'utiliser des algèbres de Hopf en combinatoire n'est pas très récente, elle remonte au moins à Rota dans les années 1970. Toutefois, c'est seulement depuis une quinzaine d'années qu'on a vu apparaître de nombreux exemples nouveaux. Ces algèbres de Hopf combinatoires (AHC) sont formées de combinaisons linéaires formelles d'objets combinatoires classiques, et leurs opérations (produit et coproduit) s'expriment en termes d'algorithmes de composition ou de décomposition de tels objets. Ces exemples sont souvent reliés (par des homomorphismes) aux fonctions symétriques ou quasi-symétriques. Or, ces dernières sont définies au moyen de variables auxiliaires, et leurs opérations sont induites par le produit ordinaire des polynômes, et une opération simple de dédoublement des variables. Il est donc tentant de rechercher des variables auxiliaires permettant une description similaire des autres AHC. Lorsque cela est possible, on parle de réalisation polynomiale de l'algèbre. On obtient alors en général une simplification importante de la théorie, ainsi que de nouvelles bases qui semblent paver la voie vers une théorie des fonctions spéciales non-commutatives.

  • Nicolas Thiéry (LRI, Université Paris 11), Nombre moyen de tresses dans les mots réduits et tableaux justifiés à droite, 2/06/2016
    , 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.

  • Béatrice de Tillière (Laboratoire de Probabilités et Modèles Aléatoires, UPMC), Le Laplacien Z-invariant massique sur les graphes isoradiaux, 4/06/2015
    , 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.

  • Christophe Tollu (LIPN, Villetaneuse), Nombres de Littlewood-Richardson : modèles combinatoires, calcul et complexité, 29/03/2012
    , Transparents.

Les nombres de Littlewood-Richardson sont des entiers naturels paramétrés par trois partitions d'entiers, qui énumèrent des points entiers dans des polytopes à sommets rationnels. Ils apparaissent dans l'étude des représentations des groupes généraux linéaires. L'exposé présentera quelques propriétés importantes de ces nombres, connues de longue date ou plus récemment découvertes, puis traitera de la complexité de leur calcul et du test de leur non-nullité, ce qui permettra de faire le lien avec la théorie géométrique de la complexité, un programme d'approche du problème P vs. NP à travers la théorie des invariants et la théorie des représentations, lancé il y a quelques années par K. Mulmuley et M. Sohoni.

  • Brigitte Vallée (GREYC-Caen), Théorie de l'information : Sources, Séries de Dirichlet, Analyse réaliste d'algorithmes, 3/01/2011
    , Transparents.

En algorithmique, on manipule très souvent des mots, notamment dans l'algorithmique du texte ; plus souvent encore, on manipule ce qu'on appelle communément des clés, notamment dans les algorithmes de tri ou de recherche, ou dans les bases de données. Une clé, comme un mot, est une suite finie de symboles sur un alphabet. En algorithmique du texte, on étudie les propriétés fines des mots, et leur influence sur l'efficacité des algorithmes. C'est alors le nombre de comparaisons entre symboles qui va être la bonne mesure de coût. La manière dont les mots sont produits, les corrélations possibles entre symboles vont jouer alors un rôle essentiel; cependant, on se limite le plus souvent à des modèles simples, qui conduisent donc à des analyses peu réalistes. En algorithmique générale, la structure d'une clé est "transparente" et n'est pas prise en compte dans l'analyse : on compte pour un coût unitaire la comparaison entre deux clés. Cela conduit à des énoncés classique du type "la complexité moyenne de l'algorithme QuickSort est en $O(n \log n)$, celle de QuickSelect est en $O(n)$". Cette mesure de coût est souvent peu réaliste, dès que les clés ont une structure complexe, dans le contexte des bases de données ou de la langue naturelle, par exemple. Pour effectuer une analyse plus réaliste, il faut d'abord prendre en compte la structure d'une clé, et la considérer vraiment comme un mot. On remplace alors le coût unitaire d'une comparaison entre deux clés par le coût de la comparaison entre deux mots, égal au nombre de symboles comparés. L'algorithmique générale devient alors ... de l'algorithmique du texte. Ensuite, il faut définir un cadre adapté qui modélise la "source"qui "produit" le mot. Notre programme, décrit dans l'exposé, est donc le suivant (a) Donner un sens à ce qu'on appelle une "source générale", opérer une classification des sources, en exhibant des sous-classes intéressantes, reliées notamment à des systèmes dynamiques. (b) Définir une série génératrice (de type Dirichlet) reliée canoniquement à la source et relier la classification des sources à la classification (analytique) de leurs séries de Dirichlet. (c) Utiliser les propriétés analytiques des séries génératrices des sources pour obtenir l'asymptotique des principales structures ou algorithmes construits sur les mots de la source : arbres binaires de recherche, arbres digitaux, et algorithmes QuickSort et QuickSelect.

  • Michèle Vergne (Institut de Mathématiques de Jussieu), Continuation analytique de polytopes, 6/12/2012
    , Transparents, Synthèse.

Soit $P(b)$ un polytope défini par $N$ inéquations linéaires $(\mu_1, x) \leq b_1$, $(\mu_2, x) \leq b_2 ,\ldots, (\mu_N, x) \leq b_N$. Lorsque le paramètre $b$ varie dans un petit voisinage du paramètre initial $b^0$, le polytope $P(b)$ garde la même forme. En particulier, son volume $vol(b)$ est donné par une fonction polynomiale de $b$, lorque $b$ est proche de la valeur $b^0$. Ce polynôme change lorsque $b$ passe un mur. Varchenko a défini une "continuation analytique" $AP(b)$ de $P(b)$ : une réunion signée de polytopes $Q_i(b)$, de diverses dimensions. Si $b$ est proche de $b^0$, $AP(b) = P(b)$, mais $AP(b)$ est "analytique" en $b$. Par exemple le volume de $AP(b)$ (une somme signée de volumes) est un polynôme en $b$ pour tout $b\in \mathbb{R}^{N}$. Nous avons donné une formule de saut pour $AP(b)$. Cette étude est une version ensembliste de la variation en fonction du fibré en lignes $L$ du support du module $\sum_i (-1)^i H_i(M,O(L))$ lorsque $M$ est une variété torique. En particulier, on retrouve les formules de saut de Paradan pour le nombre de points entiers dans le polytope $P(b)$, lorsque le paramètre $b$ passe un mur.
Travail commun avec Nicole Berline.

  • Xavier Viennot (Labri-Bordeaux), Algèbres quadratiques, Robinson-Schensted, matrices à signes alternants et au-delà, 26/05/2011
    , Transparents.

La plus simple algèbre de Weyl-Heisenberg, bien connue en physique, est définie par les opérateurs $U$ et $D$ (création et suppression de particules) avec la relation de commutation $UD=DU+Id$. Un des derniers articles de P. Flajolet (avec P. Blasiak) donne des modèles combinatoires pour la réduction sous "forme normale" de polynômes dans une telle algèbre quadratique. Nous introduisons un autre modèle combinatoire, initialisé par S.Fomin, et permettant de retrouver à partir de cette algèbre quadratique, la très classique correspondance de Robinson-Schensted entre les permutations et les paires de tableaux de Young de même forme. Partant de cet exemple fondamental, nous esquisserons une théorie générale, l' "Ansatz cellulaire", permettant d'associer à certaines algèbres quadratiques Q des objets combinatoires (les Q-tableaux) , ainsi que des constructions "semi-automatiques" de bijections, comprenant en particulier la correspondance de Robinson-Schensted et les célèbres matrices à signes alternants. Une approche équivalente est basée sur la nouvelle notion d'"automate planaire".

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

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.

  • Paul Zinn-Justin (Laboratoire de Physique Théorique et Hautes Energies - LPTHE, CNRS), Des fibrés conormaux des variétés de Schubert au modèle de boucles de Brauer, 3/02/2014
    .

Dans ce travail en collaboration avec A. Knutson, nous investiguons la correspondance entre géometrie algébrique et systemes intégrables quantiques, sous l'angle des dégénerescences de Gröbner. Ce dernier point de vue a l'avantage d'être très combinatoire et de s'appliquer à la fois en cohomologie et en K-théorie.
Suivant Knutson et Miller, je rappellerai le cadre le plus simple dans lequel on peut développer cette approche, qui est celui des variétés (matricielles) de Schubert et des polynômes de Schubert et de Grothendieck. Ensuite je formulerai plusieurs variations et extensions successives de cette approche, qui nous amèneront naturellement aux modèles de boucles sur réseaux: d'abord de boucles non-croisantes (modèle de Temperley--Lieb), puis si le temps le permet, de boucles croisantes (modèle de Brauer).

  • Lenka Zdeborova (Institut de Physique Theorique, CEA/SACLAY), Clustering of sparse graphs: From phase transitions to optimal algorithms, 2/06/2016
    , 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.