Pour toute surface avec bord et points marqués, il est possible d'associer à chaque arc une variable, de sorte que les arcs se croisant respectent une certaine “relation de Ptolémée”. L'algèbre engendrée par ces éléments est un exemple d'algèbre amassée (“cluster algebra”) au sens de Fomin et Zelevinsky. Dans cet exposé, nous ferons un survol des applications de la combinatoire des triangulations de surfaces aux algèbres amassées, et terminerons par une idée de la démonstration de la conjecture d'unistructuralité pour ces algèbres amassées.

In this talk, we study quotients of the magmatic operad, that is the free nonsymmetric operad generated by one binary generator. We equip the set of these quotients with a lattice structure, defined in terms of operad morphisms, and provide an analog of the Grassmann formula for the dimensions of these operads. We study a subset of this lattice, formed by operads that we call comb associative operads. The latter are not stable for the lattice operations of magmatic quotients, however, we define new operations making comb associative operads a lattice, isomorphic to the lattice of integers, equipped with the division relation and gcd, lcm operations. Finally, we study the existence of a finite convergent presentation for comb associative operads using the Knuth-Bendix completion procedure. In particular, the comb associative operad corresponding to 3 admits a finite convergent presentation, from which we deduce a complete description of its Hilbert series.

Isoradial graphs are embedded planar graphs in such a way that every face is inscribed in a circle of radius 1. They are a perfect ground to develop a theory of discrete complex analysis and to define integrable models in statistical mechanics. In this talk, we will describe combinatorial and geometric aspects of these graphs, and their impact on locality of some models of statistical mechanics (dimer models, random walk, spanning trees…)

The Partially asymmetric exclusion process (PASEP) is a physical model viewed as a Markov chain representing the displacement of particles over a finite line. The steady-state probabilities of this chain can be computed by enumerating permutations according to certain statistics. These probabilities have a natural connexion with some transition matrices, in the algebra of noncommutative symmetric functions, which implies a refinement of the probabilities of the PASEP using statistics on permuations. We place ourself in the context of the 2-PASEP, the PASEP with two kind of particles, and exhibit a connexion with the free algebra indexed by segmented compositions using statistics on partially signed permutations.

Given a cake (identified with the interval [0,1]) and players with different tastes, the envy-free cake-cutting problem asks for a partition of the cake into connected pieces so that it is possible to assign the pieces to the players without making any of them jealous. The Stromquist-Woodall theorem ensures the existence of such an envy-free division under mild conditions. Recently, Segal-Halevi asked whether these conditions could be even further relaxed by allowing that some players dislike the cake (e.g., they know the cake has been poisoned). In the traditional setting, all players are “hungry”, and always prefer to get something instead of nothing. We provide a partial answer to that question and propose also other extensions, e.g., when suddenly one player disappears.

Based on joint work with Florian Frick, Kelsey Houston-Edwards, Francis E. Su, Shira Zerbib.

Imagine a plane tree together with a configuration of particles (cars) at each vertex. Each car tries to park on its node, and if the latter is occupied, it moves downward towards the root trying to find an empty slot. This model has been studied recently by Bruner and Panholzer as well as Goldschmidt and Przykicki where is it shown that parking of all cars obeys a phase transition ruled by the density of cars. We study the annealed critical model of random plane tree together with a parking configuration of cars. Surprisingly this object is connected to stable looptree of parameter 3/2 and to processes encountered in the theory of random planar maps!

The talk is based on ongoing work with Olivier Hénard.

A pattern in a permutation is a subsequence with a specific relative order. What can we say about a typical large random permutation that avoids a particular pattern? We use a variety of approaches. For certain classes we give a geometric description that relates these classes to other types of well-studied concepts like random walks or random trees. Using the right geometric description we can find the the distribution of certain statistics like the number and location of fixed points.

“Pour un entier positif n donné, on dénombre autant de partitions de n en parts distinctes que de partitions de n en parts impairs”.

Cette identité, attribuée à Euler, résume bien ce qu'est une identité du type Rogers-Ramanujan: une égalité entre cardinaux d'ensembles de partitions, qui pour l'un vérifient des conditions de congruences sur ses parts, et l'autre des conditions sur les différences entre parts consécutives.

