Séminaire de Géométrie Algorithmique et Combinatoire
Exposés passés
Retour à la page principale du séminaire
24 mai 2018
14h Olivier Devillers Loria, Nancy
Walking in Poisson Delaunay triangulations
The talk will review some results about several walking strategies between $(0,0)$ and $(1,0)$ in the Delaunay triangulation of points distributed according to Poisson law of large intensity $n$. We provide a first non-trivial lower bound for the distance on the expected length of the shortest path of $1+10^{-11}$. Simulations indicate that the correct value is about $1.04$. We also prove results about the expected length of paths produced by various algorithms:
  • The Voronoi path has an expected length of $4/\pi$.
  • The expected length of the upper path converges to $35/(3\pi^2)$ when intensity goes to infinity.
In dimension $d$, we prove that the expected length of the Voronoi path has length $\sqrt{2d/\pi}+O(1/\sqrt{d})$ when $d$ goes to infinity. In any dimension, we provide a precise interval containing the actual value; in 3D the expected length is between $1.4977$ and $1.50007$.
Joint work with Nicolas Chenavier, Louis Noizet, and Pedro M. M. de Castro.
15h30 Julien Tierny LIP6, Paris
The Topology ToolKit
This talk will present the Topology ToolKit (TTK), a software platform designed for the topological analysis of scalar data in scientific visualization. While topological data analysis has gained in popularity over the last two decades, it has not yet been widely adopted as a standard data analysis tool for end users or developers. TTK aims at addressing this problem by providing a unified, generic, efficient, and robust implementation of key algorithms for the topological analysis of scalar data, including: critical points, integral lines, persistence diagrams, persistence curves, merge trees, contour trees, Morse-Smale complexes, fiber surfaces, continuous scatterplots, Jacobi sets, Reeb spaces, and more. TTK is easily accessible to end users due to a tight integration with ParaView. It is also easily accessible to developers through a variety of bindings (Python, VTK/C++) for fast prototyping or through direct, dependency-free, C++, to ease integration into pre-existing complex systems. While developing TTK, we faced several algorithmic and software engineering challenges, which I will describe in this talk. In particular, I will present an algorithm for the construction of a discrete gradient that complies to the critical points extracted in the piecewise-linear setting. This algorithm guarantees a combinatorial consistency across the topological abstractions supported by TTK, and importantly, a unified implementation of topological data simplification for multi-scale exploration and analysis. We also present a cached triangulation data structure, that supports time efficient and generic traversals, which self-adjusts its memory usage on demand for input simplicial meshes and which implicitly emulates a triangulation for regular grids with no memory overhead. Finally, we describe an original software architecture, which guarantees memory efficient and direct accesses to TTK features, while still allowing for researchers powerful and easy bindings and extensions. TTK is open source (BSD license) and its code, online documentation and video tutorials are available on TTK’s website: https://topology-tool-kit.github.io/.
15 mars 2018
14h Xavier Allamigeon CMAP, École Polytechnique
A formalization of convex polyhedra based on the simplex method
We present a formalization of convex polyhedra in the proof assistant Coq. The cornerstone of our work is a complete implementation of the simplex method, together with the proof of its correctness and termination. This allows us to define the basic predicates over polyhedra in an effective way (ie, as Coq programs), and relate them with the corresponding usual logical counterparts. The benefit of this approach is that we can easily derive the proof of several essential results on polyhedra, such as Farkas Lemma, duality theorem of linear programming, and Minkowski Theorem. The talk doesn't require any prior knowledge on theorem proving. This is joint work with Ricardo D. Katz (CIFACIS-CONICET, Argentina).
15h30 Éric Colin de Verdière LIGM, CNRS & Univ. Marne-la-Vallée
Deciding contractibility of curves on the boundary of a $3$-manifold
In $3$-dimensional computational topology, one of the most important problems is the unknot problem: Is an input simple closed curve in $R^3$ unknotted? The seminal result by Hass, Lagarias, and Pippenger [JACM 1999] shows that the problem is in NP. Very recently, Lackenby proved that the problem is also in coNP. However, no subexponential-time algorithm is known.
I will briefly describe Hass et al.'s method, based on normal surface theory, and will explain why it provides an exponential-time algorithm for the following problem: Given a simple closed curve $c$ on the boundary of a $3$-manifold $M$, is $c$ contractible in $M$? Then, I will describe an exponential-time algorithm to solve the same problem, removing the restriction for $c$ to be simple. The main tool for this result, obtained together with Salman Parsa, is the loop theorem, a fundamental tool in the study of $3$-manifolds, which I will also explain.
8 février 2018
14h Kolja Knauer LIS, Université Aix-Marseille
Oriented matroids and beyond
Acyclic orientations of a graph, linear extensions of a poset, hyperplane arrangements, linear dissections of polyhedra, pseudoline arrangements... all of these can be seen as (complexes of) oriented matroids (COMs). The tope graph of a COM is a graph capturing all the information of this potentially quite complex object. In the above examples it corresponds to: the flip graph of acyclic orientations (two are linked by an edge if they differ in one arc), the linear extension graph of a poset (two are linked if they differ by one neighboring transposition), the region graphs of any of the other examples. In this talk, I will explain all these concepts carefully. Finally we will give a purely graph theoretic characterization of tope graphs of COMs, which furthermore is polytime verifyable. This answers a kind of central question in Oriented Matroid Theory and in a sense identifies the latter as a branch of Metric Graph Theory.
Based on joint work with Hans-Jürgen Bandelt, Victor Chepoi, and Tilen Marc.
15h30 Vincent Cohen-Addad CNRS, Univ. Paris 6
Local search for clustering type problems
Local search is a popular heuristic to find solutions to hard problems. How good are those solutions? There is a risk of getting stuck in a local optimum whose value is quite far from the optimal value. Here, we propose a broadened version of local search, where we enlarge the local neighborhood. Clustering problems aims to partition input data according to similarity. We will show that for several types of clustering problems, enlarged local search finds a nearly optimal solution. The key is to work in a space with good separability structure.
18 janvier 2018
14h Marie Albenque LIX, École Polytechnique
Limite d’échelle de cartes planaires aléatoires
Si les cartes planaires (plongements de graphes planaires dans la sphère) ont été introduites et énumérés par Tutte dans les années 60, ce n’est qu’au début des années 2000 que les premiers résultats (du à Chassaing et Schaeffer, puis à Marckert et Mokkadem) sur les cartes aléatoires ont été obtenus. Depuis, l’étude des cartes planaires aléatoires a connu un développement considérable. En particulier, il a été montré ces dernières années que de nombreuses familles de cartes planaires aléatoires convergeaient (après renormalisation) vers la carte brownienne introduite par Miermont et Le Gall en 2013. Je décrirai dans mon exposé le résultat de Miermont et Le Gall en le remplaçant dans son contexte et donnerai la preuve d’un résultat similaire obtenu pour les triangulations simples.
Au travers de cette preuve, j’essaierai de donner une intuition de la construction de la carte brownienne en m’appuyant principalement sur les constructions combinatoires qui sous-tendent la démonstration. L’exposé ne supposera connu aucun résultat combinatoire ni probabiliste !
Il s’agit d’un travail commun avec Louigi Addario-Berry.
15h30 Philippe Chassaing IEC, Université de Lorraine
Mosaïques poissoniennes et bootstrap percolation
On discutera les propriétés d’invariance d’une mosaïque poissonienne qui apparaît comme diagramme espace-temps à deux occasions au moins : pour un système balistique de particules en interaction d’une part, pour un modèle de bootstrap percolation sur $\mathbb{Z}$, avec guérison, d’autre part. (Collaboration avec Anne Briquet).
22 décembre 2017
14h Karim Bouyarmane LORIA, Nancy
The humanoid robot motion planning problem
The ability of an intelligent agent endowed with a physical (mechanical) body, to act and interact with its environment through physical motion, is a key ability to qualify the agent as intelligent. Humanoid robots are such agents. They are computers with physical embodiment, or « algorithms » that can act on the real world. A key component of their intelligence is thereby their ability to reason about their environment and their own body (both at geometrical level and physics level), and understand how they can move within this environment and interact with it (planning problem), as well as their ability to actually execute the motion, i.e. to perform a physical realization of the plan (control problem) confronting any idealized model used at planning time to the physical reality. We label both the motion planning and motion control problems as motion intelligence. Through humanoid robots, we try to emulate the human's self motion intelligence. The applications of this endeavor are multiple, from creating autonomous humanoid robots capable of executing high-level commands (physical motion-inducing tasks, which is their added value over other computers tasks), to understanding human motion and motor control, and efficiently assisting the humans in their motions through physical wearable devices or through physical collaboration with robots. The motion planning problem takes different levels of complexity when considering the different kinds of robotic embodiments (fixed-base industrial manipulator arms, wheeled mobile robots, four-legged or six-legged robots, flying drones, bipedal humanoids), each category having its own specificity, constraints, dimensionality, and proposed methods of resolution that proved more or less efficient over the years. We will give an overview of the motion planning problem and control for robots in general and focus on the case of humanoid robots, presenting both the early approaches and the recent advances and open problems on the topic.
16 novembre 2017
14h Sara Kalisnik Max Planck Institute for Mathematics in the Sciences
A Higher-Dimensional Homologically Persistent Skeleton
A data set is often given as a point cloud, i.e. a non-empty finite metric space. An important problem is to detect the topological shape of data — for example, to approximate a point cloud by a low-dimensional non-linear subspace such as a graph or a simplicial complex. Classical clustering methods and principal component analysis work very well when data points split into well-separated groups or lie near linear subspaces.
Methods from topological data analysis detect more complicated patterns such as holes and voids that persist for a long time in a 1-parameter family of shapes associated to a point cloud. These features can be visualized in the form of a 1-dimensional homologically persistent skeleton, which optimally extends a minimal spanning tree of a point cloud to a graph with cycles. We generalize this skeleton to higher dimensions and prove its optimality among all complexes that preserve topological features of data at any scale.
15h30 Marco Cuturi CREST - ENSAE , Université Paris-Saclay
Generative Models and Optimal Transport
A recent wave of contributions in machine learning center on the concept of generative models for extremely complex data such as natural images. These approaches provide principled ways to use deep network architectures, large datasets and automatic differentiation to come up with algorithms that are able to synthesize realistic images. We will present in this talk how optimal transport is gradually establishing itself as a valuable tool to carry out this estimation procedure.
12 octobre 2017
14h Marie-Paule Cani LIX, École Polytechnique
Modélisation expressive des mondes virtuels : Connaissances, distributions et contrôle en informatique graphique
Les avancées récentes en informatique graphique ont vu l'émergence de systèmes d'aide à la création, qui combinent des modèles géométriques contraints exprimant des connaissances a priori, avec un contrôle gestuel offert à l'utilisateur inspiré du dessin ou de la sculpture. Etendre cette «modélisation expressive» à la synthèse de mondes virtuels - typiquement des terrains parcourus de cours d'eau et peuplés de myriades d'éléments comme des rochers ou des plantes - demande d'associer contrôle utilisateur avec de multiples contraintes de cohérence, de la géomorphologie aux écosystèmes. Nous montrerons à travers une série d'exemples comment un contrôle interactif peut être entrelacé avec le maintien de la cohérence, et comment des outils issus de l'apprentissage statistique et de l'interpolation de distributions peuvent être exploités pour peupler les paysages.
15h30 Éric Fusy LIX, École Polytechnique
Combinatorics and applications of Schnyder woods
Schnyder woods are combinatorial structures on planar triangulations (maximal planar graphs embedded on the sphere) that can be formulated as a certain partition of the edges into 3 spanning trees. These structures have found many algorithmic applications, for instance in graph drawing, succinct encoding of meshes, efficient routing in planar networks, spanners, etc. I will present some of these applications, with an emphasis on the interplay with combinatorics.
22 juin 2017
14h Boris Bukh Carnegie Mellon University
One-sided epsilon-approximants
Two common approximation notions in discrete geometry are $\epsilon$-nets and $\epsilon$-approximants. Of the two, $\epsilon$-approximants are stronger. For the family of convex sets, small $\epsilon$-nets exist while small $\epsilon$-approximants unfortunately do not. In this talk, we introduce a new notion "one-sided $\epsilon$-approximants", which is of intermediate strength, and prove that small one-sided $\epsilon$-approximants do exist. The proof is based on a (modification of) the regularity lemma for words by Axenovich--Person--Puzynina. Joint work with Gabriel Nivasch.
15h30 Jean-François Marckert CNRS, LaBRI, Université Bordeaux 1
Around Sylvester question in the plane
Pick $n$ points uniformly at random in a compact convex body $K$ of the plane. What is the probability $P_{n,K}$ that these points are the vertices of a convex polygon ? (we say, in a convex position). We will discuss exact results existing for the triangle and square (Valtr, and Buchta), and for the disk, as well as asymptotics on $n$. Sylvester problem is the name given to the optimization problem, where the optimization is done on $K$ : for $n=4$ points, the maximum and the minimum are obtained for the disk and triangle (Bläschke). We will see that it is also true for $n=5$, and probably for any $n > 5$ as well.
11 mai 2017
14h Pierre Alliez Inria Sophia-Antipolis — Méditerranée
Inter-surface Mapping via Optimal Mass Transport
Recent advances based on entropic regularization are unleashing the power of optimal transport. In this talk I will present a novel approach for computing a homeomorphic map between two discrete surfaces. While most previous approaches compose maps over intermediate domains which result in suboptimal inter-surface mapping, we directly optimize a map by computing a mass transport plan between two surfaces. This non-linear problem, which amounts to minimizing the Dirichlet energy of both the map and its inverse, is solved using two alternating convex optimization problems in a coarse-to-fine fashion. Computational efficiency is further improved through the use of Sinkhorn iterations, modified to handle minimal regularization and unbalanced transport plans. The resulting inter-surface mapping algorithm applies to arbitrary shapes, with little to no user interaction.

