Séminaire de l'Équipe Modèles Combinatoires

31 janvier 2007 Pawel Hitczenko Permutation tableaux: stochastic properties of basic statistics Permutation tableaux, their connections to PASEP, and some of their properties were discussed by a few speakers of this year's seminar.
In this talk I will describe an elementary approach that allows one to analyze stochastic properties (expectations, variances, limiting distributions) of basic statistics of a random permutation tableau: the number of unrestricted rows, the number of 1's in top row, the number of superfluous 1's.
The talk is based on joint work (still very much in progress) with Sylvie Corteel.

7 fevrier 2007 Robert Cori Hypercartes et commutateurs

14 fevrier 2007 Frederic Chazal Stabilité et échantillonnage topologique et géométrique L'estimation et l'approximation de grandeurs topologiques ou géométriques associées à des formes dont on ne connait qu'une approximation posent des problèmes pratiques et théoriques délicats en calcul géométrique. Ces problèmes ont été largement étudiés depuis plusieurs années dans le cas de la reconstruction d'hypersurfaces lisses dans R^n : à partir d'un nuage de points mesurés sur une forme lisse, on souhaite 'reconstruire' la surface de cette forme en garantissant que le résultat produit possède la même topologie que celle de la forme échantillonnée. Il existe bon nombre de résultats et d'algorithmes satisfaisant permettant de répondre a ce problème dans le cas particulier des surfaces dans R^3.Cependant, les résultats et les méthodes actuelles possèdent un double inconvénient. Ils ne se généralisent pas à des objets non lisses et conduisent à des algorithmes inefficaces en dimension supérieure à 3. Le développement récents des outils de mesure et de simulation nécessite de mettre au point des techniques mathématiques et algorithmiques permettant d'extraire l'information topologique et géométrique de nuages de points issus d'objets non lisses dans des espaces de toutes dimensions. Dans cet exposé, nous présenterons quelques résultats récents dans cette voie. Nous verrons en particulier, que dans le cas de l'approximation d'objets non lisses, il apparait des “phenomènes d'échelle” faisant apparaitre différentes topologies à différentes échelles.
Travail en commun avec D. Cohen-Steiner (INRIA Sophia) et A. Lieutier (Dassault Systèmes)

28 fevrier 2007 Robert Cori Automates de codes correcteurs

7 mars 2007 Frederic Meunier Algorithme HyperLoglog pour estimer la cardinalité de grands multiensembles On souhaite compter le nombre de flots transitant par un routeur du web. Le débit est tel qu'il est impossible de garder en mémoire tous les flots qui passent, ni d'effectuer beaucoup de calculs. La théorie de l'information semble indiquer qu'une telle tache est impossible. Mais qu'en est-il si l'on ne souhaite qu'estimer ce nombre? Ce type de questions se retrouve dans le contexte de la sécurité des réseaux puisque de nombreuses attaques se caractérisent par une augmentation inattendue du nombre de flots. L'algorithme probabiliste LogLog, proposé par Durand et Flajolet en 2003, répond à cette requête: en utilisant m registres de taille log (log(N)), il peut compter jusqu'à N éléments distincts, avec une erreur relative de l'ordre de 1.3/sqrt(m) .
Récemment, en changeant d'estimateur, il a été possible de ramener l'erreur relative à 1.04/sqrt(m), ce qui fait actuellement de ce nouvel algorithme le meilleur et le plus simple effectuant cette tâche. Ce travail a été mené en commun avec Eric Fusy, Philippe Flajolet et Olivier Gandouet.
Les techniques utilisées pour analyser l'algorithme sont la transformée de Mellin, la poissonisation et la dépoissonisation analytique.

14 mars 2007 Bertrand Eynard Solution des equations de Tutte et geometrie algebrique: compter les cartes en tous genres Je montrerai comment resoudre les equations de Tutte et calculer la fonction generatrice des cartes ayant une topologie donnee. Les equations de Tutte planaires sont des equations algebriques, et font apparaitre une courbe algebrique. Toutes les fonctions generatrices peuvent s'exprimer en terme de geometrie algebrique. En utilisant le theoreme des residus de Cauchy sur la courbe, et en deplacant le contour d'integration, les equations se simplifient, et font apparaitre une structure de geometrie algebrique tres riche. Cette structure algebrique se represente aisement d'une facon diagrammatique, mais l'interpretation combinatoire de cette diagrammatique reste a comprendre...