Nous présenterons certaines méthodes utilisées pour établir ces égalités, telles que la méthode des mots pondérés, les équations de q-différence, ainsi que des bijections directes. On étudiera entre autre l'identié Alladi-Gordon qui généralise celle de Schur, et si le temps nous le permet, l'identité de Siladic issue de la théorie des représentations des algèbres de Lie.

Dans cet exposé (basé sur un travail en cours), nous considérons le modèle d’arbres aléatoires suivant: étant donné n nombres entiers strictement positifs, on choisit un arbre (planaire enraciné) uniformément au hasard parmi ceux possédant n noeuds internes, dont les degrés sortants sont donnés par ces nombres ; par exemple, un arbre d-aire uniforme correspond à prendre tous ces n nombres égaux à d. Nous donnons une condition (très simple !) optimale sur les degrés pour que cette suite d’arbres, correctement mis à l’échelle, converge en loi vers le célèbre arbre continu brownien d'Aldous. En particulier, pour n'importe quelle suite (d_n)_n, les arbres d_n-aires uniformes à n noeuds internes convergent vers cet arbre brownien. De la même manière, nous considérons (plus brièvement) le modèle de cartes planaires biparties à degrés (des faces) prescrits et nous montrons que la même condition sur les degrés entraîne la convergence vers la carte brownienne ; en particulier, pour n’importe quelle suite (p_n)_n, les 2p_n-angulations à n faces convergent vers la carte brownienne.

La hiérarchie KP est un ensemble d’EDP provenant originellement de la physique mathématique. Il s’avère qu’elle s’applique aussi aux cartes combinatoires et aux objets similaires (constellations, nombres de Hurwitz) : Goulden et Jackson en ont tiré une formule de récurrence pour les triangulations, puis Carrell et Chapuy ont trouvé une formule s’appliquant aux cartes en général. Ces différentes formules ont été prouvées à l’aide de la théorie des représentations du groupe symétrique, et il est naturel de chercher des bijections les expliquant. La restriction de ces formules aux cartes à une face — la formule d’Harer Zagier — a été prouvée bijectivement par Chapuy Féray et Fusy. Je présenterai une preuve bijective de la restriction de ces formules aux cartes planaires.

La théorie des fonctions symétriques est une source particulièrement fertile d'identités combinatoires importantes. Pour ce faire, il faut bien entendu des expressions positives (avec coefficients entiers). Après avoir illustré les mécanismes qui permettent d'obtenir de belles identités combinatoires à partir des fonctions symétriques, nous allons montrer qu'il y a à la fois une rareté de ces phénomènes, et d'autre part une forte invariance de la positivité pour toutes les opérations importantes du contexte. On mentionnera au passage des liens avec une version algébrique du problème P vs NP.

Au cours de cet exposé, nous décrirons le formalisme DLR de description des états d’équilibre en mécanique statistique mathématique tel qu’il a été établi par Georgii (1988), après avoir été introduit par Dobrushin (1968) et Lanford/Ruelle (1969). Nous décrirons tout d’abord l’ensemble des mesures de Gibbs dans le cadre de modèles d’Ising aux proches voisins en insistant sur l’absence ou l’existence d’états extrémaux non-invariant par translation (Etats de Dobrushin). Tandis qu’en dimension 2 l’absence de tels états est reliée à la fluctuations d’interfaces microscopique et à la coexistence de phases à basse température, leur présence en dimension supérieure est interprétée comme la manifestation d’interfaces macroscopiques séparant des phases dites pures. Nous décrirons ensuite des résultats plus récents concernant des modèles d’Ising à longues portées obtenus en collaboration avec R. Bissacot, E. Endo et A. van Enter (en dimension 1) et avec L. Coquille, A. van Enter et W. Ruszel (en dimension 2).

We present the first combinatorial scheme for counting labelled 4-regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function of labelled 4-regular planar graphs can be computed effectively as the solution of a system of equations, from which the coefficients can be extracted. As a byproduct, we also enumerate labelled 3-connected 4-regular planar graphs, and simple 4-regular rooted maps. Finally, we discuss how to obtain asymptotic results.

