Combinatoire énumérative et analytique Jeudi 21 décembre 2017, 11 heures 45, Salle 1007 Pierre-Loïc Méliot (Université Paris-sud) Fluctuations des mesures centrales sur les partitions 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. Combinatoire énumérative et analytique Mardi 12 décembre 2017, 14 heures, Salle 3052 Jean Krivine (IRIF) Incremental Update for Graph Rewriting 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 Séminaire commun du pole Algorithmes et Structures Discrètes Combinatoire énumérative et analytique Jeudi 7 décembre 2017, 10 heures 30, Institut Henri Poincaré, Amphi Hermite Enrica Duchi, Riccardo Biagioli, Louis Esperet Séminaire Philippe Flajolet Combinatoire énumérative et analytique Jeudi 30 novembre 2017, 11 heures 45, Salle 1007 Thomas Fernique (LIPN, Université Paris 13) Plans discrets et règles locales 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. Combinatoire énumérative et analytique Jeudi 23 novembre 2017, 11 heures 45, Salle 1007 Mathias Lepoutre (École Polytechnique (LIX)) A bijective proof of the enumeration of maps in higher genus 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. Combinatoire énumérative et analytique Mardi 14 novembre 2017, 14 heures, Salle 3052 Laurent Maussoulie (MSR-Inria) Rapid Mixing of Local Graph Dynamics 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. Joint seminar Combinatoire énumérative et analytique Jeudi 9 novembre 2017, 11 heures 45, Salle 1007 Marie Albenque (École Polytechnique (LIX)) Convergence locale de triangulations munies d’un modèle d’Ising 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. Combinatoire énumérative et analytique Mardi 17 octobre 2017, 14 heures, Salle 3052 Claire Mathieu (École Normale Supérieure - DI) Online k-compaction 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. Séminaire du pôle algorithmique/combinatoire Combinatoire énumérative et analytique Jeudi 12 octobre 2017, 11 heures 45, Salle 1007 Béatrice De Tilière (Université Paris-Est Créteil, LAMA) Le modèle d'Ising Z-invariant via les dimères 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. Combinatoire énumérative et analytique Jeudi 5 octobre 2017, 11 heures 45, Salle 1007 Philippe Marchal (LIPN) Surfaces aléatoires associées à un tableau de Young et lois limites 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. Combinatoire énumérative et analytique Jeudi 28 septembre 2017, 11 heures 45, Salle 1007 Eric Fusy (LIX) Intervalles de Tamari et cartes planaires 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). Combinatoire énumérative et analytique Jeudi 29 juin 2017, 11 heures, Salle 1007 Wolfgang Steiner (IRIF) Développements en base réelle et permutations 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. Combinatoire énumérative et analytique Jeudi 22 juin 2017, 11 heures, Salle 1007 Luca Lionni (Paris Sud) Cartes combinatoires généralisées en dimensions supérieures 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. Combinatoire énumérative et analytique Jeudi 15 juin 2017, 10 heures 30, Salle 3052 Samuele Giraudo (LIGM CNRS Universite Paris Est) Découpage d'associativité généralisé 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. Combinatoire énumérative et analytique Jeudi 8 juin 2017, 11 heures, Salle 1007 Arthur Nunge (LIGM CNRS Universite Paris Est) Processus d'exclusion a deux especes et algebres combinatoires 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. Combinatoire énumérative et analytique Jeudi 1 juin 2017, 10 heures 30, Institut Henri Poincare Irène Marcovici, Elie De Panafieu, Jean-Christophe Aval (Universite de Lorraine, Nokia (Bell Labs), CNRS Labri) Seminaire Flajolet http://semflajolet.math.cnrs.fr/ Combinatoire énumérative et analytique Jeudi 18 mai 2017, 11 heures, Salle 1007 Matthieu Josuat-Verges (LIGM CNRS) Ordre de Belinschi et Nica sur les partitions non croisees 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. Combinatoire énumérative et analytique Jeudi 4 mai 2017, 11 heures, Salle 1007 Svetlana Puzynina (IRIF) Combinatoire additive basée sur les mots uniformémement récurrents 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. Combinatoire énumérative et analytique Jeudi 27 avril 2017, 10 heures 30, Salle 3052 Bérénice Delcroix-Oger (IMT) Des arbres sans ambiguités Seminaire PPS https://www.irif.fr/seminaires/pps/index Combinatoire énumérative et analytique Jeudi 20 avril 2017, 11 heures, Salle 1007 Sergey Dovgal (LIPN et IRIF) Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints 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. Combinatoire énumérative et analytique Jeudi 26 janvier 2017, 14 heures, Amphi Darboux - IHP Sanjay Ramassamy Et Eric Fusy (Brown University et LIX) “Miquel dynamics for circle patterns” et “Bijections for planar maps with boundaries”