D
- 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.
- Bérénice Delcroix-Oger (IRIF, Paris 7),
Polytopes d’hypergraphes, algèbres et opérades.
12/04/2018.
Transparents.
En 2011, Dosen et Petric ont généralisé la notion d'épine d'un graphe aux hypergraphes. Après avoir expliqué ces notions, nous verrons une construction qui associe à une "bonne" famille d'hypergraphes une algèbre graduée sur les épines de ces hypergraphes, et l'opérade associée. Cela fournit un cadre général dans lequel s'intègrent notamment le simplexe, le cube, l'associaèdre et le permutoèdre. Ce travail est en collaboration avec Emily Burgunder et Pierre-Louis Curien.
- Vincent Delecroix (CNRS, LaBRI, Université Bordeaux),
Polynomialité dans les méandres.
29/11/18.
Les méandres sont les configurations de deux cercles plongés dans la sphère. Le paramètre principal est leur nombre d'intersection. C'est un problème ouvert de déterminer l'exposant de croissance exponentielle du nombre de méandres lorsque l'on fait croître le nombre d'intersection (Di Francesco-Golinelli-Guitter conjecturent que c'est $\sqrt{29}(\sqrt{29}+\sqrt{5})/12)$. Le but de mon exposé sera de présenter deux résultats de polynomialité pour un comptage bi-varié d'une sous classe de méandres. Le premier démontre un équivalent asymptotique lorsque la second paramètre est fixé et le second démontre la polynomialité à partir d'un certain rang lorsque le premier paramètre est fixé.
- Arnaud de Mesmay (CNRS, Gipsa-Lab, Université Grenoble),
Allers-retours entre les graphes plongés et la géométrie des surfaces.
20/09/2018.
Transparents.
Dans cet exposé, nous expliquerons à l'aide de problèmes précis comment la géométrie continue (riemannienne) des surfaces peut éclairer la combinatoire des graphes plongés et vice-versa. Nous dresserons des parallèles entre du premier côté les géodésiques, les homotopies optimales et les balayages, et de l'autre côté les cycles non-triviaux (edge-width), l'algorithmique d'un problème de recherche de graphes planaires (hauteur d'homotopie) et les décompositions arborescentes des graphes planaires. L'exposé ne présuppose aucune connaissance en géométrie différentielle ou en topologie.
Basé sur des travaux réalisés avec Erin Chambers, Gregory Chambers, Eric Colin de Verdière, Alfredo Hubard, Francis Lazarus, Tim Ophelders et Regina Rotman.
- Elie de Panafieu (Bell Labs France, Nokia),
Combinatoire analytique des graphes connexes.
01/06/2017.
Transparent. Synthèse.
Nous présentons le calcul, basé sur la combinatoire analytique, de l'asymptotique des graphes connexes en fonction de leur nombre de sommets et d'arêtes. Il s'agit à la fois d'un problème naturel pour de nombreuses applications où les graphes connexes apparaissent, mais aussi d'un défi motivant l'élaboration de nouveaux outils d'énumération des graphes. Pour parvenir au résultat, nous aborderons l'énumération des graphes à degrés contraints, et des graphes où une famille de sous-graphes est interdite. Une partie de ces travaux a été présentée à FPSAC'16.
- 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.
- Carola Doerr (LIP 6),
Randomized Search Heuristics, their working principles, and the role of theory.
08/02/2024.
Randomized search heuristics form a widely applied class of black-box optimization techniques, designed with the hope to produce high-quality solutions for a great variety of problems and without requiring any problem-specific knowledge. Many different types of randomized search heuristics exist. After discussing their main working principles, we will describe the state of the art in analyzing randomized search heuristics by theoretical means. We will highlight a few examples that demonstrate how these analyses have influenced the design of new algorithmic ideas. To stimulate a discussion with the audience of this seminar, we will then summarize where the current challenges are.
- 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.
- Jehanne Dousse (Université de Genève),
Calcul de caractères d’algèbres de Lie avec les partitions d’entiers.
6/10/2022.
Le caractère d'une représentation V d'une algèbre de Lie peut être vu comme une série génératrice des dimensions de certains sous-modules de V. Ces séries sont par définition à coefficients positifs, mais trouver des formules qui exhibent cette positivité est assez difficile et un problème important en théorie des représentations. En utilisant la théorie des cristaux parfaits et une bijection avec un nouveau type de partitions d'entiers, les "multi-grounded partitions", nous donnerons une formule de caractère purement combinatoire. Nous l'utiliserons ensuite pour trouver de nouvelles formules de caractères manifestement positives pour certaines représentations algèbres de Lie classiques en calculant des séries génératrices de partitions. Ceci est un travail en commun avec Isaac Konan.
- Enrica Duchi (IRIF, Université Paris 7),
Fighting fish.
7/12/2017.
Transparents.
Fighting fish are combinatorial structures made of square tiles that form two dimensional branching surfaces. A main feature of these fighting fish is that the area of uniform random fish of size $n$ scales like $n^{5/4}$ as opposed to the typical $n^{3/2}$ area behavior of the staircase or direct convex polyominoes that they generalize. In this talk we concentrate on enumerative properties of fighting fish: in particular we show that the number of fighting fish with $i$ left lower free edges and $j$ right lower free edges is equal to $(2i+j−2)!(2j+i−2)!/i!j!(2i−1)!(2j−1)!$.
These numbers are known to count rooted planar non-separable maps with $i+1$ vertices and $j+1$ faces, or two-stack-sortable permutations with respect to ascending and descending runs, or left ternary trees with respect to vertices with even and odd abscissa.
- 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.
- Hugo Duminil-Copin (IHES),
Compter les marches auto-évitantes sur le réseau hexagonal.
12/04/2018.
Dans cet exposé, nous présenterons les progrès récents dans le décompte des marches auto-évitantes sur le réseau hexagonal. En particulier, nous expliquerons comment calculer la constante de connectivité du modèle, prédite par le physicien Bernard Nienhuis. Travail joint avec Stanislav Smirnov.
E
- Andrew Elvey-Price (CNRS, Université de Tours),
Counting lattice walks by winding angle.
1/10/2020.
Transparents.
We count walks by winding angle around the origin on four different lattices. Our method uses a decomposition of each lattice, which allows us to write functional equations characterising generating functions for these walks. We then exactly solve these equations in terms of Jacobi theta functions, allowing us to extract asymptotic information about the associated counting sequences using methods popularised by Flajolet and Sedgewick. For each of the four lattices, we then use the reflection principle to count walks confined to cones such as the quarter plane and three quarter plane. On the square lattice, most of our results were derived by Timothy Budd in 2017 using a very different method, based on an explicit eigenvalue decomposition of certain matrices counting paths in the lattice.
- 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.
- Louis Esperet (G-SCOP, Grenoble),
Coloration de graphes et autres espaces métriques.
7/12/2017.
Transparents.
Un problème classique d'Hadwiger et Nelson (1945) demande le nombre minimum de couleurs nécessaires pour colorier les points du plan, de manière à ce que toute paire de points à distance exactement $1$ aient des couleurs différentes (on sait que la réponse se situe entre $4$ et $7$ couleurs). Une propriété du plan est que le nombre de couleurs nécessaires ne change pas si au lieu de considérer les paires de points à distance $1$ on considère les paires de points à distance $d$ (pour un réel $d > 0$ arbitraire). En revanche dans d'autres espaces métriques, il n'est pas clair que la réponse est indépendante de $d$ (dans le plan hyperbolique, c'est un problème ouvert). Dans cet exposé, on s'intéressera à une version discrète de ce problème, introduite récemment par Parlier et Petit. Dans cette version, on cherche à colorier les sommets de l'arbre $q$-régulier infini de manière à ce que les sommets à distance $d$ aient des couleurs différentes. Quand $d$ est impair c'est facile (deux couleurs suffisent). Quand $d$ est pair on montre que le nombre de couleurs nécessaires est de l'ordre de $d \log (q) / \log (d)$. Il se trouve que cela donne une réponse négative à un problème de van den Heuvel et Naserasr sur la coloration des graphes planaires.
Travail en commun avec Nicolas Bousquet, Ararat Harutyunyan, et Rémi de Joannis de Verclos.
F
- Wenjie Fang (TU Graz),
La transformation zeta steep-bounce dans le Cataland parabolique.
7/02/2019.
Transparents.
Le treillis de Tamari se définit comme l'ordre faible sur $S_n$ restreint aux permutations qui évitent le motif $231$. Mühle et Williams (2018+) ont généralisé cette construction aux quotients paraboliques de $S_n$, qui donne le treillis de Tamari parabolique. Il s'avère que la somme de tailles de tous les treillis de Tamari parabolique d'ordre $n$ correspond à la dimension de la composante homogène de degré $n$ d'une certaine algèbre de Hopf des pipe dreams, étudiée par Bergeron, Ceballos et Pilaud (2018+). Nous trouvons une explication bijective de ces relations d'équi-énumération reliant ces familles d'objets, en passant par une famille d'arbres coloriés. Muni des bijections trouvées, nous pouvons en déduire des résultats structurels intéressants, certains concernant la transformation zeta sur les chemins de Dyck, qui est centrale dans l'étude combinatoire de l'espace diagonal des coinvariants. Ce travail en cours est joint avec Cesar Ceballos et Henri Mühle.
- 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)
- Valentin Féray (Institut Elie Cartan de Lorraine),
Une bijection asymptotique et un résultat de limite d’échelle pour les factorisations de genre fixé d’un grand cycle.
1/10/2021.
Transparents.
Considérons les factorisations en transpositions du grand cycle $(1,2,...,n)$ dans le groupe symétrique $S_n$. Il est bien connu que le nombre minimal de transpositions nécessaires pour factoriser $(1,2,...,n)$ est $n-1$ et que le nombre de factorisations correspondantes est $n^{n-2}$. Les factorisations en $n-1+2g$ facteurs sont appelées factorisations de genre $g$; nous noterons $h_{n,g}$ leur nombre. On dispose d'une formule explicite pour $h_{g,n}$, mais sans preuve combinatoire.
Dans cet exposé, nous présenterons une construction combinatoire expliquant le terme dominant de $h_{g,n}$, quand $g$ est fixe et quand $n$ tend vers l'infini. Comme conséquence, nous proposerons un algorithme simple pour générer une factorisation de genre $g$ aléatoire, dont la distribution est asymptotiquement uniforme. Nous déduirons de cela la limite d'échelle d'une factorisation uniforme de genre $g$.
Travail en commun avec Baptiste Louf et Paul Thévenin.
- Ilse Fischer (Universität Wien),
Bijective proofs of alternating sign matrix theorems.
04/02/2021.
Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and alternating sign triangles, and their numbers are given by a simple product formula. For about 40 years now, combinatorialists have been trying to construct bijective proofs of these relations.
We present the first bijective proof of the enumeration formula for alternating sign matrices and of the fact that alternating sign matrices are equinumerous with descending plane partitions. Our constructions rely on signed sets, sijections and related notions such as a generalization of the Garsia-Milne involution principle. The starting point for these constructions are known “computational” proofs, but the combinatorial point of view led to several drastic modifications. We also provide computer code where all of our constructions have been implemented.
This is joint work with Matjaz Konvalinka.
- 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 (CNRS, LIX École Polytechnique),
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.
- Éric Fusy (CNRS, LIX École Polytechnique),
Intervalles de Tamari généralisés et cartes planaires orientées.
3/10/2019.
Transparents.
La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années, avec de riches propriétés énumératives. En particulier une construction due à Bernardi et Bonichon (s'appuyant sur les bois de Schnyder) établit une bijection entre intervalles de Tamari de taille n et triangulations à n sommets internes.
Le treillis de Tamari a été récemment étendu par Préville-Ratelle et Viennot aux treillis dits de nu-Tamari, et dans ce contexte on parle d'intervalles de Tamari généralisés. Fang et Préville-Ratelle ont montré que les intervalles généralisés sont en bijection avec les cartes planaires non-séparables, par une approche bijective à base d'arbres étiquetés de parcours en profondeur. Nous montrerons ici deux autres approches bijectives. La première s'appuie sur les décompositions séparantes de quadrangulations et est une extension de la bijection de Bernardi et Bonichon. La seconde spécialise la bijection de Bernardi et Bonichon aux intervalles de Tamari dits synchronisés, qui s'identifient aux intervalles généralisés.
Travaux en commun avec Abel Humbert.
