Séminaire de l'équipe Géométrie, Combinatoire et Algorithmes

• Orateur/Speaker : Jaroslav Nesetril, Charles University, Prague
• Titre/Title : On the Category of Graphs
• Résumé/Abstract
  Despite of the title we hope to demonstrate the richness of the approach to combinatorial problems using categorical reasoning. No previous knowledge of CT is necessary.

• Orateur/Speaker : Jaroslav Nesetril, Charles University, Prague
• Titre/Title : Constraint Satisfaction and Sparse Structures
• Résumé/Abstract
  How complex are Constraint Satisfaction Problems when restricted to sparse instances? The answer depends on the notion of sparsity and we shall survey the recent development in this direction.

• Orateur/Speaker : Ioannis Emiris, Université d'Athènes
• Titre/Title : Implicitisation des courbes et des surfaces paramétrées par des méthodes combinatoires
• Résumé/Abstract
  Un problème important en modélisation géométrique consiste à déterminer la forme implicite d'une courbe ou surface, étant donnée sa représentation paramétrique.
  Nous présentons des méthodes pour calculer le support ou, plus précisément, le polytope de Newton de l'équation implicite, en réduisant ainsi le problème initial à une question d'algèbre linéaire.
  Nos algorithmes se basent sur la théorie d'élimination creuse et du résultant creux (ou torique), ce qui nous permet d'exploiter la structure creuse des équations paramétriques.
  Ces méthodes font appel à la géométrie combinatoire, et les triangulations régulières. On esquisse aussi une approche alternative qui utilise la géométrie tropicale.

