Séminaire de l'Équipe Modèles Combinatoires - 2012
9 janvier 2012 Nicolas Bonichon (LaBRI) Spanner géométrique planaire de degré au plus 6 We consider the problem of constructing planar spanners of Euclidean graphs with the smallest maximum degree. We present a 6-spanner of degree bound by 6. The best previous bound on the degree of planar spanner was 14 with a stretch of \(\approx 3.53\). The spanner we proposed can be easily computed the Triangular Distance Delaunay triangulation introduced by Chew in 1989, that is known to have a stretch factor of 2 but its degree may not be bounded.
Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et Ljubomir Perković.
16 janvier 2012 Omid Amini (ENS) Théorème de Riemann-Roch tropical Je présente un survol des résultats récents autour du théorème de Riemann-Roch en géométrie tropicale.
20 janvier 2012 Jarek Rossignac (Georgia Tech) Mesh parsimony: Towards compact formats for processing and transmitting triangulations Modern representations of 3D shapes in Engineering, Scientific, Medical, and Entertainment domains are based on triangulations. The constant increase in the fidelity and hence complexity of these models increases storage cost and hence adversely impacts transmission and processing performance. To address this problem, we discuss compact formats for transmitting and processing triangulations. On the practical side, we review the Corner-Table (CT) a representation for triangle meshes, where the connectivity is encoded as 13 rpv (references per vertex) and the associated standard sets of random, mesh-traversal corner-operators. Its simplicity and compactness makes it a prime choice for teaching and implementing mesh-processing algorithms. We also discuss its VOT extension to tetrahedral meshes, which requires storing about 48 rpv, and the associated mesh-traversal wedge-operators. Then, we review the popular triangle-mesh compression, Edgebreaker, which requires about 2 bpv (bits per vertex) and can be implemented with a few lines of code, and discuss some improvements and extensions to tetrahedral meshes, including TetStreamer, which requires only about 10 bpv. Finally, we discuss recent advances in compact mesh-representations that support the corner-operators and wedge-operators at constant cost. These include SOT (which halves the storage requirements of CT and VOT), SQuad for triangle meshes (which requires 4 rpv), and LR (which orders the vertices around a nearly Hamiltonian cycle and requires only about 1.6 rpv). On the theoretical side, we cast the recent approaches as special cases of the catalogue approach of Castelli-Aleardi & Devillers, investigate the role of re-orderings and the interplay between compression, streaming, and random-access support, and seek to extract the essential information that is captured in the connectivity of a triangle mesh.
The talk is based on joint work with U. Bischoff, T. Gurung, P. Lindstrom, M. Luffel, and A. Szymczak and other colleagues.
12 mars 2012 Xavier Goaoc (LORIA, INRIA) Autour des nombres de Helly Dans cet exposé, je relierai le théorème de Helly sur l'intersection d'ensembles convexes (1913) à diverses questions récentes de nature algorithmique, combinatoire et topologique. L'exposé sera destinés aux non-spécialistes et ne supposera aucune de ces notions connues.
Issu d'un travail commun avec Éric Colin de Verdière (CNRS-ENS) et Grégory Ginot (UPMC-ENS).
23 mars 2012 Christian Stump (Hannover) A bijection between \(k\)-triangulations and \(k\)-fans of Dyck paths I will present a bijection between \(k\)-triangulations of the \(n\)-gon and \(k\)-fans of Dyck paths. This bijection goes through maximal north-east fillings of triangles, pipe dreams, flagged tableaux, and plane partitions.
This is joint work with Luis Serrano.
14 mai 2012 Louigi Addario-Berry (Mc Gill Montréal) The spectrum of random lifts For a fixed \(d\)-regular graph \(H\), a random \(n\)-lift is obtained by replacing each vertex \(v\) of \(H\) by a “fibre” containing \(n\) vertices, then placing a uniformly random perfect matching between adjacent fibres. We show that with high probability, all eigenvalues of the adjacency matrix \(A\) of the lift, that are not eigenvalues of \(H\) (“new” eigenvalues), have order \(O(\sqrt{d})\), and that any exceptionally large new eigenvalues are whp caused by a dense subgraph of size \(O(|E(H)|)\). Our key tools are (1) a convexity argument which yields exponential bounds number of “test” vectors we need to consider when bounding the largest new eigenvalue, and (2) a reduction which, given a vector \(v\) with \((Av,v)\) large, produces another, sparser vector \(v'\) satisfying \((Av,v)=O((Av',v'))\) and such that \(v'\) in a sense encodes the reasons why \((Av,v)\) is large.
Joint work with Simon Griffiths.
PDF Lundi 17 septembre 2012 Axel Bacher (LIPN, Paris) Animaux dirigés et multi-dirigés sur le réseau Union Jack Soit \(R\) un réseau orienté. Un animal dirigé de source \(s\) sur le réseau \(R\) est un ensemble fini de sommets contenant \(s\) et tel que tout point de l'animal peut être atteint depuis \(s\) par un chemin orienté ne visitant que des sommets de l'animal.
On s'intéressera ici aux animaux dirigés sur le réseau Union Jack dirigé, qui est le réseau \(\mathbb Z^2\) muni des arcs \(\{(-1,0),(-1,1),(0,1),(1,1), (1,0)\}\). Nous montrerons comment étendre des résultats classiques d'énumération des animaux dirigés sur ce réseau. Nous étendrons aussi à ce réseau la classe des animaux multi-dirigés, une généralisation des animaux dirigés introduite par Bousquet-Mélou et Rechnitzer.
PDF Lundi 17 septembre 2012 Thomas Lewiner (PUC, Rio de Janeiro) Un peu de théorie de Morse combinatoire La théorie de Morse est un outil très utile en géométrie et en topologie différentielles, offrant souvent des preuves élégantes et intuitives de résultats complexes sur les variétés. R. Forman a proposé une formulation combinatoire de cette théorie, en formulant les relations différentielles par des mariages sur les graphes extraits de variétés (et non-variétés) discrètes. Ce séminaire propose une introduction de cette théorie, en cherchant à relier certains de ses aspects combinatoires et topologiques et en présentant quelques résultats récents.
PDF Lundi 1 octobre 2012 Michael Albert (University of Otago, Nouvelle-Zélande) New perspectives on the enumeration of permutation classes A permutation class is a collection of permutations closed downwards in a natural ordering. Early research about permutation classes tended to concentrate on specific enumerative results. I will describe a sequence of ideas which lead to the most general known results about the structure and hence enumerative properties (specifically, the rationality or algebraicity of generating functions) for a collection of such classes. One particular consequence is that all “small” classes have rational generating functions. I will also illustrate how these ideas can be a guide for the actual enumeration of some specific classes.
PDF Lundi 8 octobre 2012 Gwendal Collet (LIX) Formules bijectives pour les cartes (quasi-)biparties avec bords Nous présenterons deux nouveaux résultats d’énumération sur les cartes planaires obtenus par des méthodes bijectives. La première formule porte sur les cartes biparties avec un nombre fixé de bords (faces marquées) de longueur arbitraire. Elle est obtenue en exploitant une bijection déjà connue entre cette famille de cartes et une famille d’objets appelés mobiles. En décomposant ces mobiles, nous établissons une correspondance \((n−1)!\)-à-\((n−1)!\) dont découle la formule recherchée. La deuxième formule est une extension de la première aux cartes quasi-biparties, dont au plus deux bords sont de longueur impaire, en adaptant la méthode précédente.
PDF Lundi 15 octobre 2012 Jérémie Bettinelli (Institut Élie Cartan, Nancy) Croissance de cartes planaires par une approche bijective Au cours de cet exposé, je présenterai des bijections sur les cartes planaires permettant de faire varier certains paramètres. En particulier, cela permet de rajouter une face à une quadrangulation uniforme ou d'augmenter la taille du bord d'une quadrangulation à bord. On peut également retrouver directement la formule des slicings de Tutte comptant les cartes planaires dont les faces ont des degrés prescrits, deux au plus de ces degrés étant impair. La stratégie générale de ces bijections consiste à définir convenablement un chemin dans la carte initiale, à couper le long de ce chemin, puis à recoller avec un léger décalage, ce qui modifie légèrement la structure de la carte.
PDF Lundi 22 octobre 2012 Juanjo Rué (ICMAT, Madrid) On the probability of planarity of a random graph near the critical point Consider the uniform random graph \(G(n,M)\) with \(n\) vertices and \(M\) edges. Erdös and Rényi (1960) conjectured that the limit \[ \lim_{n \to \infty} \Pr\,\{G(n,\textstyle{n \over 2}) \text{ is planar}\} \] exists and is a constant strictly between \(0\) and \(1\). Luczak, Pittel and Wierman (1994) proved this conjecture and Janson, Luczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this talk we show how to determine the exact probability of a random graph being planar near the critical point \(M=n/2\). More exactly, for each \(\lambda\), we find an exact analytic expression for \[ p(\lambda) = \lim_{n \to \infty} \Pr\,\{G(n,\textstyle{n\over 2}(1+\lambda n^{-1/3})) \text{ is planar}\}.\] In particular, we obtain \(p(0) \approx 0.99780\). If time permits we will show extensions of these techniques and further research.
This is a joint work with Marc Noy (UPC-Barcelona) and Vlady Ravelomanana (LIAFA-Paris)
PDF Lundi 12 novembre 2012 Vivien Ripoll (LACIM, UQAM, Montréal) Racines-limites des systèmes de racines de groupes de Coxeter Étant donné un groupe de Coxeter \(W\), on peut le représenter géométriquement comme groupe engendré par des réflexions. Un système de racines de \(W\) est un ensemble de vecteurs qui encodent les réflexions de \(W\). Notre objet d'étude est l'ensemble \(E\) des points d'accumulation des directions des racines, qu'on appellera racines-limites. Nous verrons d'abord sur des exemples illustrés en rang \(2\), \(3\), et \(4\) l'aspect fractal que peut avoir cette forme limite \(E\). Puis nous expliquerons quelques résultats généraux découverts récemment sur les racines-limites (propriétés d'une action de \(W\) sur \(E\), enveloppe convexe de \(E\)...).
Travaux en collaboration avec M. Dyer, Ch. Hohlweg et J.-P. Labbé.
PDF Lundi 19 novembre 2012 Basile Morcrette (Inria Rocquencourt et LIP6, UPMC) Urnes de Polya algébriques La suite des tirages dans une urne de Polya équilibrée additive peut se voir comme une marche dans le quart de plan, où les pas sont pondérés. Dans le cas classique des marches dans le quart de plan, la question de la nature de la série génératrice a été traitée récemment par Bousquet-Mélou et Mishna, Bostan et Kauers, Fayolle et Raschel. Nous nous posons ici le même problème dans le cadre des urnes de Polya équilibrées: quelles séries génératrices sont algébriques?
Par une approche automatique de Guess'n'Prove, nous exhibons un ensemble de cas où la série est algébrique. Cela nous amène à une classification partielle de ces urnes. Nous obtenons ensuite des preuves élémentaires d'algébricité. Enfin, une étude analytique (utilisant analyse de singularité et méthode de cols coalescents) permet de conclure sur les lois limites de ces urnes.
PDF Lundi 26 novembre 2012 Nicolas Delfosse (LIX) Percolation et codes correcteurs quantiques Les codes topologiques sont des codes correcteurs quantiques définis à partir de graphes plongés dans une surface. Ils ont été introduits par Kitaev, qui a proposé de construire un code quantique basé sur un pavage carré du tore. Nous commençons par rappeler comment les paramètres du code quantique s'expriment en fonction des propriétés du graphe. Nous observons ensuite la ressemblance entre effacements quantiques et phénomène de percolation. En utilisant cette ressemblance, nous obtenons une borne sur le seuil de percolation d'une famille de graphes hyperboliques, à partir de résultats de théorie de l'information quantique.
Travail commun avec Gilles Zémor.
PDF Lundi 3 décembre 2012 Robert Cori (LaBRI et LIX) La notion de rang pour les configurations sur un graphe et un résultat qui rappelle la formule de Riemann-Roch Plusieurs modèles de physique statistique consistent à considérer un graphe et des entiers associés aux sommets, une règle de transition entre les configurations est aussi définie.
On examinera celle qui a été introduite pour le modèle du tas de sable mais avec des conditions légèrement différentes. Pour ce modèle, Baker et Norine ont défini une notion de rang, ceci les a amenés à prouver une formule qui présente de grandes similitudes avec celle de Riemann-Roch. Je présenterai une nouvelle preuve plus combinatoire de ce résultat et proposerai une étude du cas du graphe complet. Cela conduit à introduire des polynômes symétriques à deux variables qui peuvent être considérés comme des $q,t$-analogues des nombres de Catalan.
Cet exposé présente des résultats d'un travail en commun avec Yvan Le Borgne.
PDF Lundi 10 décembre 2012 Philippe Nadeau (Institut Camille Jordan, Univ. Lyon I) Eléments totalement commutatifs et chemins du plan Un élément d'un groupe de Coxeter \(W\) est dit “totalement commutatif” si deux de ses décompositions réduites peuvent toujours être reliées par une suite de transpositions de générateurs adjacents et qui commutent. Ces éléments ont été étudiés en détail par Stembridge dans le cas où \(W\) est fini. Ils indexent une base d'un quotient de l'algèbre de Hecke de \(W\), correspondant à l'algèbre de Temperly-Lieb dans le cas où \(W\) est de type A. Nous considérons ici \(W\) fini ou affine, et énumérons les éléments totalement commutatifs selon leur longueur de Coxeter. Notre approche consiste à encoder ces éléments par diverses classes de chemins du plan que nous décomposons récursivement pour obtenir les fonctions génératrices voulues. Pour le type \(A\) fini, cela redonne un théorème de Barcucci et al.; pour \(A\) affine, cela simplifie et précise des résultats de Hanusa et Jones. Pour tous les autres groupes finis et affines, nos résultats sont nouveaux.
Cet exposé est basé sur un travail en collaboration avec Riccardo Biagioli et Frédéric Jouhet (Lyon).
PDF Lundi 17 décembre 2012 Alice Jacquot (LIPN) Génération aléatoire d'arbres de Motzkin “à la Rémy” Une spécification holonome est une spécification combinatoire différentielle (faisant intervenir des opérateurs de pointage) linéaire à coefficients polynomiaux. Nous donnons une telle spécification pour les arbres de Motzkin, dont nous nous servons pour obtenir un générateur de Boltzmann. Puis, nous transformons ce générateur en générateur en taille exacte, donnant en algorithme “à la Rémy”, en temps et espace linéaire en moyenne.
Travail commun avec Olivier Bodini et Axel Bacher

Valid XHTML 1.0 Strict CSS Valide !