Séminaire de l'Équipe Modèles Combinatoires - 2011
2 fevrier 2011 Benjamin Leveque (LIRMM, Montpellier) Triangle contact representations and duality A contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. de Fraysseix et al. proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A primal-dual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intesertection between the triangles corresponding to u and v is the same point as the intesertection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal-dual contact representation by triangles. Moreover, it can be required that the interiors of the triangles form a tiling of the triangle corresponding to the outer face and that each contact point is a node of exactly three triangles. Then, these representations are in one-to-one correspondance with generalized Schnyder woods defined by Felsner for 3-connected planar maps.
16 mars 2011 Vincent Pilaud (LIAFA, Université Paris 7) Le polytope des briques L'objet central de cet exposé est le graphe des flips sur les arrangements de pseudodroites avec points de contact couvrant un support donné. Il généralise les graphes de flips sur trois objets géométriques intéressants : les triangulations d'un polygone convexe, les pseudotriangulations d'un ensemble de points du plan en position générale, et les multitriangulations d'un polygone convexe. On s'intéresse en particulier à la polytopalité de ces graphes de flips. Par example, le graphe des flips sur les triangulations est le graphe de l'associahédre et le graphe des flips sur les pseudotriangulations est le graphe du polytope des pseudotriangulations. Pour les multitriangulations, la question reste ouverte. Dans cet exposé, je rappellerai dans un premier temps les principales propriétés combinatoires de ces objets. Dans un deuxième temps, je présenterai la construction du “polytope des briques” d'un support. Son graphe est un sous-graphe du graphe des flips sur les arrangements de pseudodroites ayant ce support. Cette construction contient en particulier toutes les réalisations de l'associaèdre d'Hohlweg et Lange, qui apparaissent comme polytopes de briques de certains supports bien choisis.
Travail en commun avec Francisco Santos (Université de Cantabrie).
19 septembre 2011 Igor Pak (UCLA) Cayley compositions, statistics on labeled trees, and triangulations of polytopes Cayley polytopes were defined recently as convex hulls of compositions introduced by Cayley in 1857. A remarkable Braun's conjecture expresses the volume of Cayley polytopes in terms of the number of connected graphs. We resolve this conjecture by giving an explicit triangulation of the polytopes into simplices which correspond to labeled trees, and whose total volume is given via an evaluation of the Tutte polynomial of the complete graph. The key idea is a direct bijection based on the neighbors-first search graph traversal algorithm due to Gessel and Sagan.
Joint work with Matjaz Konvalinka.
19 septembre 2011 Alain Goupil (UQTR) Polyominos inscrits Dans cet exposé, je discuterai de l’énumération de polyominos selon l’aire. L’approche proposée consiste à fixer le format d’un rectangle et à compter les polyominos inscrits dans ce rectangle. Un polyomino est inscrit dans un rectangle lorsqu’il touche chacun des quatre côtés du rectangles. Nous commencerons par construire la série génératrice des polyominos d’aire minimale en les caractérisant géométriquement puis nous considérons différentes extensions de cette construction.
2 octobre 2011 Dominique Poulalhon (LIX) Comment minimiser une tresse ? Le groupe Bn des tresses à n brins est décrit de façon standard comme le groupe engendré par n-1 éléments s(1),..., s(n-1) satisfaisant les relations suivantes: pour tous i et j, si |i − j| = 1, alors s(i) s(j) s(i) = s(j) s(i) s(j), et sinon s(i)s(j) = s(j)s(i) . La notion de longueur d’une tresse induite par cette présentation est la plus intuitive, puisqu’elle coïncide avec le nombre minimal de croisements de brins des isotopes de la tresse considérée. Mais alors que pour d’autres présentations de Bn , la longueur et les géodésiques sont assez bien comprises, aucun résultat n’est connu pour la présentation standard dès que n > 3. Nous présenterons de nouveaux résultats concernant B4, et proposerons un algorithme polynomial pour le calcul d’un représentant géodésique (dont la correction n’est que partiellement prouvé).
Travail en cours avec Jean Mairesse et Anne Micheli.
17 octobre 2011 Guillaume Chapuy (LIAFA) Démonstration bijective des formules de Goupil-Schaeffer On s'intéresse à l'énumération de cartes à une faces (recollement bord à bord d'un polygone). Il y a quelques années je donnais une bijection qui aboutissait à certaines formules, qui n'étaient pas du même type que les formules déjà existantes (dont Harer-Zagier). Passer d'un type de formule à l'autre demandait un calcul pas franchement naturel. Dans ce travail on rajoute une petite couche bijective, très simple, qui explique comment passer de ladite bijection à la formule d'Harer-Zagier. Pour ceux qui connaissent, il s'agit de montrer que la “récurrence des trisections” des cartes à une face est également satisfaite par un modèle très simple de permutations. On se rend alors compte que l'on peut contrôler bien des choses, comme le degré de tous les sommets, et l'on retrouve les célèbres formules dues à l'invité actuel du LIX et à l'organisateur du séminaire.
Travail en cours avec Valentin Féray et Éric Fusy.
24 octobre 2011 Dimitrios M. Thilikos (University of Athens) Algorithmic Consequences of the Graph Minors Theory The main mathematical achievement of the Graph Minors Theory (GMT), developed by Robertson and Seymour, was the proof of Wagner's conjecture, now known as the {\sl Robertson & Seymour Theorem}, stating that graphs are well quasi ordered under the minor containment relation. Besides its purely theoretical importance, GMT induced a series of powerful algorithmic results and techniques that had a deep influence in theoretical computer science. GMT offered the theoretical base for the understanding and the resolution of some of the most prominent graph-algorithmic problems in parameterized complexity. In this talk we give a brief presentation of the main results and techniques to this direction.
24 octobre 2011 Adrian Tanasa (LIPN) Polynômes de graphes (et de cartes) et leurs liens avec les théories quantiques des champs In the first part of this talk I will present the Tutte polynomial, a combinatorial object encoding the topological information of a graph. I will then briefly introduce some notions of quantum field theory (QFT) and show that the Tutte polynomial is naturally related to some polynomials appearing within this framework of theoretical physics. In the second part of the talk I will show how these notions generalize, on one hand to the Bollobas-Riordan polynomial for ribbon graphs (or maps) and on the other hand, to non-commutative QFT. As previously, I will show the relation between these a priori distinct notions.
24 octobre 2011 Memari Pooran (Telecom-paristech) Hodge Optimized Triangulations We introduce Hodge-optimized triangulations (HOT), a family of well-shaped primal-dual pairs of complexes designed for fast and accurate computations in computer graphics. Previous work most commonly employs barycentric or circumcentric duals; while barycentric duals guarantee that the dual of each simplex lies within the simplex, circumcentric duals are often preferred due to the induced orthogonality between primal and dual complexes. We instead promote the use of weighted duals (power diagrams). They allow greater flexibility in the location of dual vertices while keeping primal-dual orthogonality, thus providing a valuable extension to the usual choices of dual by only adding one additional scalar per primal vertex. Furthermore, we introduce a family of functionals on pairs of complexes that we derive from bounds on the errors induced by diagonal Hodge stars, commonly used in discrete computations. The minimizers of these functionals, called HOT meshes, are shown to be generalizations of Centroidal Voronoi Tesselations and Optimal Delaunay Triangulations, and to provide increased accuracy and flexibility for a variety of computational purposes.
This is a joint work with Patrick Mullen, Fernando de Goes and Mathieu Desbrun from Caltech.
28 novembre 2011 Luca Castelli Aleardi (LIX) Structures de données compactes pour les triangulations We consider the problem of designing space-efficient explicit data structures for planar and surface meshes. Our main result is a new explicit data structure for compactly representing planar triangulations (corresponding to genus 0 triangle meshes): if one is allowed to permute input vertices, then a triangulation with n vertices requires at most 4n references (5n references if vertex permutations are not allowed). Our solution combines existing techniques from mesh encoding with a novel use of Schnyder woods. As far as we know, our solution provides the most parsimonious data structures for triangle meshes, allowing constant time navigation in the worst case.
Joint work with O. Devillers.