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

Lundi 7 janvier 2013 Laurent Menard (Paris Ouest, Nanterre) Percolation sur la carte infinie uniforme La carte infinie uniforme est la limite locale des cartes à n arêtes, sans contrainte de degré sur les faces, choisies uniformément au hasard. Nous montrerons comment un procédé d'épluchage, arête par arête, permet d'étudier la percolation sur cette carte. En particulier, cela permet d'obtenir les valeurs explicites du point critique pour la percolation par arêtes ainsi que la percolation par sites.
Cet exposé est basé sur un travail en cours avec Pierre Nolin (ETH Zürich).

Lundi 14 janvier 2013 Carsten Lange (Équipe Combinatoire et Optimisation, UPMC) Minkowski decompositions of associahedra into faces of a standard simplex J.-L. Loday gave a beautiful and simple combinatorial description for explicit realizations of associahedra. His construction was generalized subsequently and the resulting family of realizations is parametrized by Coxeter elements of the symmetric group. A remarkable property of these realizations is that they decompose into Minkowski sums and differences of dilated faces of a standard simplex.
My talk consists of two parts. Firstly, I will explicitly describe the combinatorics of the realizaitions. Secondly, I will show that these polytopes in fact admit the mentioned Minkowski decomposition and I will give an efficient combinatorial algorithm to compute its coefficients.

Lundi 18 février 2013 Cécile Mailler ( Laboratoire de Mathématiques de Versailles, UVSQ) Formules booléennes aléatoires construites sur un ensemble non borné de variables Un arbre booléen est un arbre binaire, planaire dont les nœuds internes sont étiquetés par des connecteurs logiques (ici ET ou OU), et dont les feuilles sont étiquetées par des littéraux. Si les littéraux sont choisis dans une famille finie \(\{x_1,\bar{x}_1,\ldots,x_k,\bar{x}_k\}\), l'arbre booléen calcule une fonction booléenne à \(k\) variables. Si l'arbre booléen est tiré uniformément parmi les arbres de taille \(n\), on obtient, quand \(n\) tend vers l'infini la distribution des grands arbres, définie sur l'espace des fonctions booléennes à \(k\) variables. Mais ne serait-il pas plus naturel de choisir “\(k=\infty\)” ou même “\(k = k(n)\)” ?

Lundi 25 février 2013 Juanjo Rué (ICMAT, Madrid) Threshold functions for systems of equations on random sets We present a unified framework to deal with threshold functions for the existence of certain combinatorial structures in random sets. More precisely, let \(Mx = 0\) be a linear system of \(r\) equations and \(m\) variables, and \(A\) a random set on \([n]\) where each element is chosen independently with the same probability. We show that, under certain conditions, there exists a threshold function for the property “\(A^m\) contains a non-trivial solution of \(Mx = 0\)”, depending only on \(r\) and \(m\) and, furthermore, we study the behavior of the limiting probability in the threshold scale in terms of volumes of certain convex polytopes arising from the linear system under study. Our results cover several combinatorial families, namely sets without arithmetic progressions of given length, \(k\)-sum-free sets, \(B_h[g]\) sequences and sets without Hilbert cubes of dimension \(k\), among others.
The techniques used in this approach combines the so-called Probabilistic Method, widely used in discrete mathematics, joint with lattice point estimates coming from Ehrhart theory on polytopes.
If time permits, further extensions and on-going projects in this direction will be also discussed.
This is a joint work with Ana Zumalacárregui. The preprint is available on-line.