Joint work with David Cohen-Steiner, Manish Mandad, Mathieu Desbrun and Leif Kobbelt.

15h30 Guilherme Dias da Fonseca Université Clermont Auvergne
Geometric Approximation Using a Hierarchy of Macbeath Regions
This talk is divided in two parts, presenting two papers written with Sunil Arya and David M. Mount (SODA 2017 and SoCG 2017). Both papers are based on a new hierarchy of Macbeath regions that approximates a convex body $K$ in $d$-dimensional space up to an error $\epsilon > 0$. For the purpose of the complexity analysis, we assume that $d$ is a constant, but that $\epsilon$ is an asymptotic variable approaching $0$. Out goal is to minimize dependencies on $\epsilon$, for example from $1/\epsilon^d$ to $1/\epsilon^{d/2}$.

In the first part of the talk, we present an optimal data structure to approximately answer if a query point $q$ is inside or outside of $K$. We attain logarithmic query time with storage of only $O(1/\epsilon^{(d-1)/2})$, which matches the worst-case lower bound on the complexity of any $\epsilon$-approximating polytope. Using known reductions, we obtain major improvements to approximate nearest neighbor searching.

In the second part, we show how the hierarchy can be used to construct an $\epsilon$-kernel in near-optimal time. Kernels provide an approximation to the convex hull, and therefore are on the basis of several geometric algorithms. We obtain major improvements to the complexity of other fundamental problems, such as approximate diameter, approximate bichromatic closest pair, and approximate Euclidean minimun bottleneck tree, as well as near-optimal preprocessing times to multiple data structures.