28 mars 2007 Nicolas Orantin Fonction génératrice de disques bicolores et conditions de bords Les modèles de matrices aléatoires donnent accès aux fonctions génératrices de cartes coloriés dans un cadre général. Je présenterai dans cet exposé le cas de deux matrices hermitiennes qui permettent de générer toutes les cartes bicoloriés. En particulier, je montrerai comment calculer la fonction génératrice de disques consitués de polygones de deux couleurs quelque soit les conditions de couleur imposées sur le bord du disque grâce à une formule universelle indépendante du type de carte considérée (triangulations, quadrangulations,...). Je présenterai notammant quelques exemples simples de facon explicite.

11 avril 2007 Dimitri Zvonkine Sur une algèbre de séries formelles, les revêtements ramifiés de la sphère et la théorie de l'intersection des espaces des modules Soit A l'algèbre engendrée par les séries formelles \(\sum n^{n-1} q^n / n!\) et \(\sum n^n q^n / n!\). Nous prouvons que de nombreuses séries génératrices appartiennent à cette algèbre : des séries énumérant certains graphes, des séries énumérant les revêtements ramifiés de la sphère, des séries apparaissant dans la théorie de l'intersection des espaces des modules des courbes stables.

25 avril 2007 Jean Cardinal Tight Results on Minimum Entropy Set Cover In the minimum entropy set cover problem, one is given a collection of \(k\) sets which collectively cover an \(n\)-element ground set. A feasible solution of the problem is a partition of the ground set into parts such that each part is included in some of the \(k\) given sets. Such a partition defines a probability distribution, obtained by dividing each part size by \(n\). The goal is to find a feasible solution minimizing the (binary) entropy of the corresponding distribution.
Halperin and Karp have recently proved that the greedy algorithm always returns a solution whose cost is at most the optimum plus a constant. We improve their result by showing that the greedy algorithm approximates the minimum entropy set cover problem within an additive error of 1 nat \(= \log_2 e\) bits \(\simeq 1.4427\) bits. Moreover, inspired by recent work by Feige, Lov\'asz and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem.
Joint work with Samuel Fiorini and Gwenaël Joret. Presented at APPROX'06, to appear in Algorithmica.

23 mai 2007 Guillaume Chapuy Répartition des points dans une matrice de permutation

6 juin 2007 Claire Mathieu Partage de couts de diffusion et equilibre de Nash We consider a multicast game played by a set of selfish noncooperative players (i.e., nodes) on a rooted undirected graph. Players arrive one by one and each connects to the root by greedily choosing a path minimizing its cost; the cost of using an edge is split equally among all users using the edge. How large can the sum of the players' costs be, compared to the cost of a “socially optimal” solution, defined to be a minimum Steiner tree connecting the players to the root? We show that the ratio is \(O(\log^{2} n)\) and \(\Omega(\log n)\), when there are \(n\) players. One can view this multicast game as a variant of {\sc Online Steiner Tree} with a different cost sharing mechanism.
Furthermore, we consider what happens if the players, in a second phase, are allowed to change their paths in order to decrease their costs. Thus, in the second phase players play best response dynamics until eventually a Nash equilibrium is reached. We show that the price of anarchy is \(O(\log ^3 n)\) and \(\Omega(\log n)\).
Joint work with Moses Charikar, Howard Karloff, Joseph (Seffi) Naor, and Michael Saks.

19 septembre 2007 Bilyana Shoilekova Unlabeled enumeration in cacti graphs Unlabelled simple cacti graphs are enumerated using cycle index sums and dissimilarity theorems. We give the asymptotic form of the coefficients of the vertex rooted and unrooted cacti as well as the growth constant to arbitrary precision. We also investigate properties of cacti graphs such as the probability of being connected, the expected number of components, and the expected number of isolated vertices. We also look at dissimilarity theroems which can prove useful in the enumeration of more complex unlabelled varieties of planar graphs such as series-parallel graphs.

