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.