20 avr. 2017
salle 314 (exceptionnellement)
14h Lionel Pournin LIPN, Université Paris 13
From mesh generation to associahedra and related structures
The flip operation is used in computational geometry to generate meshes or modify them. Depending on the underlying point set, these meshes also give rise, via flips, to structures with deep connections to a number of other fields such as combinatorics, algebra, topology, theoretical physics, and biology. Some of these connections will be described in this talk. One of these connections is with the associahedron, a polytope that pops up in surprisingly different contexts. Another is related to the triangulations of topological surfaces. Several results and open problems will be mentioned along the way. Part of this talk is based on a joint work with Hugo Parlier.
15h30 Pierre-Guy Plamondon Université Paris-Sud
Combinatoire des triangulations de surfaces
L'objectif de cet exposé sera de présenter un survol de certaines propriétés combinatoires et algébriques des triangulations dites décorées (en un sens à définir) de surfaces orientables avec bord et points marqués. La notion de "flip" permettant de passer d'une triangulation à une autre est intimement liée à la notion de "mutation" dans la théorie des algèbres amassées. Après avoir passé en revue des propriétés combinatoires des triangulations, nous étudierons des applications aux algèbres amassées par ce lien.
23 mars 2017
14h Louis Esperet CNRS, G-SCOP, Grenoble
Box representations of embedded graphs
A box in $\RR^d$ is the cartesian product of $d$ intervals of $\RR$. For instance, a box in $\RR$ is an interval and a box in $\RR^2$ is an axis-parallel rectangle. Representing graphs as intersection graphs of low dimensional boxes (i.e. each vertex corresponds to a box of $\RR^d$ and two vertices are adjacent if and only if their boxes intersect) is an important problem with applications in the study of ecological and sociological networks. In this talk, I will give a gentle introduction to low dimensional box representations of graphs, and in particular explain an interesting connection with the notion of dimension of a partially ordered set. A classical result of Thomassen (1986) states that every planar graph can be represented as intersection graph of boxes in $\RR^3$. I will explain how this result can be extended to graphs embedded in any fixed surface: I will show that every graph of genus $g$ can be represented as the intersection graph of boxes in dimension $\sqrt{g}\log g$, while random graphs provide a lower bound of order $\sqrt{g\log g}$. I will also show that if a graph is embedded in a fixed surface and has no short non-contractible cycles, then it can be represented as the intersection graph of boxes in $\RR^5$.
15h30 Raphaëlle Chaine LIRIS, Université Claude Bernard Lyon 1
Quasi-uniform triangulations for virtual sculpture and super resolution of digitized surfaces
In this talk I will describe how triangulations can be used to track a surface being sculpted interactively with deformation fields. I will focus on the way to embed and to maintain some drawings on this surface or to transform it as an aggregate of small objects such as a sand pile or a swarm of birds. These approaches rely on maintaining a quasi uniform sampling of the surface, while ensuring some visual continuity. Then I will talk about an approach to up-sample a surface from an eneven point set obtained from laser scans. This involves the use of a new descriptor to detect self-similarities that naturally arise on surfaces and to enrich similar areas jointly, independently of the local shape.
23 févr. 2017
14h Sergio Rajsbaum Universidad Nacional Autonoma de Mexico, Mexique — professeur invité au LIX à l'École Polytechnique
Introduction to distributed computing analysis using combinatorial topology
The equivalence between single-tape and multi-tape Turing machines is often interpreted as implying that the use of one computing machine versus the use of several machines may differ in questions of efficiency, but not computability. It has been clear from early on that the addition of parallelism to Turing machines does not change the fundamental notion of Turing-computability. In the theory of distributed computing, we study computability in the presence of failures and timing uncertainties.

Task computability is very sensitive to the details of the model: failures (type and number of process and communication failures), communication (various forms of message passing and shared memory), and timing (relative process speeds and communication delays). However, the many possible distributed computing models can be understood through a common framework: There is an intimate relation between distributed computability and topology. Roughly speaking, the question whether a task is computable (and how fast) in a given model can be reduced to the question whether an associated geometric structure, called a simplicial complex has "holes" of certain dimensions. There are various implications of these insights. In particular, Turing computability is orthogonal to distributed computability. In distributed computing we allow for individual processes to have an infinite number of states, thus each one individually can solve the Halting problem, however, there are simple Turing-computable tasks that are not computable even in the presence of a single process crash. This talk presents an introduction to the fascinating topological perspective of distributed computing.

15h30 Jérémie Chalopin CNRS, LIF, Marseille
Cop and robber game and hyperbolicity
In this talk, we consider a variant of the cop and rober game where the cop and the robber move at different speed. The difference with the classical cop and robber game is that at each step, the cop can move along a path of length at most $s'$, and the robber can move along a path of length at most $s$ (without going through the position of the cop). A graph is $(s,s')$-copwin if the cop with speed $s'$ has a strategy to capture any robber moving at speed $s$.

$\delta$-hyperbolic graphs are graphs that are close to trees from a metric point of view; we will present a few (of the many) definitions of hyperbolicity.

We will present some results relating the cop and robber game and the hyperbolicity of a graph. We show that if a graph is $\delta$-hyperbolic, then it is $(2r,r+2\delta)$-copwin for any $r$. Conversely, we show that a $(s,s')$-copwin graph (with $s>s'$) is $O(s^2)$-hyperbolic. From our approach, we deduce an $O(n^2)$ algorithm to approximate the hyperbolicity of a graph when we are given its distance matrix.

19 janv. 2017
14h Brigitte Servatius Worcester Polytechnic Institute
On configuration spaces of linkages
A linkage consists of rigid bars connected by revolute joints and may be fully described by its configuration space. Farber, Hausmann and Schutz (2009) proved that the integral cohomology rings of planar polygon spaces determine their diffeomorphism types. Even for small linkages the configuration spaces have complicated structure, for example there are seven diffeomorphs of a quadrilateral. We will review the basic results about the rigidity of frameworks, the motion of simple linkages, and how they can affect one another.
15h30 Pierre Dehornoy Institut Fourier, Université Grenoble-Alpes
Intersection norms on the homology of surfaces
Intersection numbers of curves on surfaces are a topological and an algorithmic topic. In this talk we introduce for every finite collection of closed curves on a surface a norm on the first homology group of the surface that captures some properties of the intersection. These norms are 2-dimensional analogs of the Thurston norms that are famous among 3d-topologists. In particular their unit balls are also finite polyhedra. We give an explicit way to compute them. We also give an application that actually motivated these norms: we show how the integer points inside the unit balls classify certain topological/dynamical objects, namely the surfaces transverse to the geodesic flow in the unit tangent bundle to the surface.
8 déc. 2016
14h Luca Castelli Aleardi LIX, École Polytechnique
Mesures spectrales de distortion pour la visualisation de réseaux dynamiques
Dans cet exposé nous allons considérer le problème de la détection et visualization des modifications dans un graphe qui évolue dans le temps. Le problème de visualiser un graphe dynamique pose des défis supplémentaires par rapport au cas statique: en plus des contraintes esthétiques usuelles, on souhaite détecter les changements structurels du graphe de manière robuste et efficace. Notre contribution principale consiste à proposer une nouvelle notion de distortion (une fonction qui quantifie les changements dans le graphe) basée sur des méthodes spectrales et faisant intervenir l'optimization d'une fonction énérgie associée aux sommets du graphe. Notre approche est assez générale et flexible, permettant à l'utilisateur d'adapter de manière fine et multi-échelle le calcul de la distortion pour tenir compte de la nature des modifications dans le graphe. Pour conclure, nous allons montrer comment intégrer notre mesure de distortion dans un algorithme de visualisation de type "force-directed" capable de préserver la "mental map" du graphe.