• Orateur/Speaker : Micha Sharir, Tel Aviv University
• Titre/Title : Weak epsilon-nets, stabbing interval chains, and Davenport-Schinzel sequences
• Résumé/Abstract
  We present improved upper bounds for the size of weak epsilon-nets for convex ranges and point sets in convex position in the plane, and for points on the moment curve in higher dimensions.
  
  (A weak epsilon-net for a point set P is a set N of points (not necessarily a subset of P), with the property that the convex hull of any subset of epsilon*|P| points of P contains a point of N.
  
  The bounds that we derive involve the inverse Ackermann function. For example, for point sets in convex position in the plane, we obtain a bound of O(r\alpha(r)) for the size of weak (1/r)-net.
  
  Some nontrivial lower bounds were also obtained, more recently.
  
  The proof is via a reduction to an interesting combinatorial problem (stabbing interval chains) which apparently has not been studied before. We provide sharp upper and lower bounds for this problem.
  
  These bounds are suspiciously similar to the bounds on the maximum length \lambda_s(n) of Davenport-Schinzel sequences. My Ph.D. student Gabriel Nivasch has followed this cue, and managed to improve, and essentially tighten, the bounds for \lambda_s(n) for even values of s. In the process, several new insights on Davenport-Schinzel sequences were discovered, including a new formulation of the seqeunces, leading to new questions and new bounds.
  
  (Joint work with Gabriel Nivasch, Noga Alon, Haim Kaplan, and Shakhar Smorodinsky.)

• Orateur/Speaker : Micha Sharir, Tel Aviv University
• Titre/Title : Improved bounds and new proofs for epsilon-nets
• Résumé/Abstract
  We present an improved upper bound of O(r\log\log r) for the size of (standard, "strong") (1/r)-nets (required to be subsets of the given point set) for points and axis-parallel rectangles in the plane (or boxes in 3-space). The new paradigm can also be extended to other instances. This is work in progress, and we are still trying to understand all the implications of the new technique.
  
  (Joint work with Esther Ezra and Boris Aronov.)
  
  Finally, we have re-examined the old results on the existence of epsilon-nets of size O(1/epsilon) for halfspaces in two and three dimensions, and have come up with *many* new and simple proofs. Again, this is work in progress and we are trying to apply the new proofs to several new instances as well.
  
  (Joint work with Esther Ezra, Sariel Har-Peled, Haim Kaplan, and Shakhar Smorodinsky.)

• Orateur/Speaker : Vincent Pilaud, Ens
• Titre: Énumération des arrangements de cinq double pseudodroites
• Title : Enumerating arrangements of five double pseudolines
• Résumé
  Les arrangements de pseudodroites (ou de pseudohyperplans en dimension supérieure) ont été largement étudiés comme abstraction combinatoire de configurations de points. Récemment, Habert et Pocchiola ont introduit les arrangements de double pseudodroites pour étudier les configurations de convexes disjoints du plan projectif. Les principales propriétés structurelles des arrangements de pseudodroites (plongeables dans un plan projectif géométrique, connexité du graphe des mutations, caractérisation axiomatique) se généralisent aux arrangements de double pseudodroites.
  Pour étudier ces objets et expérimenter des conjectures sur les petits cas, nous avons implémenté un algorithme incrémental d'énumération des arrangements mixtes de pseudodroites et double pseudodroites. Nous présentons l'algorithme et son implémentation.
  (travail en commun avec Julien Ferté et Michel Pocchiola)
• Abstract
  Pseudoline arrangements (or in higher dimension, pseudohyperplane arrangements) have been extensively studied in the last decades as a useful combinatorial abstraction of configurations of points. Recently, Habert and Pocchiola introduced double pseudoline arrangements as a combinatorial abstraction of projective configurations of disjoint convex bodies. The main structural properties of pseudoline arrangements (embedability in a geometric projective plane, connectivity of the mutation graph, axiomatic characterization) extend to double pseudoline arrangements.
  In order to carry out computer experiments, we have implemented an incremental algorithm to enumerate mixed arrangements, that is, with both pseudolines and double pseudolines. We present this algorithm and its implementation.
  (joint work with Julien Ferté and Michel Pocchiola)

• Orateur/Speaker: Francisco Santos, Santander, Espagne
• Titre/Title: Triangulations of polytopes
• Résumé/Abstract :
  Triangulations of polytopes play an important role in several parts of mathematics, both pure and applied. This course is an introduction to them, focusing in the theory of regular triangulations and secondary polytopes developed in the last twenty years. We will follow the first half of the forthcoming book by J. A. de Loera, J. Rambau and F. Santos, specially chapters 2, 4 and 5. The current version of the book can be downloaded here
  
  As prerequisites, a certain familiarity with polyhedral combinatorics will be helpful, but will not be strictly required.

• Orateur/Speaker : Luca Castelli Aleardi, ULB
• Titre/Title : Schnyder woods for higher genus triangulated surfaces
• Résumé/Abstract

• Orateur/Speaker : Guillaume Chapuy
• Titre/Title : Sur la structure des cartes à une face
• Résumé/Abstract

• Orateur/Speaker : John Harer, Duke University
• Titre/Title : Persistent homology - Finding global shape in datasets
• Résumé/Abstract

• Orateur/Speaker : Franck Nielsen, Sony CSL/Ecole Polytechnique
• Titre/Title : On the Centroids of Symmetrized Bregman Divergences
• Résumé/Abstract

• Orateur/Speaker : Éric Colin de Verdière, ENS Paris, CNRS
• Titre/Title : Plus courts chemins disjoints dans un graphe planaire
• Résumé/Abstract

• Orateur/Speaker : Jürgen Bokowski, TU Darmstadt
• Titre/Title : Oriented matroids, i.e., a natural extended equivalence class of matrices, with applications to polyhedral embeddings and point line configurations
• Résumé/Abstract

• Orateur/Speaker : Yves Bertot, Inria, Sophia Antipolis
• Titre/Title : Formalisation d'algorithmes de géométrie: le cas des enveloppes convexes, CC-systèmes et contournement des problèmes de dégénérescence
• Résumé/Abstract

• Orateur/Speaker : Vincent Pilaud , Ecole Normale Supérieure, Paris
• Titre/Title : Etoiles et multi-triangulations
• Résumé/Abstract