This is based on joint works with Marc Noy (UPC) and Clément Réquile (TU Wien)

We introduce notions of certificates allowing to bound eccentricities in a graph. In particular , we revisit radius (minimum eccentricity) and diameter (maximum eccentricity) computation and explain the efficiency of practical radius and diameter algorithms by the existence of small certificates for radius and diameter plus few additional properties. We show how such computation is related to covering a graph with certain balls or complementary of balls. We introduce several new algorithmic techniques related to eccentricity computation and propose algorithms for radius, diameter and all eccentricities with theoretical guarantees with respect to certain graph parameters. This is complemented by experimental results on various real-world graphs showing that these parameters appear to be low in practice. We also obtain refined results in the case where the input graph has low doubling dimension, has low hyperbolicity, or is chordal.

This talk will be an introduction to the enumeration of combinatorial types of convex polytopes, and the contrast between low and high dimensions. While in dimensions up to 3 we have a very good understanding on the asymptotic growth of the number of polytopes with respect to the number of vertices, in higher dimensions we only have coarse estimates. There is a family for which precise enumeration is possible, d-polytopes with d+3 vertices, thanks to Gale duality. I will finish with open problems and partial results concerning the enumeration of d-polytopes in terms of their number of vertices and facets.

Le calcul de volume de polytopes est un problème combinatoire classique, et peut se ramener à un problème d'énumération une fois qu'on a triangulé le polytope. Plus généralement, le comptage de points entiers dans les polytopes permet de raffiner le calcul du volume (via le polynôme d'Ehrhart). Ici on s'intéresse à une famille de polytopes bien particulières, et le problème d'énumération associé fait apparaître des permutations cycliques satisfaisant certaines conditions.

Il s'agit d'un travail en commun avec A. Ayyer et S. Ramassamy (mais l'exposé sera relativement indépendant de celui donné par Sanjay dans un précédent séminaire !).

Introduced by Gosper in 1978, the Continued Logarithm Algorithm computes the gcd of two integers efficiently, performing only shifts and subtractions. Shallit has studied its worst-case complexity in 2016, showing it to be linear. Here, we perform the average-case analysis of the algorithm: we study its main parameters (number of iterations, total number of shifts) and obtain precise asymptotics for their mean values, with explicit constants. Our analysis involves the dynamical system underlying the algorithm, which produces continued fraction expansions whose quotients are powers of 2. Even though studied by Chan in 2005, this system from an Ergodic Theory perspective, the presence of powers of 2 in the quotients gives a dyadic flavour which cannot be analysed only with Chan's results. Thus we introduce a dyadic component and deal with a two-component dynamical system. With this new mixed system at hand, we provide a complete average-case analysis of the algorithm.

Dans cet exposé, nous nous intéressons à plusieurs modèles de marches sur le réseau~${\mathbb Z}^2$, pour obtenir, à longueur~$n$ fixée et pour certains ensembles de pas bien choisis, des bijections entre, d'une part, des modèles de marches du demi-plan supérieur terminant sur l'axe des abscisses, et d'autre part, des modèles de marches du quart de plan.

Une première bijection tout à fait explicite est classique pour les marches tandem, c'est-à-dire entre les marches du demi-plan empruntant les pas Nord, Ouest et Sud-Est, et les marches du quart de plan empruntant les mêmes pas. Nous donnons d'abord un nouveau calcul de cette bijection et de son inverse, exprimé à l'aide d'automates réalisant des transductions. L'analyse de ce calcul permet un suivi de paramètres sur la position finale des marches, raffinant ainsi la bijection initiale.

Le résultat se généralise d'abord en une bijection entre une bicoloration du modèle précédent à trois pas confiné au demi-plan et le modèle du quart de plan obtenu en complétant l'ensemble de pas par symétrie, de sorte à autoriser les six pas Nord, Nord-Ouest, Ouest, Sud, Sud-Est et Est. Cette nouvelle bijection fournit une explication bijective au facteur~$2^n$ observé par Bousquet-Mélou et Mishna pour le modèle à six pas.

Une autre généralisation fournit une bijection entre modèles à grands pas. Plus précisément, pour chaque~$p$ donné, en conservant le pas Sud-Est et en remplaçant les pas Nord et Ouest par les $p+1$ pas de longueur~$p$ dans le quadrant Nord-Ouest. Ce modèle est proche, mais distinct, des modèles de chemins tandems généralisés étudiés par Bousquet-Mélou, Fusy et Raschel.

(Exposé sur la base de travaux en cours avec A.~Bostan, A.~Mahboubi et K.~Yeats.)

While the enumeration of linear extensions of a given poset is a well-studied question, its cyclic counterpart (enumerating extensions to total cyclic orders of a given partial cyclic order) has been subject to very little investigation. In this talk I will introduce some classes of partial cyclic orders for which this enumeration problem is tractable. Some cases require the use of a multidimensional version of the classical boustrophedon construction (a.k.a Seidel-Entringer-Arnold triangle). The integers arising from these enumerative questions also appear as the normalized volumes of certain polytopes.

This is partly joint work with Arvind Ayyer (Indian Institute of Science) and Matthieu Josuat-Vergès (LIGM / CNRS)

We analyze a certain finite temperature generalization of the Plancherel measure on partitions using the cylindric (periodic) Schur process. The measure, introduced by Borodin and which interpolates between Plancherel and uniformly random partitions, counts standard Young tableaux of skew shape. A simple modification becomes determinantal with kernel the finite temperature Bessel kernel. Edge fluctuations are governed by the one-third exponent and the finite temperature Tracy–Widom distribution of Johansson, itself interpolating between the Tracy–Widom distribution and the Gumbel distribution of extreme statistics. If time permits, we mention semi-speculative relations to longest increasing subsequences. Our results are discrete analogues of finite temperature random matrix results of Forrester, Johansson, and more recently, of Majumdar–Schehr and Cunden–Mezzadri–O'Connell. This is joint work with Jeremie Bouttier.

Cluster algebras were introduced by Fomin and Zelevinsky in the early 2000s, with the intent of establishing a general algebraic structure for studying dual canonical bases of semisimple groups and total positivity. A cluster algebra is a commutative ring determined by an initial “seed,” which consists of A-variables, X-variables, and some additional data. One then applies a combinatorial process called mutation to this seed to obtain another seed. The cluster algebra is generated by the variables obtained from all possible sequences of mutations. In this talk, we will focus on cluster algebras of finite type, which are those with finitely many A- and X-variables. There is a complete classification of finite type cluster algebras due to Fomin and Zelevinsky, which coincides with the classification of reduced crystallographic root systems. For classical types, the combinatorics of the A-variables and their mutations are encoded by triangulations of marked surfaces associated to each type. In particular, seeds are in bijection with triangulations, and A-variables are in bijection with the arcs of the triangulations. In this talk, we will discuss new results on the combinatorics of the X-variables in finite type cluster algebras. We will show that in classical types, the X-variables are in bijection with the quadrilaterals (with a choice of diagonal) appearing in triangulations of the surface of the appropriate type. Using this bijection, we can then count the number of X-variables in each type, as well as obtain some corollaries regarding the structure of finite type cluster algebras.

In the paper “Arctic curves of the six-vertex model on generic domains: the Tangent Method” [J. Stat. Phys. 164 (2016) 1488, arXiv:1605.01388], of Filippo Colomo and myself, we pose the basis for a method aimed at the determination of the “arctic curve” of large random combinatorial structures, i.e. the boundary between regions with zero and non-zero local entropy, in the scaling limit.

In this paper many things are claimed, and few are proven. In particular a few questions remain only vaguely answered: * how rigorous is this method? * in which cases does it apply, rigorously or heuristically? * in the cases where other methods exist, how does it compare?

We will try to answer to this partially, by giving a “top-to-bottom” rigorous derivation for the simplest and oldest case: the arctic circle phenomenon for “domino tilings of the aztec diamond”, first discovered by Jockusch, Propp and Shor [arXiv:math/9801068, but in fact from 1995]. We suppose that, of the nowadays many possible derivations of the arctic circle phenomenon, those coming from the tangent method (and restricted to the rigorous versions of it) are the fastest and cheapest ones. The audience will judge…

Les arbres syntaxiques sont des structures de données adaptées pour représenter des expressions de toutes sortes (algébriques, arithmétiques, logiques, etc.). Une notion d'arbres à motifs exclus apparaît alors naturellement dans ce contexte et apporte de belles propriétés combinatoires. Nous parlerons ici de séries formelles d'arbres, généralisant les séries génératrices habituelles. Une façon de dénombrer les arbres évitant un ensemble de motifs sera présentée. Nous nous intéresserons ensuite aux inverses de ces séries d'arbres vis-à-vis d'un produit de composition. Tout ceci entretient des liens très forts avec la théorie des opérades, point qui fera l'objet de la dernière partie de l'exposé.

Dans cet exposé j'expliquerai plusieurs de mes travaux sur différents modèles de graphes aléatoires : en particulier, je vais expliquer les périodes de connexité d'un modèle dynamique des graphes géométriques Euclidiens, la rigidité et l'orientabilité du graphe G(n,p), et je parlerai (de résultats sur) des graphes aléatoires hyperboliques et d'applications pour des grands réseaux.

Étant donné un groupe de permutation infini G, on définit la fonction qui à tout entier naturel n associe le nombre d'orbites de sous-ensembles de cardinal n, pour l'action induite de G sur les sous-ensembles d'éléments. Cameron a conjecturé que cette fonction de comptage (le profil de G) est un quasi-polynôme dans le cas où sa croissance est polynomiale. Une autre conjecture, plus forte, a été émise plus tard par un de ses étudiants, Macpherson. Elle concerne une certaine structure d'algèbre graduée sur les orbites de sous-ensembles, créée par Cameron, et suppose que si le profil de G est polynomial, alors son algèbre des orbites est de type fini. L'exposé présentera ces deux conjectures et leur contexte, ainsi que les idées de la preuve de la conjecture de Macpherson, fruit d'un travail commun de Nicolas Thiéry et Justine Falque (avec les conseils précieux de Peter Cameron lui-même).

Voir : http://semflajolet.math.cnrs.fr/

We give a short proof that a uniform noncrossing partition of the regular n-gon weakly converges toward Aldous's Brownian triangulation of the disk, in the sense of the Hausdorff topology. This result was first obtained by Curien & Kortchemski, using a more complicated encoding. Thanks to a result of Marchal on strong convergence of Dyck paths toward the Brownian excursion, we furthermore give an algorithm that allows to recursively construct a sequence of uniform noncrossing partitions for which the previous convergence holds almost surely. In addition, we also treat the case of uniform noncrossing pair partitions of even-sided polygons.

We show that for all d in {3,…,n-1} the size of the largest component of a random d-regular graph on n vertices at the percolation threshold p=1/(d-1) is of order n^(2/3), with high probability. This extends known results for fixed d and for d=n-1, confirming a prediction of Nachmias and Peres on a question of Benjamini. In contrast to previous approaches, our proof is based on a simple application of the switching method. This is joint work with Felix Joos.

Guillem's visit is sponsored by the ERC CombiTop.

Dans sa thèse de doctorat, Dupont s’intéresse au problème du calcul du coproduit de l’algèbre de Hopf fondamentale dans la catégorie des structure de Hodge-Tate mixte pour la famille des polylogarithmes motiviques de dissection. Pour cela, il introduit une famille d’algèbres de Hopf combinatoires de diagrammes de dissection, dont le produit est donné par l’union disjointe et le coproduit par un procédé d’extraction-contraction à paramètre. Ces outils lui permettent de définir, pour tout entier naturel n, des n-formes méromorphes de C^n et de définir par la suite des intégrales absolument convergentes (périodes).

Pour tout scalaire x, nous notons HD l’algèbre de Hopf graduée connexe des dia- grammes de dissection de paramètre x. Nous nous sommes intéressés au problème de l’étude de sa coliberté. Pour cela nous avons considéré son dual gradué HD*. Il possède une structure pré-Lie. Nous construisons l’unique morphisme pré-Lie entre l’algèbre pré-Lie des arbres enracinés à un générateur et l’algèbre pré-Lie des diagrammes de dissection. Ceci nous permet d’étudier l’algèbre pré-Lie engendrée par le diagramme de dissection de degré 1. Nous obtenons que cette dernière est une sous-algèbre pré-Lie non triviale non libre de l’algèbre pré-Lie des diagrammes de dissection.

Last spring, I visited François Bergeron and we worked on his favorite objects: the spaces H(n,k) of diagonal harmonic polynomials in k sets of n variables. Those spaces connect to many areas of algebraic combinatorics, representation theory and beyond, and the case H(n,2) became famous a decade ago with the n! conjecture and its proof by Haiman.

To fuel his ongoing studies François needed to compute the structure of H(5,6). This is a space of dimension 6.10^5 made of polynomials in 30 variables of degree up to 15, each having thousands of terms.

In this talk, I'll explain how the calculation can now be completed in 45 minutes with a dozen cores and ~15Go of memory. This exploits a combination of strategies (symmetries, representation theory of the symmetric and general linear group, …), each of which reduces the complexity in time and memory by one or two orders of magnitude.

There will be little prerequisites and it's my hope that some strategies (and maybe the code!) could be used in other contexts.

On s’intéresse aux fluctuations en grande dimension de modèles de partitions aléatoires introduits dans les années 80 par Kerov et Vershik. On montrera que pour tout modèle de ce type, une observable générique des partitions aléatoires est asymptotiquement gaussienne, et que l’on peut compléter ce résultat par une estimée de la vitesse de convergence et par une inégalité de concentration. La structure qui émerge pour ces mesures centrales sur les partitions est celle d’espace de modules mod-gaussien ; c’est une structure que l’on retrouve également pour les modèles de graphons et de permutons.

Graph rewriting formalisms are well-established models for the representation of biological systems such as protein-protein interaction networks. The combinatorial complexity of these models usually prevents any explicit representation of the variables of the system, and one has to rely on stochastic simulations in order to sample the possible trajectories of the underlying Markov chain. The bottleneck of stochastic simulation algorithms is the update of the propensity function that describes the probability that a given rule is to be applied next. In this talk we present an algorithm based on a data structure, called extension basis, that can be used to update the counts of predefined graph observables after a rule of the model has been applied.

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg

Discrétiser un plan irrationnel est un moyen générique d'obtenir un pavage non périodique. On s'intéresse ici à la question de savoir quand un tel pavage est, malgré son apériodicité, caractérisé par un ensemble fini de configurations locales (en termes plus savant : quand son enveloppe forme-t-elle un sous-shift de type fini ou sofique). On commencera par quelques exemples simples en dimension un, puis on introduira le formalisme de la discrétisation de plan (certes un peu abstrait en dimensions supérieures à 3, mais qui donne pourtant des pavages très visuels) et on proposera survol des résultats obtenus ces dernières années (notamment en collaboration avec Mathieu Sablik et Nicolas Bédaride). Il y aura des simulations de machine de Turing et de la géométrie algébrique de bas niveau.

Bender and Canfield proved in 1991 that the generating series of maps in higher genus is a rational function of the generating series of planar maps. In this talk, I will give the first bijective proof of this result. Our approach starts with the introduction of a canonical orientation that enables us to construct a bijection between $4$-valent bicolorable maps and a family of unicellular blossoming maps.

Graph dynamics arise naturally in many contexts. For instance in peer-to-peer networks, a participating peer may replace an existing connection with one neighbour by a new connection with a neighbour's neighbour. Several such local rewiring rules have been proposed to ensure that peer-to-peer networks achieve good connectivity properties (e.g. high expansion) in equilibrium. However it has remained an open question whether there existed such rules that also led to fast convergence to equilibrium. In this work we provide an affirmative answer: We exhibit a local rewiring rule that converges to equilibrium after each participating node has undergone only a number of rewirings that is poly-logarithmic in the system size. The proof involves consideration of the whole isoperimetric profile of the graph, and may be of independent interest.

This is joint work with Rémi Varloot.

En 2003, Angel et Schramm ont montré que la loi uniforme sur les triangulations planaires convergeait au sens de la limite locale lorsque l’on faisait tendre leur taille vers l’infini. La loi limite, appelée UIPT (pour Uniform Infinite Planar Triangulation) a été depuis très étudiée et est maintenant un objet bien compris. Dans mon exposé, je montrerai un résultat analogue à celui d'Angel et Schramm mais pour des triangulations échantillonnées selon la loi correspondant à un modèle d’Ising et non à la loi uniforme. La principale difficulté est d’étendre au modèle d’Ising les résultats combinatoires et énumératifs connus dans le cadre des triangulations « sans matière ». En utilisant les techniques développées par Bernardi et Bousquet-Mélou, nous parvenons à montrer que la série génératrice des triangulations avec une condition de bord fixée est algébrique. Je donnerai dans mon exposé, les principales idées des techniques qui permettent d’obtenir ces nouveaux résultats.

Je finirai par des questions ouvertes. L’objet limite est pour le moment très mal compris et pourrait servir à confirmer (ou non !) les fameuses prédictions de Watabiki.

Il s’agit d’un travail commun avec Laurent Ménard et Gilles Schaeffer.

Given, at each time t = 1, 2, …, n, a new file of length l(t) and a read rate r(t), an online k-compaction algorithm must maintain a collection of at most k files, choosing (at each time t, without knowing future inputs) some of the files to merge into one, thereby incurring a merge cost equal to the total length of the merged files and a read cost equal to the read rate r(t) times the number of files present at time t. The goal is to minimize the total cost over time. K-compaction algorithms are a key component of log-structured merge trees, the file-based data structure underlying NoSQL databases such as Accumulo, Bigtable, Cassandra, HBase,and others. We initiate the theoretical study of k-compaction algorithms. We formalize the problem, consider worst-case, average-case and competitive analysis (per-instance optimality), and propose new algorithms that are optimal according to these metrics.

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.

Introduit par Baxter, le modèle d'Ising Z-invariant est un modèle d'Ising en dimension 2 défini sur un graphe plongé satisfaisant la condition d'isoradialité. Les constantes de couplages satisfont aux équations de Yang-Baxter; elles dépendent d'un paramètre k, interprété comme la température extérieure au système. Pour la valeur particulière k=0, le modèle d'Ising est critique.

Dans un premier temps, nous allons introduire ces notions. Nous expliquerons comment le modèle d'Ising peut être étudié au travers du modèle de dimères. Ensuite, nous parlerons de résultats obtenus avec Cédric Boutillier et Kilian Raschel sur ce modèle. Nous démontrerons une expression explicite ne dépendant que de la géométrie locale du graphe pour les probabilités du modèle de dimères. Nous prouverons une expression explicite et locale pour l'énergie libre du modèle d'Ising. Nous montrerons une transition de phase d'ordre 2 en k=0 pour le modèle d'Ising et établirons qu'il s'agit de la même transition de phase que celle des forêts couvrantes Z-invariantes.

Un tableau de Young de forme fixée et dont on choisit un remplissage standard aléatoire peut être vu comme une surface aléatoire. L'étude de celle-ci est liée à des modèles de systèmes de particules. Cependant on ne sait pas bien étudier cette surface aléatoire. Je m'intéresserai à ce qui se passe sur le bord d'un tableau rectangulaire ou dans les coins d'un tableau de forme générale.

La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années. Nous présenterons ici un survol des liens bijectifs avec des familles de cartes planaires, en particulier avec les triangulations (pour les intervalles classiques) et avec les cartes biparties (pour les intervalles dits “nouveaux”), en mettant l'accent sur des symétries de distribution de paramètres que ces bijections révèlent (la partie sur les intervalles nouveaux est basée sur des discussions récentes avec Frédéric Chapoton).

Elizalde (2011) a caractérisé les permutations qu'on obtient en ordonnant des éléments consécutifs dans une trajectoire d'une $\beta$-transformation, avec une base $\beta$ positive. Le cas d'une base $\beta$ entière correspond au full shift sur $\beta$ lettres, qui a été étudié par Amigó, Elizalde et Kennel (2008). Nous considérons les bases négatives. Travail en commun avec Émilie Charlier.

Je parlerai d'espaces discrets obtenus en collant des polytopes en dimensions trois et plus, comme des tétraèdres ou des octaèdres. En dimension 2, les collages de polygones qui maximisent le nombre de sommets à nombre fixé de polygones sont les configurations planaires, et la classe d'universalité ne dépend pas du type de polygone. En dimensions supérieures, on cherche à identifier les collages de polytopes qui maximisent le nombre de D-2 cellules à nombre fixé de polytopes. On trouve plusieurs classes d'universalité selon le type de polytope, et la situation semble donc plus riche. Je détaillerai l'étude de plusieurs exemples.

Les algèbres dendriformes sont des structures algébriques introduites par Loday. Elle offrent un moyen de découper un produit associatif en deux produits non nécessairement associatifs. L'étude de ces algèbres, réalisée avec le point de vue fourni par la théorie des opérades, fait apparaître la combinatoire des arbres binaires et des mélanges d'arbres. Nous définissons ici une opérade à un paramètre entier généralisant l'opérade diassociative. Par dualité de Koszul, nous obtenons des généralisations de l'opérade dendriforme. Les algèbres sur ces opérades permettent de découper un produit associatif en plusieurs parties, avec certaines relations de compatibilité. Les propriétés combinatoires et algébriques de ces structures sont passées en revue.

Nous nous intéresserons une l'étude algébrique des coefficients apparaissant dans le calcul des probabilités stationnaire du ASEP à deux particules. Ces travaux généralisent ce qui a été fait dans le cas a un type de particule. Pour cela nous étudierons une sous-classe des permutations signées pour lesquelles nous définirons des statistiques permettant d'interpréter ces coefficients du 2-ASEP. Notre étude portera également sur une algèbre généralisant l'algèbre des fonctions symétriques non commutatives : l'algèbre des compositions segmentées.

http://semflajolet.math.cnrs.fr/

In the context of noncommutative probabilty theories, Belinschi and Nica introduced an order on noncrossing partitions, which is stronger than the usual refinement order. Our goal is to investigate its generalization to finite Coxeter groups. The motivation is that a generating function of its intervals is related with the Möbius function of the usual order. Via Chapoton's ex-conjectures F=H and H=M, it connects this enumeration of intervals with that of faces in the cluster complex and antichains in the root poset.

Un sous-ensemble des entiers strictement positifs est appelé un ensemble IP s'il contient toutes les sommes finies d'une suite infinie croissante d'entiers naturels. Nous étudions les ensembles IP et certaines autres propriétés additives des ensembles d'entiers naturels, avec comme point de vue celui de la combinatoire des mots. Nous utilisons diverses familles bien connues de mots infinis, comme par exemple les mots Sturmiens ou les points fixes de substitution, afin de construire divers ensembles IP possédant une multitude de propriétés additives différentes qui reflètent la richesse de la structure combinatoire du mot sous-jacent.

Seminaire PPS https://www.irif.fr/seminaires/pps/index

We show that by restricting the degrees of the vertices of a graph to an arbitrary set Δ, the threshold α(Δ) of the phase transition for a random graph with n vertices and m = α(Δ).n edges can be either accelerated (e.g., α(Δ) approx 0.38 for Δ = {0,1,4,5}) or postponed (e.g., α(Δ) approx 0.95 for Δ={1,2,50}) compared to a classical Erdős–Rényi random graph where α(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path…). We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literal is incident to belongs to the set Δ. We prove a lower bound for the probability that a formula with n variables and m=2.α(Δ) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.α.n.(1-μ.n-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson. This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals. Joint work with Vlady Ravelomanana.

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.

Rapporteurs: M. Dukes et J.F. Marckert. Examinateurs: F. Bassino, J. Bouttier, P. Chassaing, S. Corteel, A. Sportiello, V. Ravelomanana

http://semflajolet.math.cnrs.fr/

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.

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.

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.

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.

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.

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)

Joint work with P. Zinn Justin.

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$).

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”

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.

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.

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.

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.

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.

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.

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.