Travail en collaboration avec Rania Ibrahim, Semih Salihoglu et Maks Ovsjanikov.

15h30 Xavier Goaoc Université Paris-Est Marne-la-Vallée
Topological Helly theorems
I will discuss how topological Helly-type theorems, which restrict the intersection patterns of families of sets of bounded topological complexity, relates to various classical topics: nerve theorems, non-embeddability of certain simplicial complexes, upper bound theorems, and sampling.
10 nov. 2016
14h David Coeurjolly CNRS et LIRIS, Université de Lyon
Geometry Procesing on Digital Surfaces
Digital Geometry can be simply characterised as a set of definitions, theorems and algorithmic tools that deal with the geometric properties of objects defined on regular lattices. Originating from shape processing in 2D and volumetric images, this specific constraint on the input data implies new axioms and results with strong connections between various fields such as computational geometry, discrete mathematics (arithmetic, theory of words) and image processing. In this presentation, I first introduce the specificities of the model and then present several geometry processing tools we have developed dedicated to digital surfaces.
15h30 Jean-Marie Mirebeau CNRS et Université Paris-Sud
Calcul de chemins minimaux avec pénalisation de courbure, via l'algorithme du Fast Marching
Motivés par des applications en planification de mouvement et en segmentation d'image, nous considérons des modèles de plus courts chemins avec pénalisation de courbure, tels que les élasticas d'Euler/Mumford, ou la voiture de Reed-Shepp avec ou sans marche arrière. Notre stratégie numérique, pour le calcul du chemin d'énérgie minimale joignant deux points donnés, est d'approcher ces modèles singuliers à l'aide de métriques Riemanniennes ou Finsleriennes fortement anisotropes sur l'espace produit $\RR^d\times\SS^{d-1}$. Les équations eikonales associées sont ensuites résolues via des variantes spécialisées de l'algorithme du Fast-Marching.
13 oct. 2016
14h Gabriel Peyré CNRS et DMA, École normale supérieure, Paris
From Monge-Kantorovich to Gromov-Wasserstein : Optimal Transport and Barycenters Between Several Metric Spaces
Optimal transport (OT) has become a fundamental mathematical theoretical tool at the interface between calculus of variations, partial differential equations and probability. It took however much more time for this notion to become mainstream in numerical applications. This situation is in large part due to the high computational cost of the underlying optimization problems. There is however a recent wave of activity on the use of OT-related methods in fields as diverse as computer vision, computer graphics, statistical inference, machine learning and image processing. In this talk, I will review an emerging class of numerical approaches for the approximate resolution of OT-based optimization problems. These methods make use of an entropic regularization of the functionals to be minimized, in order to unleash the power of optimization algorithms based on Bregman-divergences geometry. This results in fast, simple and highly parallelizable algorithms, in sharp contrast with traditional solvers based on the geometry of linear programming. For instance, they allow for the first time to compute barycenters (according to OT distances) of probability distributions discretized on computational 2-D and 3-D grids with millions of points. This offers a new perspective for the application of OT in machine learning (to perform clustering or classification of bag-of-features data representations) and imaging sciences (to perform color transfer or shape and texture morphing). These algorithms also enable the computation of gradient flows for the OT metric, and can thus for instance be applied to simulate crowd motions with congestion constraints. This is a joint work with M. Cuturi and J. Solomon.
15h30 Frédéric Chazal INRIA Saclay—Île-de-France
Subsampling methods for persistent homology
Computational topology has recently seen an important development toward data analysis, giving birth to Topological Data Analysis. Persistent homology appears as a fundamental tool in this field. It is usually computed from filtrations built on top of data sets sampled from some unknown (metric) space, providing "topological signatures" revealing the structure of the underlying space. When the size of the sample is large, direct computation of persistent homology often suffers two issues. First, it becomes prohibitive due to the combinatorial size of the considered filtrations and, second, it appears to be very sensitive to noise and outliers. In this talk we will present a method to overcome these issues by computing persistent diagrams from several subsamples and combining them in order to efficiently infer robust and relevant topological information from data.
9 juin 2016
14h Maks Ovsjanikov École Polytechnique et CNRS
Functional Characterization of Shapes and their Relations
In recent years, several works have proposed to look at basic constructs in geometry processing from a "functional" point of view, by representing them as linear operators acting on real-valued functions defined on the shapes. In this talk I will describe what these representations entail for mappings or correspondences, tangent vector fields and shape distortions. Finally, I will describe how surfaces themselves can be represented and manipulated in a coordinate-free fashion via a functional characterization of the first and second fundamental forms.
15h30 Julie Digne CNRS, LIRIS, Lyon
Shape modeling based on similarity analysis
Most object surfaces exhibit strong local similarity defined as repetitions and variations of geometric patterns. These local properties can be inherited from the material the objects are made of or the tools used to shape them. In this talk we will describe how these local variations can be discovered and described. Using well chosen descriptors, we are able to extract and describe these data similarities. Exploiting the repetitions then allows us to revisit various surface processing tasks such as denoising, compression and shape resampling.
We will demonstrate the validity of our approach on several shapes such a digitized statues and mechanical objects but also on urban scenes.
19 mai 2016
14h Bojan Mohar Simon Fraser University, Canada and IMFM, Ljubljana, Slovenia
On terminal wye-delta reducibility
A wye-delta operation in a graph replaces a vertex v of degree 3 by a triangle through the neighbors of v. It is well-known that every planar graph can be reduced to the empty graph by using wye-delta and series-parallel operations. In an attempt to understand the wye-delta reducibility for non-planar graphs, the notion of reducibility with terminals is introduced. It turns out that this notion is tightly related to a question about a rooted minor isomorphic to K(2,4). A beautiful structural characterization of planar graphs without such minors will be outlined and discussed.
15h30 Francisco Santos University of Cantabria, Espagne
Diameters of polyhedra and simplicial complexes
The Hirsch conjecture, posed in 1957, stated that the graph of a d-dimensional polytope or polyhedron with n facets cannot have diameter greater than n−d . The conjecture itself has been disproved by Klee-Walkup (1967) for unbounded polyhedra and by Santos (2010) for bounded polytopes, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the Hirsch bound by more than 25% is known.

In this talk we review the motivation for the Hirsch Conjecture, related to the complexity of the simplex method, we describe our constructions of counter-examples to it, and report on other attempts and progress on the question, mostly those that try to answer the diameter question by generalizing it to the world of simplicial complexes. This approach has a long history, starting by Adler and Dantzig’s definition of “abstract polytopes” which are nothing but “normal pseudo-manifolds”, but it is still (or again) an active area of research.