Mercredi 20 mars 2013 Jarek Rossignac (Georgia Tech, School of Interactive Computing) Advances and challenges in the design of compact representations of meshes and complexes The lecture will address recent advances in compact representations of triangle meshes and their extensions to polygon and tetrahedron meshes and to simplicial complexes. We define a core set of Random Access and Traversal operators and discuss their desired features of Constant Amortized Time, Editability, and Streamability. We couch our discussion in terms of corners [1] and start with the Corner Table data structure [1] which stores for each triangle 3 references to its vertices and 3 references to asjacent triangles and hence uses 6 rpt (integer references per triangle) or equivalently 192 bpt (bits per triangle). By matching each vertex with a different triangle, the SOT approach [2] eliminates the need to store the references form triangles to their vertices. By matching most vertices with an incident quad (pair of adjacent incident triangles), the SQuad approach [3] eliminates about one third of the remaining references to adjacent triangles. By finding an arrangements of the quads so that their diagonals form a loop that is a nearly Hamiltonian cycle of the mesh, the LR approach [4] (and its BELR variation) reduce storage cost to about 1 rpt (and respectively to about 26 bpt). By gap encoding the references of the LR representation, the Zipper approach [5] further reduces storage to about 6 bpt, yet it supports the same Constant Amortized Time Random Access and Traversal operators as the Corner Table. Unfortunately, these compact data structures are neither editable (i.e., they do not support local changes to the connectivity, such as an edge flip or collapse, in constant amortized time) nor streamable (i.e., they cannot be efficiently constructed from a streamed input format nor processed in streamed mode when the file is larger than the available core memory). The ESQ approach [6] offers an editable and more general version of SQuad. The Grouper approach [7] offers a streamable version of SQuad. The SOT approach has also been extended to tetrahedron meshes [8]. It extends to concept of triangle corners to tetrahedron wedges and offers convenient wedge operators for mesh traversal.
1. “Edgebreaker on a Corner Table: A simple technique for representing and compressing triangulated surfaces”, J. Rossignac, A. Safonova, A. Szymczak. Book chapter in Hierarchical and Geometrical Methods in Scientific Visualization, Farin, G., Hagen, H. and Hamann, B., eds. Springer-Verlag, Heidelberg, Germany. Pages 41-50, January 2003.
2. “SOT: Compact Representation for Triangle and Tetrahedral Meshes”, T. Gurung and J. Rossignac, Georgia Institute of Technology, SIC Technical Report GT-IC-10-01, 2010 https://smartech.gatech.edu/handle/1853/35001
3. “SQuad: Compact Representation for Triangle Meshes”, T. Gurung, D. Laney (LLNL), P. Lindstrom (LLNL), and J. Rossignac. Eurographics 2011. Published as a journal paper in the Computer Graphics Forum Journal (CGF) 30(2): 355-364.
4. “LR: Compact connectivity representation for triangle meshes”, Topraj Gurung, Peter Lindstrom, Mark Luffel, Jarek Rossignac. ACM SIGGRAPH 2011. Published as a journal paper in the ACM Transactions on Graphics (TOG), 30(4): 67, August 2011.
5. “Zipper: A compact connectivity data structure for triangle meshes”, T. Gurung, M. Luffel, P. Lindstrom, and J. Rossignac. ACM Symposium on Solid and Physical Modeling, October 2012. Journal of Computer-Aided Design. 45(2): 262-269 (2013).
6. “ESQ: Editable SQuad representation for triangle meshes”, L. Castelli Aleardi, O. Devillers, J. Rossignac. IEEE sponsored Conference on Graphics, Patterns and Images (SIBGRAPI), August 22, 2012, Brazil.
7. “Grouper: A compact, streamable triangle mesh data structure” M. Luffel, R. Gurung, P. Lindstrom, and J. Rossignac, submitted 2012.
8. “SOT: Compact representation for Tetrahedral Meshes”, T. Gurung and J. Rossignac. ACM Symposium on Solid and Physical Modeling (SPM), 79-88. 2009.

Lundi 25 mars Razvan Gurau (CPHT) Graphes colorés et triangulations en dimension supérieure à deux Les graphes à lignes colorés encodent des triangulations d'espaces en dimension arbitraire. On détaillera cette relation et on étudiera notamment une sous-catégorie de graphes qui sont de genre zéro pour un ensemble canonique de projections planaires. Ces graphes représentent topologiquement des sphères et dominent le comportement de modèles de grands tenseurs aléatoires.

