Le Séminaire de Combinatoire Enumérative et Analytique, rebaptisé Séminaire Philippe Flajolet le 7 avril 2011, a pour objectif de couvrir un large spectre de recherche en combinatoire, et est ouvert à tous les chercheurs et étudiants intéressés.

Il se tient un jeudi tous les deux mois à l'ENSCP où à l'IHP, plus de détails ici.

Traditionnellement, après chaque exposé, un volontaire se charge de rédiger une petite synthèse des résultats présentés. Voir la page des archives.

Les séances de l'année 2015-2016 sont fixées au: 8 octobre 2015, 3 décembre 2015, 4 février 2016, 14 avril 2016, et 2 juin 2016 dans l'amphithéâtre Hermite de l'Institut Poincaré.

Prochaine séance: 2 juin 2016
  • 10h30 - 11h30: Lucas Gerin (CMAP, Ecole Polytechnique),
    Processus d’Hammersley discret et sous-suites croissante,
    .

À la fin des années 60, Hammersley a introduit un processus à temps et espace continus pour étudier le comportement de la plus longue sous-suite croissante d’une permutation aléatoire uniforme. Plus récemment, deux variantes discrètes de ce processus ont été introduites, ces variantes comptent des objets semblables à des sous-suites croissantes. En étudiant les mesures stationnaires de ces processus nous revisitons et unifions ces résultats. Travail en commun avec A.-L.Basdevant, N.Enriquez, J.-B.Gouéré.

  • 13h45 - 14h45: Lenka Zbedorova (Institut de Physique Theorique, CEA/SACLAY),
    Clustering of sparse graphs: From phase transitions to optimal algorithms,
    .

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.

  • 14h45 - 15h45: Nicolas Thiéry (LRI, Université Paris 11),
    Nombre moyen de tresses dans les mots réduits et tableaux justifiés à droite,
    .

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.

  • 16h00: Pause café