14 avr. 2016
14h Laurent Hauswirth Université de Marne-la-Vallée
Variational aspect of minimal surfaces in discrete and smooth geometry
The main goal of this talk is to describe an overview of recent progress in minimal surface theory. In particular we will try to evoke the proof of Coda-Marques and Neves of Willmore conjecture and related problems in discrete geometry.
15h30 János Pach EPFL Lausanne, Suisse et Renyi Institute, Budapest, Hongrie
Vapnik-Chervonenkis dimension revisited
During the past thirty years, hypergraphs of bounded Vapnik-Chervonenkis dimension (in short, VC-dimension) have played an important role in learnability theory and in computational geometry. After reviewing the basic definitions and results, I will report on some recent developments in the field. In particular, I will discuss the following result of Fox, Suk, and myself. For any $d$, every graph with $n$ vertices and VC-dimension at most $d$ contains a complete subgraph or an independent set of size at least $n^{(\log n)^{1-o(1)}}$. In contrast, Ramsey's theorem guarantees the existence of only constant times $\log n$ vertices that induce a complete or empty subgraph.
17 mars 2016
14h Mark de Berg TU Eindhoven, Pays-Bas
Fine-grained complexity analysis of two classic TSP variants
We present new results on two classic TSP variants. Our first set of results concerns BITONIC TSP: given a set of $n$ points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamic-programming exercise to solve this problem in $O(n^2)$ time. While the near-quadratic dependency of similar dynamic programs for LONGEST COMMON SUBSEQUENCE and DISCRETE FRECHET DISTANCE has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves BITONIC TSP in $O(n\log^2 n)$ time and its bottleneck version in $O(n\log^3 n)$ time. Our second set of results concerns the popular $k$-OPT heuristic for TSP in the graph setting. More precisely, we study the $k$-OPT decision problem, which asks whether a given tour can be improved by a $k$-OPT move that replaces $k$ edges in the tour by $k$ new edges, for some given constant $k$. A simple algorithm solves $k$-OPT in $O(n^k)$ time. For 2-OPT, this is easily seen to be optimal. For 3-OPT we prove that an algorithm with a runtime of the form $O^*(n^{3-\epsilon})$ exists if and only if ALL-PAIRS SHORTEST PATHS in weighted digraphs has such an algorithm. For general $k$-OPT, it is known that a runtime of $f(k) \cdot n^{o(k/\log k)}$ would contradict the Exponential Time Hypothesis. The results for $k=2,3$ may suggest that the actual time complexity of $k$-OPT is $\Theta(n^k)$. We show that this is not the case, by presenting an algorithm that finds the best $k$-move in $O(n^{\lfloor{2k/3}\rfloor + 1})$ time. Finally, we show how to beat the quadratic barrier for 2-OPT in two important settings, namely for points in the plane and when we want to solve 2-OPT repeatedly.

This is joint work with Kevin Buchin, Bart Jansen, and Gerhard Woeginger.

15h30 Otfried Cheong KAIST, Daejon, Corée du Sud
Shortcuts for the Circle
Let $C$ be the unit circle in $\RR^2$. We can view $C$ as a plane graph whose vertices are all the points on $C$, and the distance between any two points on $C$ is the length of the smaller arc between them. We consider a graph augmentation problem on $C$, where we want to place $k\geq 1$ shortcuts on $C$ such that the diameter of the resulting graph is minimized. We analyze for each $k$ with $1\leq k\leq 7$ what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of $k$. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is $2 + \Theta(1/k^{\frac{2}{3}})$ for any $k$.

This is joint work with Sang Won Bae, Mark de Berg, Joachim Gudmundsson and Christos Levcopoulos.