Lundi 8 avril Frédéric Meunier (Cermics, ENPC) Un cadre combinatoire pour la profondeur simpliciale colorée Le théorème de Carathéodory coloré, dû à Bárány, affirme que si l'on se donne \(d+1\) ensembles de points \(S_1, \dots, S_{d+1}\) dans \(\mathbb{R}^d\), chacun d'eux contenant l'origine dans son enveloppe convexe, alors il est possible de choisir un point \(p_i\) dans chaque \(S_i\) et d'avoir encore l'origine dans l'enveloppe convexe des \(p_i\). L'enveloppe convexe des \(p_i\) est alors appelée "simplexe coloré contenant l'origine". Le nombre de simplexes colorés contenant l'origine est la "profondeur simpliciale colorée" de l'origine.
Une question qui a reçu une attention particulière est celle de savoir quelle est la plus petite profondeur simpliciale colorée possible dans le cas où chaque \(S_i\) est de cardinalité \(d+1\). Le théorème de Bárány montre qu'elle vaut au moins \(1\). La valeur minimale \(\mu(d)\) qu'elle peut prendre a été étudiée par Deza et al., Bárány et Matoušek, et Stephen et Thomas, qui ont montré que \(\mu(d)\) vaut toujours au moins \(\frac{d^2+2d+1}{2}\) et au plus \(d^2+1\). La conjecture que \(\mu(d)\) vaut \(d^2+1\) a été vérifiée en dimensions \(1\), \(2\) et \(3\).
Dans cet exposé, nous améliorons la borne inférieure et montrons que \(\mu(d)\) vaut toujours au moins \(\frac{d^2+7d-16}{2}\). Nous montrons également que \(\mu(4)=17\), et donc que la conjecture est vraie en dimension \(4\). Les preuves utilisent des hypergraphes particuliers spécialement conçus pour ce problème - les systèmes octaédriques, dont l'étude a été récemment suggérée par Bárány. Quelques résultats théoriques les concernant seront également présentés.

