Enumerative and analytic combinatorics
Wednesday December 21, 2016, 11AM, Salle 3052
Victoria Lebed (Trinity College, Dublin) Que savent les tresses sur les tableaux de Young ?
Les tableaux de Young portent une multiplication associative, décrite
par l'algorithme de Schensted. Le monoïde ainsi obtenu est appelé
plaxique. Il joue un rôle fondamental dans de nombreuses applications
combinatoires et algébriques. On montrera que cette multiplication sur
les tableaux est entièrement déterminée par un tressage sur l'ensemble
(bien plus simple !) des colonnes. Ici un tressage est une solution
ensembliste de l'équation de Yang-Baxter. Notre tressage s'inscritégalement dans le cadre de la réécriture. Comme application, on
identifiera la cohomologie de Hochschild du monoïde plaxique, quirésiste à toutes les approches classiques, à la cohomologie tressée
des tableaux-colonnes, beaucoup plus accessible. Toutes les notions et constructions seront rappelées.
Enumerative and analytic combinatorics
Monday December 12, 2016, 11AM, Salle 2014
Francois Nunzi (IRIF) Soutenance de these: Autour de quelques chaines de Markov Combinatoires
Rapporteurs: M. Dukes et J.F. Marckert.
Examinateurs: F. Bassino, J. Bouttier, P. Chassaing, S. Corteel, A. Sportiello, V. Ravelomanana
Enumerative and analytic combinatorics
Wednesday December 7, 2016, 11AM, Salle 1007
Cedric Boutillier (UPMC) ??
Enumerative and analytic combinatorics
Thursday December 1, 2016, 10:30AM, Salle des these Halle aux farines 580F
Christina Goldschmidt, Jean-Christophe Novelli And Guilem Perarnau (Oxford, Marne et Birmingham) Parking on a tree, Promenade autour de l'inversion de Lagrange, A switching approach to random graphs with a fixed degree sequence
Enumerative and analytic combinatorics
Wednesday November 23, 2016, 11AM, Salle 1007
Alexander Moll (IHES) A New Spectral Theory for Jack Polynomials
The classical Benjamin-Ono equation v_t + v v_x = e_1 J[v_{xx}] with
periodic boundary conditions is a completely integrable system for v: T
→ R on the unit circle T, where J is the Hilbert transform. Let H
denote the Hardy space on the circle, |0> in H the vacuum, and L(v) the
Toeplitz operator with symbol v. Building on the work of
Nazarov-Sklyanin (2013), we show that the infinitely-many
\ell=0,1,2,3,… conservation laws T_{\ell}(v|e_1) of the classical
Benjamin-Ono system are moments of a conserved density given by the
spectral shift function of L(v) + e_1 d/dx and its (0,0) minor.
Moreover, Nazarov-Sklyanin (2013) also treat the canonical quantization
of this system, associating to classical conservation laws
T_{\ell}(v|e_1) an infinite hierarchy of commuting operators
\hat{T}_{\ell}(v|e_2,e_1) with \hbar = - e_1 e_2 simultaneously
diagonalized on Jack polynomials with parameter \alpha = - e_1 / e_2.
Their eigenvalues on Jacks depend only on the profile of the
*anisotropic* Young diagram built from rectangles of size (e_2, e_1).
Just like in the classical case, we realize the slopes of a profile of
an anisotropic Young diagram as a spectral shift function in the sense
of Krein (1953). The talk will begin with the general framework of
Kerov’s Markov-Krein correspondence (1998). These constructions are new
even for Schur polynomials e_1 + e_2 = 0 that relies on the first Szegö
theorem (1915). As time permits, we introduce a family of combinatorial
objects called ``ribbon paths” that are for random partitions what
ribbon graphs are for random matrices at general \beta /2 = -(e_2/e_1)
>0.
Enumerative and analytic combinatorics
Wednesday November 16, 2016, 11AM, Salle 1007
Yves Guiraud (IRIF equipe PPS) Introduction à la réécriture algébrique
La réécriture est une théorie des présentations d'objets algébriques (comme les monoïdes) par générateurs et relations orientées. Elle sert traditionnellement à répondre à des questions liées à la formalisation : comment représenter les éléments d’un monoïde, ou encore comment calculer son produit ? Elle possède aussi des applications moins connues, en algèbre homotopique, en permettant de classifier les différentes preuves d'une même égalité. Cet exposé proposera une introduction à ces différents concepts et problèmes, illustrés sur le cas des monoïdes d'Artin.
Enumerative and analytic combinatorics
Wednesday November 2, 2016, 11AM, Salle 1007
Dan Betea (IRIF (postdoc projet Emergences)) RSK geometrique
Enumerative and analytic combinatorics
Wednesday October 19, 2016, 11AM, Salle 1007
Gaetan Borot (Max Planck) Counting maps with simple boundaries
Maps are discretization of a given surface obtained by glueing a finite collection of polygonal faces along pair of edges. In this definition, the faces in the map can be quite singular, due to self-glueings. Although geometrically puzzling, this convention dates back to Tutte and simplifies the enumeration. It is also natural from the point of view of matrix model techniques, in which maps arise as Feynman diagrams.
Maps with n ordinary boundaries are just maps with n distinguished marked faces. I introduce a notion of maps with simple boundaries – this roughly means that the edges along the boundaries are not allowed to touch each other so as to form a “singular” face. I will explain how planar maps with ordinary boundaries can be retrieved bijectively from maps with simple boundaries, and the functional relations between their generating series determining one in terms of the other. This provides a map interpretation of the notion of free cumulants of Voiculescu and second order free cumulants of Speicher and Collins.
For arbitrary topologies, the enumeration of maps with ordinary boundary is governed by the topological recursion of Eynard and Orantin. I will present a conjecture to enumerate maps with simple boundaries in terms of the topological recursion which would give a combinatorial interpretation of the “symplectic invariance property” of the topological recursion.
This is work in progress with Elba Garcia-Failde.
Enumerative and analytic combinatorics
Wednesday October 12, 2016, 11AM, Salle 1007
Courtiel Julien (LIPN Paris Nord) Comprendre les marches dans le quart de plan à travers les pondérations centrales
Depuis une décennie maintenant, de nombreux progrès ont été réalisés quant à l'énumération des marches confinées dans un quart de plan. De ces travaux on observe différents comportements asymptotiques, variant selon le modèle étudié. La question est donc de savoir à quel moment un comportement spécifique cesse pour laisser place à un autre ; autrement dit, comment apparaissent les transitions de phase.
Dans cet exposé, nous proposons un cadre d'étude qui permet d'avoir une vision globale de ces transitions de phase, à savoir les pondérations centrales. Cela revient à assigner un poids à chaque pas de notre modèle, selon une contrainte raisonnable qui permet de couvrir l'intégralité des drifts possibles (i.e. direction générale de la marche - grossièrement).
Nous donnerons ainsi plusieurs propriétés de ces pondérations centrales, à la fois élémentaires et porteuses de sens. Nous étudierons en particulier un modèle spécifique, celui de Gouyou-Beauchamps, avec des estimées asymptotiques précises, qui nous sont fournies par la theorie de l'analyse combinatoire à plusieurs variables. Travail en commun avec S. Melzcer, M. Mishna, K. Raschel.
Enumerative and analytic combinatorics
Wednesday October 5, 2016, 11AM, Salle 1007
Yann Chiffaudel (LPMA) Approche macroscopique de la diffusion dans le modèle des miroirs
Dans la littérature mathématique, le mot diffusion fait référence à plusieurs définitions différentes. Je m'intéresse à la diffusion dite “macroscopique” caractérisée par l'existence d'une densité de particules évoluant selon la loi de Fick. Je porterai mon attention sur le modèle des miroirs en dimension 2 et sur sa généralisation en dimension quelconque. Ce modèle de gaz de Lorentz sur réseau permet un énoncé clair et rigoureux de la loi de Fick. Une approche analytique nous a permis de simplifier le problème et de réaliser une étude numérique qui permet de conjecturer la validité de la loi de Fick en dimension 3.
Je présenterai l'étude complète de façon très visuelle et abordable.
Enumerative and analytic combinatorics
Wednesday September 28, 2016, 11AM, Salle 1007
Guillaume Chapuy (IRIF) Graphes aléatoires dans les classes ajoutables et la conjecture deMcDiarmid-Steger-Welsh.
Soit G_n un graphe aléatoire uniforme à n sommets, choisi dans votre
classe de graphes favorite (graphes planaires, graphes sans triangles,graphes 7-coloriables, etc…). Quelle est la probabilité que G_n soit
connexe? Sans hypothèse sur la classe on ne peut, bien sûr, rien dire
sur cette question. Mais si la classe de graphe est *ajoutable*, àsavoir stable par l'ajout d'arêtes entre composantes connexes,
McDiarmid-Steger-Welsh (2005) ont conjecturé que P(G_n connexe) est au
moins exp(-1/2)=0.60… asymptotiquement. Cette borne est optimale (car
elle est atteinte pour la classe des forêts) et aussi assez étonnante
(car de nombreuses classes sont ajoutables, y compris des classes très
bizarres sur lesquelles on penserait ne rien pouvoir dire). Je parleraide notre démonstration de cette conjecture.
Je commencerai par expliquer la très jolie et simple technique dedouble-comptage due à McSW et qui permet de démontrer la borne exp(-1).
Puis j'essaierai de donner les idées principales de notre technique
nouvelle, le «double-comptage local». Cette technique débouche sur un
problème d'optimisation non convexe dont les fonctionnelles sont par
miracle des séries génératrices d'arbres enracinés pondérés par des
fonctionnelles supermultiplicatives. L'adaptation d'outils de
combinatoire classique (le théorème de disymétrie!) permet de résoudre
le problème.
Travail commun avec Guillem Perarnau (Birmingham)
Enumerative and analytic combinatorics
Thursday September 8, 2016, 11AM, Salle 1007
Michael Wheeler (University of Melbourne) Structure constants of Hall–Littlewood/Grothendieck polynomials,
Joint work with P. Zinn Justin.
Enumerative and analytic combinatorics
Thursday June 9, 2016, 11:30AM, Salle 1007
Vlady Ravelomanana (IRIF) Some extremal properties of critical random graphs
As witnessed by several authors (see for example Nachmias, Peres [2008],
Riordan-Wormald [2010]),
Addagio-Berry, Broutin, Goldschmidt [2010])
studying extremal properties (diameter, circumference, longuest path,
maximum block size, …)
of Erd\H os-Rényi random graphs $G(n, M)$ (resp. $G(n, p)$) appear to be
extremely difficult inside its
critical window of transition. That is as the number of edges satisfies
$M=n/2+x n^{2/3}$ (resp. $p=1/n + x/n^{4/3}$)
for $x=O(1)$.
In this talk, I will show how generating function approach
can capture the maximum block size and give explicit bounds for the
other parameters (as functions of $x$).
Enumerative and analytic combinatorics
Thursday June 2, 2016, 10:30AM, IHP Amphi Hermite
Lucas Gerin, Lenka Zbeborova, Nicolas Thiery (Polytechnique, CEA et Orsay) Seminaire Flajolet Séminaire Flajolet
10h30 - 11h30 Lucas Gerin (CMAP, Ecole Polytechnique)
“Processus d’Hammersley discret et sous-suites croissante”
13h45 - 14h45 Lenka Zbedorova (Institut de Physique Theorique, CEA/SACLAY)
“Clustering of sparse graphs: From phase transitions to optimal algorithms”
14h45 - 15h45 Nicolas Thiéry (LRI, Université Paris 11)
“Nombre moyen de tresses dans les mots réduits et
tableaux justifiés à droite”
Séminaire Flajolet
Enumerative and analytic combinatorics
Thursday May 26, 2016, 11:30AM, Salle 1007
Arnau Padrol (IMJ-PRG) Tropical Catalan Subdivisions
We revisit the associahedral subdivision of the Pitman-Stanley polytope
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 a tropical hyperplane arrangement. The
method generalizes to type B. This is joint work with Cesar Ceballos and
Camilo Sarmiento.
Enumerative and analytic combinatorics
Thursday May 19, 2016, 11:30AM, Salle 1007
Gregory Chatel (LIGM) Treillis de relations binaires.
Nous définissons une structure de treillis sur les relations binaires
qui peut être vue comme une généralisation de l'ordre faible sur les
permutations. Puis, en utilisant des surjections et des quotients,
nous redécouvrons plusieurs treillis liés à l'ordre faible et à
l'ordre de Tamari. La motivation de ce travail est l'étude de ces
treillis qui peuvent souvent être interprétés comme des algèbres de
Hopf et des polytopes.
Enumerative and analytic combinatorics
Thursday May 12, 2016, 11:30AM, Salle 1007
Anna Ben-Hamou (LPMA, Universite Paris-Diderot) Phénomène de cutoff pour des marches aléatoires sur des graphes aléatoires
On dit qu'une chaîne de Markov ergodique à espace d'états fini présente
le phénomène de cutoff lorsque sa distance à l'équilibre reste très
proche de 1 jusqu'au temps de mélange, puis chute abruptement vers 0 en
une période de temps bien plus petite, appelée la fenêtre du cutoff.
Dans cet exposé, nous considérerons des marches aléatoires
“non-backtracking” (sans marche arrière) sur des graphes aléatoires à
degrés prescrits. Sous une condition générale de sparsité, nous
établirons le cutoff, sa fenêtre, et montrerons que le profil de la
distance converge vers une forme universelle, celle de la fonction de
queue gaussienne. Il s'agit d'un travail en collaboration avec Justin
Salez.
Slides
Enumerative and analytic combinatorics
Thursday April 14, 2016, 10:30AM, IHP Amphi Hermite
Justin Salez, Carine Pivoteau, Salvatore Stella (LPMA, IGM et Roma) Seminaire Flajolet
Séminaire Flajolet
Enumerative and analytic combinatorics
Thursday April 7, 2016, 11:30AM, Salle 1007
Thomas Wong (LIPN (Postdoc projet IDEX USPC ALEA Sorbonne)) Enumeration Problems in directed walk models
Self-avoiding walks appear ubiquitously in the study of linear polymers as it naturally captures their volume exclusion property. However, self-avoiding walks are very difficult to analyse with few rigourous results available. In 2008, Alvarez et al. determined numerical results for the forces induced by a self-avoiding walk in an interactive slit. These results resembled the exact results for a directed model in the same setting by Brak et al. in 2005, suggesting the physical consistency of directed walks as polymer models. Via the kernel method, we extend the directed walk model to a series of models involving two directed walks as a way to find exact enumerative results for studying the behaviour of ring polymers near an interactive wall, or walls. In the final model we considered, we are unable to find exact solutions via the kernel method. Instead, we use transfer matrices to obtain numerical results that are qualitatively similar to those presented by Alvarez et al.
Enumerative and analytic combinatorics
Thursday March 31, 2016, 11:30AM, Salle 1007
Roberto Mantaci (IRIF) Mobiles equilibres
Un mobile est un arbre binaire dont chaque feuille est associée à un poids. Des exemples concrets peuvent être trouvés dans l'art moderne (Calder) ou au dessus des berceaux et des lits d'enfant.
Pour chaque nœud interne $u$ d'un mobile, on peut définir le déséquilibre de $u$ comme la différence $\delta(u)$ (en valeur absolue) entre la somme des poids des feuilles du sous-arbre gauche de $u$ e la somme des poids des feuilles du sous-arbre droit de $u$.
Le déséquilibre $\Delta(M)$ d'un mobile $M$ est alors la somme des désequilibres de tous ses nœuds. Si $\Delta(M)=0$, le mobile est parfaitement équilibré (comme c'est le cas pour les oeuvres de Calder et pour les mobiles pour distraire les bébés).
Le problème MobilesEquilibrés consiste à détérminer, pour un (multi-)ensemble de poids $p_1, p_2, \ldots, p_n$, le mobile $M$ dont les feuilles portent les poids $p_1, p_2, \ldots, p_n$ (dans un ordre quelconque) et dont les déséquilibre $\Delta(M)$ est le plus petit possible.
Ce problème est, dans un certain sens, la généralsation du problème bien connu qui consiste à déterminer le meilleur parenthesage pour calculer le produit ligne par colonne d'une suite de matrices (resolu polynomialement par programmation dynamique).
Bien que la question sur la complexité du problème reste ouverte (on ne sait pas s'il est NP ou si une solution polynomiale existe), nous présenterons certains algorithmes pour sa résolution, dont certains à complexité polynomiale qui résolvent le problème dans des cas particuliers, ainsi que d'autres ayant complexité exponentielles (dont un basé sur la programmation linéaire à variables entières) et qui résolvent le problème dans tous les cas. Les approches adoptées sont souvent fortément combinatoires.
Travail avec Yacine Hamoudi et Sophie Laplante.
Enumerative and analytic combinatorics
Thursday March 24, 2016, 11:30AM, Salle 1007
Clement Dervieux (IRIF) Le nombre de graphes de polyèdres en coin
Eppstein et Mumford (2014) ont récemment défini l'ensemble des polyèdres en coin comme l'ensemble des polyèdres 3D dont les sommets sont à coordonnées entières positives, les arêtes sont parallèles aux axes de coordonnées et tous les sommets sont visibles depuis l'infini dans la direction (1,1,1). Ils décrivent l'ensemble des graphes de polyèdres en coin, i.e. l'ensemble des graphes qui peuvent être squelette d'un polyèdre en coin : vus comme cartes planaires, il s'agit exactement des graphes duaux de certaines triangulations bicoloriées particulières, que nous appelons triangulations en coin enracinées. Nous comptons les graphes de polyèdres en coin en déterminant la série génératrice des triangulations en coin enracinées selon leur nombre de sommets : nous en obtenons une expression explicite en fonction de la série génératrice des nombres de Catalan. Nous montrons tout d'abord que ce résultat découle de la méthode classique de décomposition de Tutte. Ensuite, pour expliquer l'apparition des nombres de Catalan, nous donnons une décomposition algébrique directe des triangulations en coin~: en particulier nous mettons en évidence une famille de triangulations en amande qui admet une décomposition structurellement équivalente à celle des arbres binaires. Pour finir nous présentons rapidement une bijection directe entre les arbres binaires et ces triangulations en amande.
Enumerative and analytic combinatorics
Thursday March 17, 2016, 11:30AM, Salle 1007
Loick Lhote (IRIF et GREYC) Analyses en moyenne d'algorithmes en Fouille de Données: cas des motifs et des hypergraphes
L’extraction de connaissances à base de motifs (Pattern Mining) s'appuie sur de nombreux algorithmes ou structures de données pour extraire de l'information sous forme de motifs des bases de données. Les analyses dans le pire des cas conduisent très souvent à des complexités exponentielles mais les instances ne correspondent pas à des cas “réels”. Afin de décrire plus finement la complexité générique des problèmes issus du Pattern Mining, il convient de réaliser des analyses en moyenne. Dans cet exposé, nous introduirons quelques problèmes liés à l'extraction de motifs dits fréquents et nous montrerons leurs liens avec le calcul des traverses minimales d'hypergraphes. Ensuite, nous présenterons plusieurs résultats d'analyses en moyenne liés à ces objets. En particulier, nous montrons que sous certains modèles aléatoires de bases de données, l'extraction de motifs fréquents peut être de complexité polynomiale. Nous apporterons aussi un éclairage en moyenne sur la complexité d'extraction des traverses minimales d'hypergraphes. Ceci est un travail en commun avec Julien David, Arnaud Mary et François Rioult.
Enumerative and analytic combinatorics
Thursday February 18, 2016, 11AM, Salle 1007
Valentin Bonzom (LIPN) To be announced.
Enumerative and analytic combinatorics
Thursday February 11, 2016, 11AM, Salle 1007
Elie De Panafieu (Bell Labs) Énumération des graphes connexes par la combinatoire analytique
Enumerative and analytic combinatorics
Thursday February 4, 2016, 11AM, Salle 1007
Séminaire Flajolet Iii Programme
Enumerative and analytic combinatorics
Thursday January 21, 2016, 11AM, Salle 1007
Jang Soo Kim (Sungkyunkwan University (SKKU)) On q-integrals over order polytopes
Enumerative and analytic combinatorics
Thursday January 14, 2016, 11AM, Salle 1007
Karola Meszaros (Cornell University (Invitée Paris 7)) Realizing subword complexes via triangulations of root polytopes
Enumerative and analytic combinatorics
Thursday January 7, 2016, 11AM, Salle 1007
Julien Courtiel (UBC, Vancouver) Cordes terminales dans les diagrammes connexes de cordes