11 févr. 2016
14h Niloy Mitra University College London, Royaume-Uni
Computational Design of Functional Objects
Both professionals and hobbyists like to design functional objects for physical use. However, there exists limited computational support to facilitate such a design process. Existing tools either require specialized skills and extensive training, or necessitate users to perform extensive trial and error based exploration with limited guidance. In this talk, I will discuss some of our recent attempts to change current workflows focusing on functional prototyping, guided designing, and material-aware modeling. More details can be found here.
15h30 Francis Lazarus CNRS, Gipsa-Lab, Grenoble
Autour du nombre géométrique d'intersection d'une courbe
Comment reconnaître si une courbe tracée sur une surface peut être déformée continûment en une courbe simple, c'est-à-dire sans croisement ? Cette question, étudiée par Henri Poincaré dans son cinquième complément à l'Analysis Situs, soulève un autre problème : comment décider si deux courbes peuvent être déformées continûment l'une en l'autre. Nous verrons que des techniques élémentaires empruntées à la théorie géométrique des groupes permettent de répondre efficacement à ces problèmes.
14 janv. 2016
14h Hervé Fournier IMJ, Université Paris Diderot
Bornes inférieures en complexité algébrique via les dérivées partielles
Le problème VP vs VNP introduit par Leslie Valiant à la fin des années 70 est un analogue algébrique de la question booléenne P vs NP. Ce modèle a pour objet la complexité du calcul de polynômes. Déterminer si VP=VNP est la question centrale de la complexité algébrique; une borne inférieure superpolynomiale sur la taille des circuits arithmétiques calculant le permanent permettrait de séparer VP de VNP. A ce jour, seules des bornes inférieures à peine mieux que linéaires sont connues pour des circuits généraux. Cependant, des bornes inférieures superpolynomiales ont été obtenues pour des classes restreintes de circuits. Nous présenterons la technique des dérivées partielles initiée par Nisan et Wigderson, puis étendue par Raz, et Kayal, permettant d'obtenir de tels résultats.
15h30 Salman Parsa Département d'informatique, École normale supérieure, Paris
From Reeb Graphs to the Efficiency of Homology Computation
This talk is a journey through computational topology. I start by defining the notion of the Reeb graph. This is a 1-dimensional space constructed from a real-valued function on a topological space. This graph substitute of a space has found some applications. For our purposes, the spaces are always 2-dimensional simplicial complexes and the functions simplex-wise linear. In this setting, there exist algorithms for efficiently computing the Reeb graph. The Reeb graph is a graph and hence its homology and Betti numbers can easily be computed. On the other hand, loops of the Reeb graph are images of non-trivial cycles in the original space. The subgroup of the first homology group generated by these loops is called vertical homology group with respect to the function and its rank we call the vertical Betti number. Therefore, this part of homology group is always efficiently computable, i.e. in linear time. This makes a connection between Reeb graphs and homology computation. I then show that the horizontal Betti numbers cannot be computed faster than rank computation, which is the standard way of computing Betti numbers. This is done by reducing rank computation for 0-1 matrices to computing horizontal $Z_2$-Betti numbers of simplicial complexes that are moreover embedded in $R^4$. If time allows I will discuss generalizations of this reduction. In the general version, first homology group is replaced by the fundamental group. Then the problem is the following. Given a presentation of a group, construct a model complex in $R^4$ in linear time in the bit-complexity of the input presentation. I also discuss classical results directly related to this problem.
10 déc. 2015
14h Victor Chepoi Aix-Marseille Université
Local-to-global results in metric graph theory
The main subject of metric graph theory is the investigation and structural characterization of graph classes whose metric satisfies the main metric and convexity properties of classical metric geometries. The main classes of graphs occurring in metric graph theory are median graphs, Helly graphs, bridged graphs, hyperbolic graphs, weakly modular graphs, and isometric subgraphs of hypercubes. Other classes of graphs in MGT occur from combinatorics and geometry (basis graphs of matroids and dual polar graphs) and have been characterized using metric conditions.
Many of these classes of graphs give rise to important cubical and simplicial complexes. Median graphs are exactly the 1--skeletons of CAT(0) cubical complexes; CAT(0) cubical complexes were characterized by M. Gromov in a local-to-global combinatorial way as the simply connected cubical complexes in which the links of vertices are simplicial flag complexes. Analogously to median graphs, bridged graphs are exactly the 1--skeletons of simply connected simplicial flag complexes in which the links of vertices do not contain induced 4-- and 5--cycles. Those simplicial complexes were rediscovered by T. Januszkiewicz and J. Swiatkowski and dubbed systolic complexes. Systolic complexes satisfy many global properties of CAT(0) spaces (contractibility, fixed point property) and were suggested as a variant of simplicial complexes of combinatorial nonpositive curvature. More recently, similar local-to-global characterizations have been obtained for basis graphs of matroids, Helly graphs, weakly modular graphs and their subclasses.
In the talk, we will overview some of those results and describe two methods for proving them: minimal disk diagrams and universal covers. The talk is based on the following papers:
J. Chalopin, V. Chepoi, H. Hirai, and D. Osajda, Weakly modular graphs and nonpositive curvature (submitted).
J. Chalopin, V. Chepoi, and D. Osajda, On two conjectures of Maurer concerning basis graphs of matroids, J. Comb. Theory, Ser. B 114 (2015), 1-32.
V. Chepoi, Graphs of some CAT(0) complexes, Adv. Appl. Math. 24 (2000), 125-179.
15h30 Quentin Mérigot CNRS, Université Paris-Dauphine
A Newton's algorithm for semi-discrete optimal transport
Many problems in geometric optics or convex geometry can be recast as optimal transport problems: this includes the far-field reflector problem, Alexandrov’s curvature prescription problem, etc. A popular way to solve these problems numerically is to assume that the source probability measure is absolutely continuous while the target measure is finitely supported. We refer to this setting as semi-discrete optimal transport. Among the several algorithms proposed to solve semi-discrete optimal transport problems, one currently needs to choose between algorithms that are slow but come with a convergence speed analysis (and rely on coordinate-wise increments) or algorithms that are much faster in practice but which come with no convergence guarantees (Newton/quasi-Newton). In this talk we will present a simple damped Newton’s algorithm with global linear convergence and which is also very efficient in practice, when the cost function satisfies the so-called Ma-Trudinger-Wang regularity condition.
Joint work with Jun Kitagawa and Boris Thibert.
12 nov. 2015
14h Pooran Memari CNRS et Télécom ParisTech
Triangulations régulières et leurs propriétés magiques
Dans cet exposé, on s’intéresse aux propriétés des triangulations régulières qui peuvent être définies comme une généralisation des triangulations de Delaunay. Une triangulation d'un ensemble de points P dans R^n est dite régulière si elle peut être obtenue par la projection orthogonale de l’enveloppe inférieure du graphe d’une fonction réelle définie sur P. Ce type de triangulation est devenu un outil classique en géométrie algébrique et intervient naturellement dans l’étude des résultants des polynômes à plusieurs variables. Notamment, certaines de leurs propriétés sont encodées dans un polytope résultant, appelé le polytope secondaire. Comme nous allons voir, ces propriétés peuvent être présentées de façon très intuitive et purement géométrique. Ainsi, sans rentrer dans les détails techniques qui permettent de les prouver, elles peuvent nous paraître magiques !
On présentera aussi quelques cadres modernes d'applications de ces triangulations en traitement géométrique de maillages.
15h30 Jean Cardinal Université Libre de Bruxelles
The existential Theory of the Reals in Computational Geometry
Deciding the validity of sentences in the existential theory of the reals (ETR) amounts to checking the existence of a real solution to a system of polynomial equalities and inequalities. In the late eighties, Mnëv stated a theorem that led to a proof that the stretchability problem for pseudoline arrangements was ETR-complete. Since then, many more natural problems in computational geometry have been proven ETR-complete, in particular in the field of graph drawing and geometric graphs. We will describe the foundation of those proofs, some well-known results in this vein, and recent additions to the list. Parts of this talk involve joint work with Udo Hoffmann (TU Berlin) and Vincent Kusters (ETH Zurich).
15 oct. 2015
14h Jesus De Loera University of California at Davis
Quantitative Combinatorial Convexity
Carathéodory's, Helly's, and Tverberg's theorems are among the most important theorems in convex geometry. Many generalizations and extensions, including colorful, fractional, and topological versions, have been developed and are a bounty for geometers. More than 300 papers have been written on these subjects. My talk will introduced a new way to interpret these theorem by introducing quantitative versions of these three theorems where now the hypothesis and/or conclusion of our theorems include measurable or enumerable information. We present several examples of both continuous quantitative results, where we measure or quantify the size of our sets with a parameter, such as the volume or the diameter, which can vary continuously, and of discrete quantitative results, where we measure the size of our sets with an enumerative value, such as by counting the number of lattice points they contain. At the end a rather complete theory of quantitative convex geometry emerges, one where all three theorems are interconnected. E.g., Carathéodory-type theorems are used to prove our Helly-type results, and they in turn are used to prove our Tverberg-type statements. Joint work with R. La Haye, D. Rolnick, and P. Soberon.
15h30 Andreas Holmsen KAIST, Corée du Sud
A discrete geometric version of Hall's theorem
I will present a recent discrete geometric version of Hall's marriage theorem based on joint work with Luis Montejano and Leonardo Martinez. Given $n$ finite sets in the $d$-dimensional space, we give combinatorial conditions under which it is possible to choose $n$ points, one point from each set, in such a way that the selected points are in general position. When the dimension is 1 we recover Hall's theorem. The combinatorial conditions relate a certain domination parameter in hypergraphs to the homological connectedness of independence complexes.
10 sept. 2015
Séance spéciale « Quelques travaux de Jiří Matoušek (1963-2015) »
14h Uli Wagner IST, Vienne, Autriche
Matoušek’s work on the polynomial method
In this talk, we will survey Jiří Matoušek’s work on the polynomial method, in particular on the Guth-Katz polynomial partition method, and its applications in discrete geometry.
Based on the papers “Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique” (by Kaplan, Matoušek, and Sharir) and “Multilevel Polynomial Partitions and Simplified Range Searching” (by Matoušek and Patáková).
14h30 Nabil Mustafa LIGM, U. Paris Est, ESIEE
Some compact geometric structures
Starting in the mid 1980s, the use of random sampling for proving the existence of geometric structures resulted in the resolution of a number of problems in discrete and computational geometry, both combinatorial and computational. Jiří Matoušek played a decisive role in this development. In this talk I will survey this work, including epsilon-nets, discrepancy, cuttings and the simplicial partition theorem.
15h30 Frédéric Meunier CERMICS, École Nationale des Ponts et Chaussées
A combinatorial proof of Kneser's conjecture
Kneser’s conjecture, a challenging conjecture in graph theory, was proved in 1978 by Lovász using algebraic topology. In 2003, Jiří Matoušek proposed a short combinatorial proof of this conjecture. In this talk, I will explain this proof, and outline other results that were later obtained using this proof technique, which turns out to be particularly powerful.
16h Xavier Goaoc Université Paris-Est Marne-la-Vallée, IUF
(Fractional) Helly-type theorems
I will discuss the fractional Helly theorem for convex sets and a similar result for set systems with polynomial dual shatter function. This is based on the paper "Bounded VC-dimension implies a fractional Helly theorem"
18 juin 2015
salle 314 Séminaire quadruple!
10h Mickaël Buchet Ohio State University
Handling noise and complexity blow-up in topological data analysis
Topological data analysis from a point set usually works in two steps. First one goes from the discrete data sets to a continuous construction, such as simplicial complex, then uses this structure to infer topological information. Unfortunately, the usual structure suffers an exponential blow-up in complexity as the dimension increases, the so-called curse of the dimensionality. Moreover, most of the algorithms used in topological data analysis are not robust with respect to unbounded noise like the presence of aberrant values in the data. In this talk, I will describe the framework used by topological data analysis algorithm as well as some of the most classical structure. Then I will present some methods to reduce the complexity of the structure and how to handle aberrant noise in order to provide tractable algorithms for the analysis of intrinsically low dimensional data embedded in high dimensional spaces.
11h15 Clément Maria University of Queensland, Brisbane, Australie
Quantum invariants of knots and 3-manifolds
In this talk, I will present the Reshetikhin-Turaev quantum invariant of knots and 3-manifolds. This construction widely generalizes the Jones polynomial and opens exciting research questions in computational topology. In a nutshell, it consists of turning a knot (or more generally a link) into an algebraic equation by colouring knot components with algebraic objects and turning knot features into algebraic operators. A set of objects and operators leading to equations that are invariant under knot isotopy forms a ribbon category, and leads to knot and link invariants. Finally, presenting a 3-manifold by a link surgery, one can deduce 3-manifold invariants from the link invariants produced by ribbon categories. I will present some aspects of the construction of the Reshetikhin-Turaev invariant, together with mathematical insights about the proofs of invariance. I will also enumerate some recent algorithmic results for the computation of these invariants.
14h Gilles Bertrand ESIEE Paris, LIGM, Université Paris-Est
Une approche axiomatique pour la topologie combinatoire
[pas de transparents]
Nous proposons un ensemble "d'axiomes" pour décrire certaines collections de complexes simpliciaux. Ces axiomes sont exprimés par le biais de complétions, une complétion est une propriété inductive qui peut être exprimée de façon déclarative. Nous présentons ainsi la collection des dendrites qui sont des complexes acycliques au sens de l'homologie, la collection des dyads qui sont des paires de complexes liés par une topologie relative. Nous introduisons également la collection des paires d'homotopie définie à partir de l'opération de "collapse" de Whitehead. Nous proposons plusieurs résultats qui établissent un lien entre toutes ces collections. Ces résultats montrent qu'il est possible d'exprimer et de manipuler dans un même cadre unifié des notions liées à l'homologie et des notions liées à l'homotopie.
15h30 Valérie Berthé CNRS, LIAFA, Université Paris Diderot
Hyperplans discrets : une approche arithmétique et dynamique
Nous revisitons ici l'étude des hyperplans discrets considérés classiquement en géométrie digitale selon le double point de vue des systèmes dynamiques et des ensembles de Delone quasicristallins. Nous considérons en particulier la notion de récurrence (répétitivité) ainsi que les fréquences des motifs, et montrons comment les propriétés arithmétiques des paramètres de l'hyperplan interviennent.
21 mai 2015
salle 314
14h Bertrand Michel LSTA, Université Pierre et Marie Curie, Paris
Statistique et topologie pour l'analyse des données
L'analyse topologique des données désigne un ensemble de méthodes et d'algorithmes dont l'objectif est l'estimation des propriétés topologiques d'une forme géométrique. L'objectif de cet exposé est de présenter une approche statistique de l'analyse topologique des données. Dans la première partie de l'exposé, je proposerai une introduction à la persistance homologique. Je rappellerai quelques notions clé en inférence statistique et je donnerai quelques résultats statistiques pour l'analyse topologique des données. Dans une seconde partie de l'exposé, je présenterai une version plus robuste de la persistance homologique. Chazal, Cohen-Steiner et Mérigot (2011) ont en effet proposé une extension des fonctions distance aux compacts en remplaçant les sous-ensembles compacts par des mesures. Cette nouvelle fonction distance est beaucoup plus robuste et permet d'aborder l'analyse topologique des données avec un point de vue plus probabiliste. Je présenterai quelques résultats statistiques récents sur l'estimation de cette distance à la mesure.
15h30 Nicolas Broutin Inria Rocquencourt
Connectivity properties of sparsified random geometric graphs
Consider a graph whose vertices represent $n$ uniform points in the unit square. One forms a geometric graph by connecting two vertices is the distance between the corresponding points is at most some visibility radius $r$. It is well-known that for such graph to be connected with a decent probability, the average degree must be at least of order $\log n$, which may be two much for many applications. We will see and analyse one natural way to obtain a much sparser version of such graphs that is based on a decentralized protocol. Of course, one is interested in tuning the parameters (the average degree) so that the graph is then mostly connected. Quite interestingly, the phase transition for the apparition of a connected component of linear size is "explosive" in the sense that the graph goes from almost completely shattered to almost completely connected with the addition of only $o(n)$ edges.
I will be using this result mostly as a pretext to give an introduction to connectivity in geometric random graphs and to review some of the beautiful main ideas there. This is based on joint work with L. Devroye and G. Lugosi.
16 avril 2015
salle 201
14h Frédéric Meunier CERMICS, École Nationale des Ponts et Chaussées
Conjecture d'Hedetniemi pour les hypergraphes de Kneser
[pas de transparents]
La conjecture d'Hedetniemi est une conjecture centrale en théorie des graphes. Elle affirme que le nombre chromatique du produit catégorique de deux graphes est égal au minimum de leurs nombres chromatiques. En 1992, Zhu étendit la conjecture d'Hedetniemi aux hypergraphes en conjecturant que de même le nombre chromatique du produit catégorique de deux hypergraphes est égal au minimum de leurs nombres chromatiques.
Les hypergraphes de Kneser sont des hypergraphes uniformes dont les sommets sont des parties d'un ensemble fini et dont les arêtes sont formées de parties deux à deux disjointes. Ce sont des hypergraphes possédant de nombreuses propriétés remarquables. Nous prouvons la conjecture de Zhu pour les hypergraphes de Kneser de même rang, ce qui à notre connaissance constitue la première famille explicite et non triviale d'hypergraphes n'étant pas des graphes pour laquelle la conjecture est prouvée. Cette approche permet également d'exhiber de nouvelles familles de graphes vérifiant le conjecture d'Hedetniemi.
La preuve s'appuie sur une généralisation combinatoire du théorème de Borsuk-Ulam.
Travail effectué en commun avec Hossein Hajiabolhassan.
15h30 Arnaud de Mesmay IST, Vienne, Autriche
Discrete systolic inequalities and decompositions of triangulated surfaces
How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart).
Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki from 1993, a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov's systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions.
Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length $O(g^{3/2}n^{1/2})$ for any triangulated combinatorial surface of genus $g$ with n triangles, and describe an $O(gn)$-time algorithm to compute such a decomposition.
Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations.
This is joint work with Éric Colin de Verdière and Alfredo Hubard.
19 févr. 2015
salle 201
14h Alfredo Hubard INRIA et Université Paris-Est Marne-la-Vallée
Limits of order types
[pas de transparents]
The concept of "limit" of a dense combinatorial structure appeared in the last decade in an effort to unify extremal combinatorics with analysis, probability and algebra. We transport this concept to the realm of geometry. There are a number of problems about points in general position that can be stated in combinatorial terms as problems about "order types". We consider limits of these objects and regard two types of questions about them. On one hand we give new quantitative bounds on classical problems like Sylvester's problem: what is the probability that $k$ points are in convex position. On the other, we draw connections between limits of order types and measures. This is joint work with X. Goaoc, R. de Joannis de Verclos, J.S.Séréni, and J.Volec.
15h30 Guillaume Moroz INRIA Nancy-Grand Est
Parametric polynomial systems and rigid graphs
A rigid graph is a graph with distance constraints associated to its edges and finitely many euclidean embeddings satisfying these constraints. The embeddings of a rigid graph in the plan can be naturally modeled by a polynomial system where some or all the lengths are considered as parameters. We will see how computer algebra techniques can be used to solve problems involving rigid graphs in mechanical design and computational geometry.
15 janv. 2015
salle 314
14h Imre Bárány Alfréd Rényi Mathematical Institute of the Hungarian Academy of Sciences, Hongrie
On a geometric Ramsey number
[pas de transparents]
A partial result: if a planar curve intersects every line in at most 3 points, then it can be partitioned into 4 convex curves. This result can be extended to $\RR^d$, and the extension implies a good, asymptotically precise, lower bound on a geometric Ramsey number. Joint result with Jirí Matoušek and Attila Por.
15h30 Claire Mathieu CNRS, Département d'informatique, École normale supérieure, Paris
Approximation schemes for optimization in planar graphs and in the Euclidian plane
Many optimization problems are hard to approximate in general graphs but have an approximation scheme if the input graph is planar. As an illustration, I will present the Steiner tree problem and approximation schemes in planar graphs on the one hand, for instances in the Euclidian plane on the other hand, and draw parallels between the two sets of techniques.
18 déc. 2014
salle 201
14h Arnau Padrol Freie Universität Berlin, Allemagne
Realizations of neighborly, inscribable and egg-scribable polytopes
Delaunay triangulations in $\RR^d$ are a central object in many areas of mathematics and computational geometry. However, little is known about which combinatorial types can appear as a Delaunay triangulation. With an inverse stereographic projection, this question translates to asking which combinatorial types of polytopes admit realizations with all the vertices on a $d$-sphere. We will construct a large family of neighborly polytopes that are not only inscribable on the sphere, but also in every smooth strictly convex body. This provides the current best lower bound for the number of combinatorial types of Delaunay triangulations. In the second part of the talk, we will use these techniques to show that realization spaces of inscribed polytopes present Universality in the sense of Mnëv. For example, this will allow us to construct a pair of point configurations whose Delaunay triangulations are combinatorially equivalent but yet there is no continuous transformation that maps one to the other without changing the combinatorics of the Delaunay triangulation.