Lundi 15 avril Lionel Pournin (Laboratoire de Recherche en Informatique de l'EFREI) The diameters of associahedra Associahedra are polytopes that were independently discovered within different areas of mathematics such as algebraic topology, discrete geometry, and combinatorial optimization. The boundary complex of the \(d\)-dimensional associahedron can be indifferently represented using bracketed words of \(d+2\) letters, triangulations of convex polygons with \(d+3\) vertices, or size \(d+1\) binary trees.
In 1988, Daniel Sleator, Robert Tarjan, and William Thurston have shown that the diameter of this polytope is at most \(2d-4\) when \(d\) is larger than \(9\) and that this bound holds with equality when d is large enough. They further conjecture that “large enough” means “greater than \(9\)”.
The recently announced proof of this conjecture will be sketched in this talk. As a preliminary, the associahedra will be described as well as a selection of the many problems these polytopes are related to.

Lundi 22 avril Alfredo Hubard (DI, ENS) Happing ending theorems for planar convex bodies The Erdos-Szekeres (happy ending) theorem claims that, for any number \(n\) there is a number \(ES(n)\) such that among any set of at least \(ES(n)\) points in general position in the plane, there are at least \(n\) of them that form the vertex set of a convex polygon. During the last 80 years the value of \(ES(n)\) has generated a lot of interest and it remains unknown. Goodman and Pollack generalized this result to the realm of pseudoline arrangements while Bisztriczky and Fejes Toth first, and then, in more generality, Pach and Toth generalized this result to the context of arrangements of convex bodies in the plane. Denote the values of the corresponding Ramsey functions by \(GP(n)\) (pseudo lines), \(BFT(n)\) (disjoint convex bodies) and \(PT(n)\) (non crossing convex bodies) which are all unknown. In a joint work with Andreas Holmsen and Michael Dobbins we showed that the happy ending problem for pseudoline arrangements and for noncrossing convex bodies are equivalent, yielding the equality \(PT(n)=GP(n)\) and significant quantitative improvements to the upper bounds of functions \(BTF(n)\) and \(PT(n)\). The new bounds for \(GP(n)\), \(BFT(n)\) and \(PT(n)\) are the same as the known one for \(ES(n)\).

Lundi 13 mai Nabil Mustafa (ESIEE) The multiplicative weights technique in Discrete Geometry I will explain a simple broad technique for converting claims of one type to a different dual-like set of claims. While this technique has had several applications in various areas in Computer Science, I will only focus on some applications in discrete and computational geometry. In particular, I will describe three results: a classical result of Haussler-Welzl on spanning trees (1987), the Alon-Kleitman proof of Hadwiger-Debrunner conjecture (1992), and a recent result (Mustafa-Ray, 2012) on extending some classical theorems (e.g., Radon's theorem, Caratheodory's theorem) in discrete geometry.
Joint work with Saurabh Ray.

Lundi 27 mai Menelaos Karavelas (University of Crete) Towards an upper bound theorem for the Minkowski sum of convex polytopes In this talk we will consider the following problem: given \(r\) convex \(d\)-polytopes \(P_1,P_2,\ldots,P_r\) in \(\mathbb{R}^d\), what is the maximum number of \(k\)-faces of their Minkowski sum, for all \(-1\le k\le d-1\)?
We will concentrate on the case \(r=2,3\) (two/tree \(d\)-polytopes), and talk about exact tight worst-case bounds for all \(k\)'s. We will hint on the ideas behind our on-going work for the case \(r\ge 4\) (four or more \(d\)-polytopes), which is bascially a generalization of the procedure used by McMullen to prove the upper bound theorem for convex polytopes in the 1970's. Time permitting, we will also discuss a lower bound construction that produces a tight asymptotic expression for the complexity of the Minkowski sum when \(2\le r\le d-1\).
This is past and on-going work jointly done with Eleni Tzanaki and Christos Konaxis.

Lundi 3 juin Kolja Knauer (I3M, Université de Montpellier 2) Three ways to cover a graph We consider the problem of covering a host graph \(G\) with several graphs from a fixed template class \(T\). The (classical) covering number of \(G\) with respect to \(T\) is the minimum number of template graphs needed to cover the edges of \(G\). Parameters that arise this way are for example thickness, track-number and all kinds of arboricities. We introduce two new covering parameters: the local and the folded covering number. As in the global covering number each measures how far \(G\) is from the template class in a certain sense. The folded covering number has been investigated thoroughly for some template classes, e.g., interval graphs and planar graphs, yielding interval and splitting number, respectively. The local covering number was given only little attention. The three covering numbers presented not only unify the notion in the literature, they as well seem interesting in their own right, e.g., provide new approaches to attack or support classical open problems. We provide new bounds on some covering numbers w.r.t. several template classes. The classical graph parameters turning up this way are interval-number, track-number, and linear-, star-, and caterpillar arboricity. As host graphs we consider graphs of bounded degeneracy, bounded degree, or bounded tree-width, as well as, outerplanar, planar bipartite and planar graphs. We also discuss some algorithmical questions. Joint-work with Torsten Ueckerdt.

Lundi 10 juin Cédric Boutillier (LPMA) Quelques aspects du modèle de dimères plan Le modèle de dimères est un modèle de mécanique statistique qui représente le dépôt sur la surface d'un cristal (graphe) de molécules diatomiques (arêtes). Dans les années 1960, Kasteleyn et indépendamment Temperley et Fisher, introduisent un formalisme pour calculer le nombre de configurations à l'aide de déterminants. Le modèle a connu un regain d'intérêt au tournant du siècle, et une profusion de résultats ont été obtenus en développant des techniques autour de ce formalisme déterminantal. Nous présenterons certains de ces résultats et les idées essentielles à leur démonstration.

Lundi 17 juin Guillaume Chapuy (LIAFA, Paris 7) L'énumération des factorisations d'un élément de Coxeter en produit de réflexions Une formule classique dit que le nombre de factorisations du long cycle \((1,2,...,n)\) en produit de \(n-1\) transposition est \(n^(n-2)\). Je m'intéresserai à deux généralisations de cette formule: la première, qui concerne les factorisations de «genre \(g>0\)», c'est à dire en \(n-1+2g\) transpositions, est due à Shapiro, Shapiro, et Vainshtein. La seconde, où l'on remplace \(\mathfrak{S}_n\) par n'importe quel sous groupe fini de \(\mathrm{GL}(n)\) engendré par des réflexions, et le long cycle par un «élément de Coxeter» est due à Deligne puis Bessis. Je présenterai alors notre nouvelle formule, qui généralise les deux simultanément : nous traitons le cas de factorisations «de genre supérieur» dans n'importe quel groupe de réflexion complexe fini bien engendré - en particulier dans les groupes de Coxeter finis. Les buts de l'exposé seront (1) de présenter succinctement les groupes de réflexions (réels et complexes) (2) d'expliquer comment on peut aborder les questions de comptage de factorisations à l'aide de la théorie des représentations des groupes (3) de dire que toutes ces formules sont d'autant plus intéressantes qu'on les comprend encore très mal. Je m'excuse pour les gens qui verront le même exposé trois jours plus tard aux journées cartes. (Travail commun avec C. Stump.)

Mercredi 25 septembre Vincent Pilaud (LIX) Associaèdres d'arbres signés Un associaèdre est un polytope dont les sommets correspondent aux triangulations d'un polygone convexe et dont les arêtes correspondent aux flips entre ces triangulations. J.-L. Loday en a donné une réalisation particulièrement élégante qui a été généralisée ensuite dans deux directions : d'un côté par C. Hohlweg et C. Lange pour obtenir de multiples réalisations de l'associaèdre paramétrées par une séquence de signes, et de l'autre par A. Postnikov pour obtenir une réalisation des associaèdres de graphes de M. Carr et S. Devadoss. Le but de cet exposé est de présenter une généralisation commune de ces constructions aux associaèdres d'arbres signés. Nous présenterons aussi les riches propriétés combinatoires et géométriques des polytopes qui en résultent. L'exposé sera illustré par le cas de l'associaèdre classique, dont l'interprétation en termes d'épine dorsale (arXiv:1307.4391, travail en commun avec C. Lange) est le fil directeur de ce travail.

Mercredis 2, 9 et 16 octobre Christophe Hohlweg (LACIM, UQÀM) Mots et racines dans les groupes de Coxeter Cette série d’exposés se veut une invitation à l’étude de la combinatoire des racines et des mots réduits dans les groupes de Coxeter infinis. Les liens combinatoires entre racines et mots jouent un rôle fondamental dans l’étude de ces groupes et de leurs structures connexes ; ils sont, par exemple, au cœur de la preuve de Brink et Howlett du fait que les groupes de Coxeter sont des groupes automatiques.
Nous commencerons par une introduction aux groupes de Coxeter en insistant particulièrement sur les liens entre mots réduits et racines et en illustrant le tout dans les exemples classiques (groupe symétrique, groupes de réflexions réels). Dans un deuxième temps nous parlerons d’un ordre particulier, appelé « ordre faible », qui joue un rôle de premier ordre dans l’étude des mots réduits, ainsi que dans l’étude des permutoèdres et des associaèdres dans le cas fini. Finalement, nous discuterons du cas des groupes de Coxeter infinis pour lesquels la combinatoire des mots et des racines ne demande qu’à être développée. Nous parlerons en particulier de la généralisation de la notion de mots et d’ordre faible ainsi que d’ensembles d’inversion et d’ensemble « biclos » de racines.

Mercredi 23 octobre Andreas Holmsen (Department of Mathematical Sciences, KAIST) A combinatorial version of the colorful Caratheodory theorem In 1982, Barany discovered what he called the colorful Caratheodory theorem. Since then numerous « colorful » theorems in combinatorial convexity have appeared. Apart from their inherent charm, these results also have deep applications in discrete and computational geometry which appear to be inaccessible by the classical versions of the theorems. In this talk I will present a combinatorial result dealing with the intersection of a matroid and an oriented matroid, which contains Barany's result as a special case.
No background knowledge of matroids (oriented or not) will be required as all the necessary notions will be introduced.

Lundi 28, mardi 29, et mercredi 30 octobre Journées ANR EGOS Exposés le matin, discussions l'après-midi.
Programme (les résumés et certains transparents sont disponibles ici) :

28/10, 10h - Daniel Goncalves (LIRMM), On attempts to generalize Schnyder woods to other oriented surfaces (résume)
28/10, 11h30 - Michel Pocchiola (IMJ), Arrangements de double pseudodroites (resume)
29/10, 10h - Kolja Knauer (I3M, Montpellier), Making Octants Colorful (résume)
29/10, 11h30 - Éric Colin de Verdière (DI, ENS), Algorithmes topologiques pour les graphes tracés sur des surfaces (résume)
30/10, 10h - Anatolii Kostrygin (X 2010), Dessin de graphes planaires sur une grille polynomiale avec bord rectangulaire périodique (résume)
30/10, 11h30 - Nicolas Bonichon (LaBRI), Spanners planaires de degré borné (résume)

Mercredi 6 novembre Grégory Chatel (LIGM, Université Paris-Est) Comptage du nombre d'arbres plus petits dans l'ordre de Tamari Nous introduisons un nouvel objet, les intervalles-posets, pour encoder les intervalles de Tamari. Nous donnons ainsi une interprétation combinatoire à la forme bilinéaire qui apparaît dans l'équation fonctionnelle des intervalles de Tamari que donne Chapoton. De cette façon, nous retrouvons d'une nouvelle manière cette équation fonctionnelle et prouvons que le polynôme calculé récursivement à partir de la forme bilinéaire pour chaque arbre \(T\) compte le nombre d'arbres plus petits que \(T\) dans l'ordre de Tamari.

Mercredi 13 novembre Éric Fusy (LIX) Bijections pour cartes \(d\)-angulées Nous présentons une méthode bijective générale pour les cartes planaires, basée sur certaines orientations, appliquée ici à deux familles de cartes \(d\)-angulées: les \(d\)-angulations de maille \(d\) (tous les cycles ont taille au moins \(d\)), et les dissections irréductibles \(d\)-angulées (où les seuls cycles de longueur \(\le d\) sont les contours de faces internes).
Travail en commun avec Olivier Bernardi

Mercredi 20 novembre Jérôme Tomasini (LAREMA, Université d'Angers) Sur les revêtements ramifiés de la sphère Cette exposé reposera sur deux parties distinctes. Tout d’abord, nous nous intéresserons à la notion de revêtements ramifiés de la sphère par elle-même, que nous définirons au préalable, afin de lui associer une structure combinatoire simple reposant sur des cartes planaires biparties. Cette première partie repose essentiellement sur un résultat de W. Thurston. Puis nous donnerons quelques propriétés sur ces cartes, ainsi que plusieurs résultats de décomposition, pour finir (si le temps le permet) par montrer un lien simple entre ces cartes et le problème d’Hurwitz.

Mercredi 4 décembre Maciej Dolega (Instytut Matematyczny, Uniwersytet Wrocławski) Central limit theorem for random Young diagrams with respect to Jack measure In 1977 Vershik and Kerov and independently Logan and Shepp discovered that large random Young diagrams with respect to Plancherel measure concentrate around some explicit limit shape. In 1993 Kerov showed that the fluctuations around that limit shape are Gaussian. Jack measure is a probability measure on the set of Young diagrams of fixed size which is parametrized by a positive real value \(\alpha\). For \(\alpha = 1\) Jack measure coincide with the Plancherel measure, hence it can be considered as a continous deformation of the Plancherel measure. We present a central limit theorem for the Jack measure which gives an extension of the results of Vershik-Kerov (Legan-Shepp) and Kerov for the Plancherel measure.

Mercredi 11 décembre Robin Langer (LIGM, Université Paris-Est) Lambda Determinants Alternating sign matrices were discovered by Robbins and Rumsey whilst studying lambda-determinants. In this talk I will discuss a multi-parameter generalization of the lambda-determinant which extends a recent result by di Francesco. Like the original lambda-determinant, our formula exhibits the Laurent phenomenon.

Mercredi 18 décembre Xavier Pérez-Giménez (University of Waterloo) Arboricity and spanning-tree packing in random graphs with an application to load balancing We study the arboricity \(A\) and the maximum number \(T\) of edge-disjoint spanning trees of the Erdös-Rényi random graph \(G(n,p)\). For all \(p(n) \in [0,1]\), we show that, with high probability, \(T\) is precisely the minimum between \(\delta\) and \(\lfloor m/(n-1) \rfloor\), where \(\delta\) is the smallest degree of the graph and \(m\) denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for \(p\) such that:

above this threshold, \(T\) equals \(\lfloor m/(n-1) \rfloor\) and \(A\) equals \(\lceil m/(n-1) \rceil\);
and below this threshold, \(T\) equals \(\delta\), and we give a two-value concentration result for the arboricity \(A\) in that range.

Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most \(k\) in the two-choice load balancing problem, where \(k \to \infty\). This research is joint work with Pu Gao and Cristiane M. Sato.

Mercredi 18 décembre Gwendal Collet (LIX) Une bijection pour les cartes simples Marc Noy a récemment découvert une formule élégante reliant la série génératrice des cartes simples (sans boucles ni arêtes multiples, aussi appelés plane graphs) selon le nombre arêtes, et celle des triangulations eulériennes selon le nombre de faces. En collaboration avec Éric Fusy, afin de retrouver cette formule, nous avons exhibé une bijection originale reposant sur l'existence d'orientations canoniques sur ces objets, mais sans passer par l'intermédiaire d'arbres décorés. Cette bijection permet également de donner une expression bivariée pour la série des cartes simples selon les arêtes et les sommets, ainsi que de produire un générateur aléatoire efficace.