26 septembre 2007 Mihyun Kang Enumeration and uniform sampling of planar structures Planar structures, particularly planar graphs, have attracted much attention during the last few years, from the viewpoints of enumeration, sampling and typical properties. In order to determine the number of graphs of interest, typically graphs are decomposed according to connectivity. Thanks to the decomposition tree, we can either derive recursive counting formulas, from which we can design a uniform sampling algorithm to generate a random instance or interpret the decomposition in terms of equations of generating functions, from which we can estimate the asymptotic numbers using singularity analysis. On the other hand, the matrix integral method, a technique of theoretical physics, employs the powers of Hermitian matrices to express the number of embedded graphs on a 2-dimensional surface and planar maps in particular. This leads to the map enumeration results analogous to those obtained by combinatorial methods. In this talk I will discuss recent results on enumeration and uniform sampling of planar structures as well as their typical properties.

3 octobre 2007 Mathieu Cluzeau Sur l'algorithme de Valembois

10 octobre 2007 Manuel Bodirsky 10 steps to counting unlabeled planar graphs: 20 years later

17 octobre 2007 Vincent Pilaud Etoiles et multi-triangulations Soient \(k\) et \(n\) deux entiers avec \(n\) supérieur à \(2k+1\).
On appelle \(k\)-triangulation d'un polygone convexe à \(n\) côtés tout ensemble maximal de diagonales qui ne contient pas de sous-ensemble de \(k+1\) arêtes qui se croisent deux-à-deux.
Plusieurs propriétés des triangulations ont d'ores et déjà été généralisées aux \(k\)-triangulations, parmi lesquelles :

toutes les \(k\)-triangulations d'un polygone convexe à n côtés ont le même nombre d'arêtes : \(k(2n-2k-1)\).
toute arête d'une \(k\)-triangulation (de longueur au moins \(k+1\)) peut être flippée d'une unique manière. Le graphe des flips est régulier et connexe.
l'ensemble des \(k\)-triangulations d'un polygone convexe à \(n\) côtés est compté par le même déterminant de nombres de Catalan qui énumère les familles de \(k\) chemins de Dyck disjoints.

Bien que ces résultats aient déjà été démontrés (par des arguments récursifs), nous présentons de nouvelles preuves (directes) des propriétés (1) et (2) utilisant le nouveau concept d'étoiles dans les multi-triangulations qui généralise les triangles dans les triangulations. Nous présentons quelques questions ouvertes dont l'analyse pourrait être simplifiée par ce nouvel outil.
Travail en commun avec Francisco Santos, Santander, Espagne

24 octobre 2007 Guillaume Chapuy Enumeration asymptotique des constellations de genre g

7 novembre 2007 Pascal Ochem Classes d'intersection et représentabilité des graphes planaires On s'intéresse à la classe STRING des graphes d'intersection de courbes dans le plan. C'est-à-dire qu'un graphe appartient à STRING si on peut associer à chaque sommet une courbe du plan de sorte que deux sommets sont adjacents si et seulement si les courbes associées s'intersectent. Cette classe contient beaucoup de classes de graphes intéressantes (graphes de corde, d'intervalle, co-bipartis ...), notamment les graphes planaires, pour lesquels Chalopin et Goncalves ont récemment montré qu'ils admettent un modèle d'intersection dont les courbes sont des segments. Les problèmes ouverts ne manquerons pas.

28 novembre 2007 Valentin Feray Sur la conjecture de Kerov

5 décembre 2007 Marie Albenque Combinatoire des tresses positives Les tresses mathématiques sont issues d'une idée assez simple et naturelle. Cependant, leur étude mathématique, commencée par Artin en 1926, soulève des problèmes intéressants et difficiles.
Je commencerai par donner différentes présentations du groupe des tresses. Je parlerai plus particulièrement de la présentation par générateurs et relations, du problème du mot dans ce cas et comment y répondre. J'expliquerai ensuite comment généraliser la notion d'empilements de pièces pour calculer la série génératrice des tresses positives.

12 décembre 2007 Olivier Mallet Superpartitions colorées chemins et identités de type Rogers-Ramanujan On définit deux classes de séries hypergéométriques basiques multiples \(V_{k,t}(a, q)\) et \(W_{k,t}(a, q)\) qui généralisent des séries multiples étudiées par Agarwal, Andrews et Bressoud. On montre comment interpréter ces séries comme les fonctions génératrices de chemins avec certaines restrictions et de surpartitions n-colorées vérifiant des conditions de différences pondérées. On remarque aussi que certaines spécialisations de nos séries peuvent s'écrire comme des produits infinis, ce qui conduit à des identités combinatoires reliant les surpartitions n-colorées aux partitions ou surpartitions ordinaires.