This talk reports joint work with Karim Adiprasito, Bernd Gonska and Louis Theran.

15h30 Pascal Romon Université Paris-Est Marne-la-Vallée
Courbure de Ricci sur les graphes et les triangulations, d'après Ollivier
[pas de transparents]
La définition d'invariants géométriques discrets tels la courbure est un problème ardu. En 2009, Ollivier a proposé une définition adaptée à un grand nombre de contextes (espace métriques mesurés) incluant notamment les graphes et les surfaces polyédriques, et qui coïncide avec la courbure de Ricci dans le cas riemannien. Lin, Lu et Yau, puis Bauer, Jost et Liu ont étendu et appliqué cette idée aux graphes, et donné des estimées de courbure, et par conséquent de diamètre, en fonction de la combinatoire (théorème de Myers). J'expliquerai l'idée d'Ollivier (comment utiliser le transport optimal pour définir une courbure), puis comment on l'estime ou la calcule pour certains graphes et surfaces polyédriques, ainsi que les questions que cela pose.

Travail en collaboration avec Benoît Loisel.

27 nov. 2014
Jussieu, salle 15-16-101
(barre 15-16, 1er étage, salle 101)
14h Tamal K. Dey Ohio State University, États-Unis
Spectral Concentration and a Simple Clustering
A popular graph clustering method is to consider the embedding of an input graph into $\RR^k$ induced by the first $k$ eigenvectors of its Laplacian, and to partition the graph via geometric manipulations on the resulting metric space. Despite the practical success of this methodology, there is limited understanding of several heuristics that follow this framework. We provide theoretical justification for a natural such heuristic some form of which has been previously proposed in the machine learning literature.
Our result can be summarized as follows. We say that a partition of a graph is strong if each cluster has small external conductance, but large internal conductance. A recent result on graph partitioning shows that strong partitions exist for graphs with sufficiently large spectral gap. We prove that the eigenvectors cluster around their mean on each such strong partition. Combining our result with a simple greedy algorithm for $k$-centers gives us the desired spectral partitioning algorithm. We show that for bounded-degree graphs with a sufficiently large gap between the $k$-th and $(k+1)$-th eigenvalue of its Laplacian, this algorithm computes a partition that is close to a strong one. We also show how this greedy algorithm for $k$-center can be implemented in time $O(n k^2 \log n)$ using randomization. Finally, we evaluate our algorithm on some real-world, and synthetic inputs.
15h30 Elisha Falbel Institut de Mathématiques de Jussieu
Structures géométriques triangulées
On expliquera comment extraire des informations géométriques d'un espace à partir d'une triangulation et d'une "décoration" de cette triangulation. La géométrie sera encodée par un système d'équations et nous commenterons sa résolution par des méthodes de calcul formel ou numériques. On obtiendra, in fine, des représentations des groupes fondamentaux des variétés de dimension 3 dans $GL(3,C)$.
23 oct. 2014
salle 201
14h Nicolas Bonichon Université Bordeaux 1
Graphes couvrants géométriques : L'art de choisir les bons liens
L'étirement d'un graphe géométrique est le pire rapport entre la distance dans le graphe et la distance euclidienne, pour toute paire de points du graphe. Un $t$-spanner est un graphe (ou une famille de graphes) dont l'étirement est borné par $t$. Dans cet exposé je présenterai quelques résultats relatifs à certains spanners : triangulations de Delaunay, $\Theta$-graphs, spanners de degré borné,...
15h30 Nabil Mustafa LIGM, U. Paris Est, ESIEE
The Local-Search Technique for Geometric Algorithms
Local-search is an intuitive approach towards solving combinatorial optimization problems: start with any feasible solution, and try to improve it by local changes. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a locally optimal solution. In this talk I will survey the ideas and techniques behind the use of local-search in the design of provably good approximation algorithms for several geometric combinatorial optimization problems such as minimum set-cover, maximum independent-set, and minimum dominating set problem for graphs derived from geometric configurations.
25 sept. 2014
salle 421
14h Uli Wagner IST, Vienne, Autriche
Higher-Dimensional Analogues of Graph Planarity — Combinatorial and Computational Aspects of Embeddings
Graph planarity and, more generally, embeddings of graphs on surfaces, are a classical topic with connections to many areas, including combinatorics, computational geometry, and topology.
The higher-dimensional generalization, embeddings of finite simplicial complexes (compact polyhedra) into Euclidean space and other ambient manifolds, are also a well-studied in geometric topology. However, a systematic investigation of combinatorial and computational aspects of higher-dimensional embeddings has started only recently. Two typical questions are the following:
  1. Is there an algorithm that, given as input a finite $k$-dimensional simplical complex $K$, decides whether $K$ embeds in $d$-dimensional space?
  2. What is the maximum number of $k$-dimensional simplices of a simplicial complex that embeds into $d$-dimensional space?
We will discuss some recent developments and results regarding these and related questions as well as a number of open problems.
The talk will be of a survey-like nature and touch upon joint work with a number of colleagues: M. Cadek, X. Goaoc, M. Krcal, I. Mabillard, J. Matousek, P. Patak, Z. Safernova, F. Sergeraert, E. Sedgwick, M. Tancer, and L. Vokrinek.
15h30 Sergio Cabello Université de Ljubljana, Slovénie
Shortest Paths in Intersection Graphs of Unit Disks
Let $P$ be a set of points in the plane. Consider the graph $G$ with vertex set $P$ and an edge connecting two points whenever their distance is at most one. Such graph, usually called a unit disk graph, naturally appears when modelling communication between sensors. We will discuss the problem of computing in $G$ a shortest path tree from a given source in near-linear time, both when considering unweighted edges or edges weighted by their Euclidean length. As an application of this result, we will discuss how to solve the following isolation problem: given a set of unit disks in the plane and two points $s$ and $t$, find the minimum number of disks one needs to retain so that any path connecting $s$ to $t$ intersects some of the retained disks.
The presentation is based on joint works with Miha Jejčič and Panos Giannopoulos.