22 février 2024

salle Maurice Fréchet (ex salle 05)

14h00 Kate VOKES University of Luxembourg

Geometry of graphs of multicurves

In recent years, a major technique in studying hyperbolic surfaces is to look at certain graphs associated to the surface which are defined from the combinatorics of curves on the surface. The graphs we study are typically locally infinite, and can sometimes serve as a discrete model for a continuous space, such as the Teichmuller space of the surface. Often we are interested in the large-scale geometry of these graphs: roughly speaking, we care about what the graph looks like when we view it from far away. An example of a large-scale geometric property is Gromov hyperbolicity. We will give an introduction to graphs of multicurves and present a result classifying large-scale geometric properties of a family of these graphs in terms of a simple criterion.

15h30 Alexandros Eskenazis CNRS-Sorbonne Université-Trinity College

Dimensionality of Hamming metrics and Rademacher type

I shall present a lower bound on the bi-Lipschitz distortion required to embed the Hamming cube into a low-dimensional normed space. This unifies and extends (almost) all known results on the impossibility of dimensionality reduction for the hypercube metric. The proof relies on a combination of semigroup techniques on the biased cube with the Borsuk-Ulam theorem from algebraic topology.

14 decembre 2023

salle Olga Ladyjenskaïa (ex salle 01)

14h30 Faustin Adiceam LAMA-UPEC

Sur le problème de Danzer et de la construction des forêts denses

Un ensemble de points (de densité finie) est une forêt dense s’il est uniformément proche de tout segment de droite de longueur suffisamment grande. Le degré de densité d’une forêt dense est quantifié par une fonction dite de visibilité. Ce concept récemment introduit intervient en relation avec le problème de Danzer en géométrie convexe (1965), lequel demande de prouver l’existence d’un ensemble de points de densité finie intersectant tout corps convexe de volume unité. Après avoir détaillé la correspondance qui unit ces deux problèmes, l’exposé détaillera quelques-uns des liens qu'ils entretiennent avec la géométrie algorithmique et combinatoire.

16h00 Viviane Pons Paris-Saclay University

Le s-Ordre faible et s-Permutaèdre

Le permutaèdre et le treillis associé de l'ordre faible sur les permutations sont des objets classiques de la combinatoire et géométrie discète. En particulier, les liens géométriques et combinatoires avec l'associaèdre et le treillis de Tamari font l'objet de nombreux travaux. Nous présentons une généralisation de l'ordre faible, le s-ordre faible sur une certaine famille d'arbres et discutons du s-Permutaèdre associé et de sa réalisation possible comme complexe polytopal. En collaboration avec Cesar Ceballos.

12 octobre 2023
Salle Maurice Fréchet (05)

14h00 Pegah Pournajafi Collège de France

Geometric graphs and their chromatic number

Do geometric constraints cause the chromatic number of intersection graphs to be bounded? Motivated by a question by Erdős from the 1970s, in 2012, Pawlik, Kozik, Krawczyk, Lasoń, Micek, Trotter, and Walczak showed that for a large family of classes of triangle-free intersection graphs of geometric objects, the answer is negative. Surprisingly, their proof relied on exhibiting the same specific class of graphs -- Burling graphs -- inside every one of those classes. Since then, the question of exactly characterizing Burling graphs as such intersection graphs attracted attention. In this presentation, after a brief review of the literature, I introduce this exact subclass and discuss the implications of such characterizations.

15h30 Omid Amini École Polytechnique

Higher rank inner products, higher rank Voronoi tilings, and metric degenerations.

I will introduce higher rank inner products as multiscale limits of scalar products on real and complex vector spaces, and discuss interesting features of their corresponding higher rank Voronoi tilings. The framework is then used to describe Gromov-Hausdorff limits of flat tori and Hausdorff limits of Voronoi tilings. Time permitting, I will present applications to asymptotic complex geometry. Based on joint work with N. Nicolussi.

22 juin 2023

14h Stéphane Sabourau UPEC-LAMA

Métriques systoliquement extrémales sur des surfaces à courbure négative.

La régularité des surfaces systoliquement extrémales (c'est-à-dire des surfaces d'aire minimale à systole fixée) est un problème délicat déjà discuté par M. Gromov dans les années 80. Nous proposons d'étudier le problème des métriques systoliquement extrémales dans le contexte des métriques généralisées de courbure négative. Une approche naturelle est de travailler dans la classe des surfaces d'Alexandrov de courbure totale finie, où l'on peut exploiter les outils de complétude fournis dans le contexte des mesures de Radon telles qu'elles ont été étudiées par Reshetnyak et d'autres. Cependant, les métriques généralisées dans ce sens n'ont pas assez de régularité. À la place, nous développons une approche plus élémentaire qui se prête au développement d'algorithmes et montrons que, pour chaque genre, toute surface systoliquement extrémale à courbure négative est plate par morceaux avec un nombre fini de singularités coniques. Ce résultat ramène un problème de minimisation en dimension infinie au cas de la dimension finie. Travail en commun avec M. Katz.

15h30 Bram Petri Université Sorbonne. IMJ-PRG

Comment couper en deux une surface hyperbolique de manière efficace.

La constante de Cheeger (ou constante isopérimétrique) d'une surface hyperbolique mesure la difficulté de couper en deux la surface. Dans cet exposé je parlerai d'un travail en commun avec Thomas Budzinski et Nicolas Curien sur la constante de Cheeger maximale possible d'une surface hyperbolique fermée.

09 février 2023

14h Andreas Holmsen KAIST

Combinatorics in convexity spaces

“Does Radon’s theorem imply the fractional Helly Property?” This question by Kalai was the motivation for some exciting recent developments on convexity spaces, in particular concerning the relationship between (1) the fractional Helly Property, (2) the existence of finite weak epsilon nets, and (3) a bounded Radon number. In this talk we discuss the works of Alon-Kalai-Matousek-Meshulam (2002), Moran-Yehudayoff (2019), and Holmsen-Lee (2021), which combined reveal the surprising fact that these three properties are equivalent. We will also explore some connections to chi-boundedness in certain classes of graphs and hypergraphs.

15h30 Pierre Pansu Université Paris Saclay

Expanders and distances between normed chain complexes

Expansion in graphs can be measured either by an isoperimetric constant or a spectral gap. We show that both can be expressed by suitable distances on the space of normed chain complexes.

15 décembre 2022

14h Adrien Vladu CNRS, IRIF

Discrepancy Minimization via Regularization.

We introduce a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to re-interpret several breakthrough works in algorithmic discrepancy, ranging from Spencer's theorem to Banaszczyk's bound. Using our techniques, we also show that the Beck-Fiala and Komlos conjectures are true for a new regime of pseudorandom instances. Joint work with Lucas Pesenti (SODA 2023), paper: https://arxiv.org/abs/2211.05509

13 octobre 2022

14h Stephane Gaubert INRIA and CMAP, Ecole polytechnique

Tropical Convexity, Mean Payoff Games and Nonarchimedean Convex Programming

Convex sets can be defined over ordered fields with a non-archimedean valuation. Then, tropical convex sets arise as images by the valuation of non-archimedean convex sets. The tropicalization of polyhedra and spectrahedra can be described in terms of deterministic and stochastic games with mean payoff, being characterized in terms of sub or super-fixed point sets of Shapley operators, which determine the value of the game. This is motivated by open complexity issues in game theory and linear programming -- leading in particular to a counter example showing that interior point methods are not strongly polynomial. We shall give an overview of these results. This is based on a series of works with Allamigeon, Benchimol, Joswig, Skomra and Vandame.

15h30 Kristof Huszar Inria Sophia Antipolis

Thin triangulations of 3-manifolds: constructions and obstructions

Parameterized algorithms have recently been gaining prominence in low-dimensional topology. It has been shown that several computationally hard problems about triangulated 3-manifolds can be efficiently solved, provided the dual graph of the input triangulation has small treewidth. Finding such "thin" triangulations is therefore an important task, however, it can be limited by the topology of the underlying manifold. In this talk I present recent results that link the treewidth and other combinatorial width parameters associated with triangulations to classical topological invariants in a quantitative way. In particular, we show that, for certain 3-manifolds every triangulation must have dual graph of large treewidth. We establish these results through constructions involving generalized Heegaard splittings and layered triangulations of 3-manifolds. Joint work with Jonathan Spreer and Uli Wagner.

16 juin 2022

14h Hugo Parlier Université du Luxembourg

Ordering curves on hyperbolic surfaces

This talk will be about different questions pertaining to the set of lengths of closed geodesics on hyperbolic surfaces. A classical question is to ask to what extent the set of lengths determine a surface. Here the setup will be slightly different: how much do you know about a surface if you know which curves are the shortest and without actually knowing their lengths? Some of the results are joint with Cayo Dória.

21 avril 2022

14h Vincent Despré LORIA

Flipping geometric triangulations on hyperbolic surfaces

We will describe the behavior of the classical Delaunay flip algorithm in the case of hyperbolic surfaces. The complexity of the algorithm depends not only on the number of points of the input triangulation but also on its diameter. Indeed, there are infinitely many different triangulations on a given hyperbolic surfaces with some fixed points. We will give a proof of a polynomial bound for the flip algorithm but also experimental evidences that this bound is largely overestimated. This result can be intuitively explained by the structure of the mapping class group of surfaces.

15h30h Theo Lacombe UGE-LIGM

Transport Optimal : Régularisation Entropique et Homogénéité.

Le problème de transport optimal, dont les origines remontent à Monge, fournit une métrique pour comparer des mesures de probabilités via un problème d'optimisation. Si ce problème possède de nombreuses propriétés théoriques importantes, sa résolution numérique devient rapidement trop lourde et sa limitation aux mesures de probabilités est contraignante. Cet exposé proposera une introduction au problème de transport optimal, d'abord dans sa forme la plus classique, puis dans ses variantes modernes qui font son succès aujourd'hui notamment en apprentissage : la régularisation entropique et le transport déséquilibré. Dans un travail récent [1], T.Séjourné et ses co-auteurs proposent un modèle unifiant ces deux formalismes. Dans certains cas (non-standard), ce nouveau modèle fait apparaître des inhomogénéités qui peuvent mener à des incohérences numériques. Nous ferons la lumière sur ce phénomène et proposerons une correction possible pour obtenir un modèle de transport régularisé déséquilibré homogène, introduit dans [2]. [1] T.Séjourné, J Feydy, FX Vialard, A Trouvé, G Peyré : Sinkhorn divergences for unbalanced optimal transport. [2] TL. An Homogeneous Unbalanced Regularized Optimal Transport model with application to Optimal Transport with Boundary

24 mars 2022

14h Karim Adiprasito University of Copenhagen & Hebrew University of Jerusalem

Unimodality of the h-star polynomial

We prove a conjecture of Hibi and Stanley concerning the unimodality of the hstar polynomial of reflexive lattice polytopes by extending some deep results in algebraic geometry.

15h30h Jonathan Spreer University of Sydney

An algorithm to compute the crosscap number of a knot

An algorithm to compute the crosscap number of a knot The crosscap number of a knot is the non-orientable counterpart of its genus. It is defined as the minimum of one minus the Euler characteristic of S, taken over all non-orientable surfaces S bounding the knot. Computing the crosscap number of a knot is tricky, since normal surface theory - the usual tool to prove computability of problems in 3-manifold topology, does not deliver the answer "out-of-the-box". In this talk, I will review the strengths and weaknesses of normal surface theory, focusing on why we need to work to obtain an algorithm to compute the crosscap number. I will then explain the theorem stating that an algorithm due to Burton and Ozlen can be used to give us the answer. This is joint with work with Jaco, Rubinstein, and Tillmann.

16 décembre 2021

14h Monique Teillaud INRIA-Nancy

Triangulations in CGAL - To non-Euclidean spaces and beyond!

The talk will review some of the basic ideas underlying the design of the classic triangulation packages in CGAL, the Computational Geometry Algorithms Library. Then it will present more recent work on the computation of Delaunay triangulations of some flat tori and of the Bolza surface, and show how the CGAL basic ideas could be extended. Triangulations are known to have many applications. The talk will exhibit concrete uses of the various CGAL triangulation packages.

15h30h Matej Stehlik Université de Paris-IRIF

Edge-critical subgraphs of Kneser graphs

In a landmark paper from the late 1970s, Lovász proved a conjecture on the chromatic number of Kneser graphs using one of the first applications of algebraic topology in combinatorics. Schrijver sharpened the result by exhibiting a vertex-critical subgraph of the Kneser graph with the same chromatic number. I will sketch how we can go a step further, by constructing an edge-critical subgraph of the Kneser graph with the same chromatic number. Joint work with Tomas Kaiser.

21 octobre 2021

14h Artem Zvavitch Université Gustave Eiffel & Kent State University

Volume product and Mahler conjecture for convex bodies.

Let K be convex, symmetric, with respect to the origin, body in R^n. One of the major open problems in convex geometry is to understand the connection between the volumes of K and the polar body K^∗. The Mahler conjecture is related to this problem and it asks for the minimum of the volume product vol(K)vol(K^* ). In 1939, Santalo proved that the maximum of the volume product is attained on the Euclidean ball. About the same time Mahler conjectured that the minimum should be attained on the unit cube or its dual - cross-polytope. Mahler himself proved the conjectured inequality in R^2. The question was recently solved by H. Iriyeh, M. Shibata, in dimension 3. The conjecture is open staring from dimension 4. In this talk I will discuss main properties and ideas related to the volume product and a few different approaches to Mahler conjecture. I will also present a shorter solution for three dimensional case (this is a part of a joint work with Matthieu Fradelizi, Alfredo Hubard, Mathieu Meyer and Edgardo Roldán-Pensado).

15h30h Thierry Monteil LIPN - CNRS

Quantifying the aperiodicity of a Wang tile set.

A Wang tile set is a finite set of unit squares where each edge got a color. A tile set T tiles the plane if the plane can be covered by Z^2-translated copies of elements of T, where two adjacent edges must have the same color. A tile set is aperiodic if it tiles the plane, but if this can not be done in a periodic way. Most aperiodic tilings are obtained from a substitution process (Penrose, Ammann-Beenker, Robinson,...). We will introduce two invariants to quantify the level of aperiodicity of a Wang tile set. The first one is topological, the second is metric. They both rely on the way a tile set tile can tile other objects than the plane. The second invariant allows us to prove that the tile sets of Kari and Culik are not ruled by a substitution process.

22 avril 2021

14h Sergey Avvakumov University of Copenhagen

A subexponential size triangulation of ${\mathbb R}P^n$.

A practical way to encode a manifold is to triangulate it. Among all possible triangulations it makes sense to look for the minimal one, which for the purpose of this talk means using the least number of vertices. Consider a family of manifolds such as $S^n$, ${\mathbb R}P^n$, $SO_n$, etc. A natural question is how the size of the minimal triangulation depends on $n$? Surprisingly, except for the trivial case of $S^n$, our best lower and upper bounds are very far apart. For ${\mathbb R}P^n$ the current best lower and upper bounds are around $n^2$ and $\phi^n$, respectively, where $\phi$ is the golden ratio. In this talk I will present the first triangulation of ${\mathbb R}P^n$ with a subexponential, approximately $\sqrt{n}^\sqrt{n}$, number of vertices. I will also state several open problems related to the topic. This is a joint work with Karim Adiprasito and Roman Karasev.

Lien réunion Zoom

ID de réunion : 787 498 6280. Code secret : NJEy2h

25 mars 2021

14h Emo Welzl ETH Zurich

Triangulation Flip Graphs of Planar Point Sets

Full triangulations of a finite planar point set P are maximal straight-line embedded plane graphs on P. In partial triangulations some non-extreme points can be skipped. Flips are minimal changes in triangulations. They define an adjacency relation on the set of triangulations of P, giving rise to the flip graph of all (full or partial) triangulations of P. In the seventies Lawson showed that flip graphs are always connected. Our goal is to investigate the structure of flip graphs, with emphasis on their vertex-connectivity. We obtain similar bounds as they follow for regular triangulations from secondary polytopes via Balinski’s Theorem. Joint work with Uli Wagner, IST Austria

Lien réunion Zoom

ID de réunion : 787 498 6280. Code secret : NJEy2h

25 févriere 2021

14h Duncan Dauvergne Princeton University

The Archimedean limit of random sorting networks

Consider a list of n particles labelled in increasing order. A sorting network is a way of sorting this list into decreasing order by swapping adjacent particles, using as few swaps as possible. Simulations of large-n uniform random sorting networks reveal a surprising and beautiful global structure involving sinusoidal particle trajectories, a semicircle law, and a theorem of Archimedes. Based on these simulations, Angel, Holroyd, Romik, and Virag made a series of conjectures about the limiting behaviour of sorting networks. In this talk, I will discuss how to use the local structure and combinatorics of random sorting networks to prove these conjectures.

Lien réunion Zoom

ID de réunion : 787 498 6280. Code secret : NJEy2h

28 janvier 2021

14h Raman Sanyal Goethe-Universität Frankfurt

Inscribable polytopes, routed trajectories, and reflection arrangements.

Steiner posed the question if any 3-dimensional polytope had a realization with vertices on a sphere. Steinitz constructed the first counter examples and Rivin gave a complete answer to Steiner's question. In dimensions 4 and up, the Universality Theorem indicates that certifying inscribability is difficult if not hopeless. In this talk, I will address the following refined question: Given a polytope P, is there a continuous deformation of P to an inscribed polytope that keeps corresponding faces parallel? In other words, is there an inscribed polytope P’ that is normally equivalent (or strongly isomorphic) to P? This question has strong ties to deformations of Delaunay subdivisions and ideal hyperbolic polyhedra and its study reveals a rich interplay of algebra, geometry, and combinatorics. In the first part of the talk, I will discuss relations to routed trajectories of particles and reflection groupoids and show that that the question is polynomial time decidable. In the second part of the talk, we will focus on class of zonotopes, that is, polytopes representing hyperplane arrangements. It turns out that inscribable zonotopes are rare and intimately related to reflection groups and Gr\"unbaum's quest for simplicial arrangements. This is based on joint work with Sebastian Manecke.

Lien réunion Zoom

ID de réunion : 787 498 6280. Code secret : NJEy2h

10 décembre 2020

14h Andrey Kupavskii GSCOP

The extremal number of surfaces

In 1973, Brown, Erdős and Sós proved that if H is a 3-uniform hypergraph on n vertices which contains no triangulation of the sphere, then H has at most O(n^{5/2}) edges, and this bound is the best possible up to a constant factor. Resolving a conjecture of Linial, also reiterated by Keevash, Long, Narayanan, and Scott, we show that the same result holds for triangulations of the torus. Furthermore, we extend our result to every closed orientable surface S. Joint work with Alexandr Polyanskii, István Tomon and Dmitriy Zakharov

19 novembre 2020

14h Steve Oudot Inria, École Polytechnique

The pre-image problem from a topological perspective

This talk will be a review of the efforts of the Topological Data Analysis (TDA) community to tackle the preimage problem. The main focus will be on recent attempts to invert the TDA operator, either locally or globally. While this line of work is still in its infancy, the hope on the long run is to use such inverses for feature interpretation. The mathematical tools involved in the analysis come mainly from metric geometry, spectral theory, nonsmooth analysis, and the theory of constructible functions---specific pointers will be given in the course of the exposition.

Lien: https://bigbluebutton2.imj-prg.fr/b/arn-eh9-rnh (code d'accès 139013).

15 octubre 2020

14h Andrea Sportiello CNRS and LIPN, Universite' Paris 13

Some properties of the Euclidean Random Assignment Problem in dimension 2

The Euclidean Random Assignment Problem (ERAP) goes as follows: let X={x1,...,xn} and Y={y1,...,yn} be uniform iid on a variety Omega of dimension d, and, for a bijection pi: X -> Y, let H(pi)=sum_i dist(xi,y_pi(i))^2. The cost E(X,Y) of the pair (X,Y) is E = min_pi H(pi). How does the average of E scale with n? Surprisingly, in the most interesting case of d=2, logarithmic factors come into play, and we now know that = ln n / (2 pi) + ... This result has been conjectured by Caracciolo et al. in 2015 (CLPS), and proven by Ambrosio et al. in 2017. It is conjectured, but still unproven (and possibly false), that the series of corrections goes as = ln n / (2 pi) + c(Omega) + ... where the constant c(Omega) depends on the variety Omega. Recently, in various works, we have pushed further the CLPS theory. Under one basic (conjectural) assumption, we have derived 1) the exact difference of the asymptotic average constants, c(Omega)-c(Omega'), for the problem on two different varieties, in terms of the "Robin mass" of the varieties, that is, a suitable limit of the Zeta function associated to the spectrum of the Laplace-Beltrami operator on the two varieties. 2) a number of "linear relations" among the energies of different (not averaged) systems, in which various point configurations are combined: although the single summands are all of order ln n, the combination is a random quantity with small variance (possibly, of order (ln n)^2/n). This work is in collaboration with Sergio Caracciolo, Matteo D'Achille and Gabriele Sicuro, and in part with Dario Benedetto and Emanuele Caglioti (arXiv:2008.01462).

Lien: https://bigbluebutton2.imj-prg.fr/b/arn-eh9-rnh (code d'accès 13901X). Où X est le premier entier supérieur à 2.

23 janvier 2020

14h Sanjay Ramassamy Institut de Physique Théorique, CEA Saclay

Extensions of partial cyclic orders, boustrophedons and polytopes

While the enumeration of linear extensions of a given poset is a well-studied question, its cyclic counterpart (enumerating extensions to total cyclic orders of a given partial cyclic order) has been subject to very little investigation. In this talk I will introduce some classes of partial cyclic orders for which this enumeration problem is tractable. Some cases require the use of a multidimensional version of the classical boustrophedon construction (a.k.a. Seidel-Entringer-Arnold triangle). The integers arising from these enumerative questions also appear as the normalized volumes of certain polytopes.
This is partly joint work with Arvind Ayyer (Indian Institute of Science) and Matthieu Josuat-Verges (Laboratoire d’Informatique Gaspard Monge / CNRS).

15h30 Vincent Pilaud CNRS & École Polytechnique

Quotientopes

Cet exposé présentera certains aspects combinatoires et géométriques des quotients de treillis de l'ordre faible sur les permutations (le prototype est le treillis de Tamari). En particulier, Nathan Reading a montré que pour toute congruence de l'ordre faible, les cones obtenus en recollant les régions de l'arrangement de Coxeter dans une même classe d'équivalence forment un éventail complet. Je montrerai que cet éventail est l'éventail normal d'un polytope que j'appelle quotientope, et je m'intéresserai au cas où un tel polytope peut s'obtenir en retirant des facettes du permutaèdre (comme dans la construction classique de l'associaèdre). Si le temps le permet, je présenterai aussi ce que l'on sait sur les quotients du treillis des régions d'autres arrangements d'hyperplans, en particulier du groupe de Coxeter de type B. Adapté de différents travaux en commun avec Francisco Santos, Doriann Albertin, et Julian Ritter.

7 novembre 2019

14h János Pach Bézout chair

Strings and Order

Let $\omega(G)$ and $\chi(G)$ denote the clique number and chromatic number of a graph $G$, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called $x$-monotone if every vertical line intersects it in at most one point.
We solve a 25 years old problem by showing that for arbitrarily large integers $k$, there exist families of $x$-monotone curves such that their disjointness graphs $G$ satisfy $\omega(G)=k$ and $\chi(G)=\Omega(k^4)$. This bound is asymptotically tight.
If we drop the condition that the curves are $x$-monotone, then $\chi(G)$ cannot be bounded in terms of $k$. We construct, for every $g>3$, families of $n$ curves such that the girth of their disjointness graphs $G$ is at least $g$ and $\chi(G)=\Omega_g(\log n)$. This improves a result of Bollobás. Joint work with István Tomon.

15h30 Eddie Aamari LPSM, Paris Diderot

Estimating the reach of a manifold

Various problems within computational geometry and manifold learning encode geometric regularity through the so-called reach, a generalized convexity parameter. The reach $\tau_M$ of a submanifold $M \subset \mathbb{R}^D$ is the maximal offset radius on which the projection onto $M$ is well defined. The quantity $\tau_M$ renders a certain minimal scale of $M$, giving bounds on both maximum curvature and possible bottleneck structures. In this talk, we will study the geometry of the reach through an approximation theory perspective. We present new geometric results on the reach of submanifolds without boundary. An estimator $\hat{\tau}_n$ of $\tau_M$ will be described, in an idealized i.i.d. framework where tangent spaces are known. The estimator $\hat{\tau}_n$ is showed to achieve uniform expected loss bounds over a $\mathcal{C}^3$-like model. Minimax upper and lower bounds are derived. We will conclude with an extension to a model in which tangent spaces are unknown.

19 septembre 2019

14h Emeric Gioan LIRM, Université de Montpellier

The active bijection in hyperplane arrangements and oriented matroids

The active bijection in hyperplane arrangements (or more generally oriented matroids) consists in a framework of various interrelated results and constructions that appear when the ground set of the structure is linearly ordered. It notably involves canonical bijections betweens simplices and regions (or more generally bases and reorientations), a canonical decomposition of regions into bounded regions of minors, several expressions of the Tutte polynomial, as well as some strengthening of real linear programming.
Joint work with Michel Las Vergnas.

15h30 Federico Ardila San Francisco State University

The geometry of matroids

Matroid theory is a combinatorial theory of independence which has its origins in linear algebra and graph theory, and turns out to have deep connections with many other fields. With time, the geometric roots of the field have grown much deeper, bearing many new fruits.
Optimization and algebraic geometry, in particular, have provided very useful geometric models for matroids. These models have played a central role in the development of fascinating mathematics, and in the solution to long-standing questions. This talk will survey some recent successes.
I will discuss the work of many researchers, including my joint work with Caroline Klivans and with Graham Denham and June Huh. I will assume no previous knowledge of matroids.

23 mai 2019

14h Kaie Kubjas LIP6, Sorbonne Université

Geometry of nonnegative rank

One of many definitions gives the rank of an $m \times n$ matrix $M$ as the smallest natural number $r$ such that $M$ can be factorized as $AB$, where $A$ and $B$ are $m \times r$ and $r \times n$ matrices respectively. In many applications, we are interested in factorizations of a particular form. For example, factorizations with nonnegative entries define the nonnegative rank which is a notion that is used in data mining applications, statistics, complexity theory etc.
Nonnegative rank has geometric characterizations using nested polytopes. I will explain how to use these characterizations to study the semialgebraic geometry of the set of matrices of given nonnegative rank. In particular, I will recall what was previously known about the set of matrices of nonnegative rank at most $r$ for $r = 1, 2, 3$ and present recent results on the boundaries of the set of matrices of nonnegative rank at most four using notions from the rigidity theory of frameworks. These results are based on joint work with Robert Krone.

15h30 Marcos Cossarini Université Paris Est Marne-la-Vallée

Discrete surfaces with length and area and minimal fillings of the circle

In 1983, Gromov conjectured that the Euclidean hemisphere has minimum area among orientable Riemannian surfaces that fill isometrically a closed curve of given length. A surface fills isometrically its boundary curve if the distance between each pair of boundary points measured along the surface is not less than the distance measured along the boundary.
Motivated by Gromov's filling area conjecture (FAC), we propose to imagine that every Riemannian metric is discrete at the small scale, made of curves called walls. The length of a curve is its number of crossings with the walls, and the area of the surface is the number of crossings between the walls themselves. We pose a discrete version of the FAC: if a surface with walls fills isometrically its boundary of length 2n, then its area is at least n(n-1)/2. We discuss the connection with the original, continuous FAC.
If time allows, we discuss a newer discretization where the metric is directed. We now imagine that the surface is a simplicial set: roughly speaking, a triangulated surface where the edges are oriented. The length of each edge is 1 in the forward way and 0 in the reverse way, and the area of the surface is the number of triangles. These discrete surfaces are dual to Postnikov's plabic graphs.

28 mars 2019

14h Jean-Philippe Labbé Freie Universität Berlin

Dissections du carré avec des triangles de surface presque égale

[transparents]

Le théorème de Monsky de 1970 stipule qu'un carré ne peut pas être découpé en un nombre impair n de triangles ayant la même aire. La preuve de Monsky ne fournit pas une borne inférieure pour la différence minimale entre les aires des triangles. Durant l'exposé, nous explorerons ce problème de minimisation en géométrie. D'une part, nous donnons une borne inférieure doublement exponentielle à l'aide d'une technique provenant de géométrie semi-algébrique réelle. D'autre part, nous obtenons une première borne supérieure superpolynomiale pour ce problème, dérivée d'une construction explicite faisant intervenir la séquence de Thue-Morse.
Ces travaux ont été fait en collaboration avec Günter Rote et Günter M. Ziegler.

15h30 Matthieu Fradelizi Université Paris-Est Marne-la-Vallée

Inégalités d'Alexandrov-Fenchel locales sur les volumes mixtes de corps convexes et analogie avec la théorie de l’information

De nombreuses inégalités en théorie de l’information sur l’entropie de Shannon de la somme de variables aléatoires indépendantes ont leur analogue en théorie de Brunn-Minkowski sur le volume de la somme de corps convexes ainsi que sur les déterminants de sommes de matrices positives. Nous exposerons ces analogies et plus particulièrement des versions locales de l’inégalité d’Alexandrov-Fenchel portant sur la comparaison du volume d’un corps convexe avec celui de ses projections.

31 janvier 2019

14h Guillaume Chapuy CNRS, IRIF, Université Paris 7

Sur l'énumération asymptotique des triangulations coloriées de variétés d-dimensionnelles

En dimension $d>=3$ on prend $n$ simplexes, et on recolle leurs facettes de manière arbitraire. On obtient ainsi un espace topologique qui est a priori une pseudo-variété, mais pas toujours une variété. De combien de manières peut-on le faire, asymptotiquement, pour obtenir une variété ? On donne des réponses (très) partielles à cette question sous la forme de bornes inférieures et supérieures superexponentielles. En particulier on détermine le comportement surexponentiel en dimension $3$, dans le cas des triangulations coloriées issues des modèles de tenseurs. Au passage on croise des questions rigolotes et nouvelles d'énumération de graphes que nous laissons partiellement ouvertes. Travail en commun avec Guillem Perarnau.

15h30 Spencer Backman Hebrew University of Jerusalem

Cone valuations, Gram's relation, and flag-angles

Interior angle vectors of polytopes are semi-discrete analogues of $f$-vectors that take into account the interior angles at faces measured by spherical volumes. In this context, Gram's relation takes the place of the Euler-Poincaré relation as the unique linear relation among the entries of the interior angle vectors. Simple normalized cone valuations naturally generalize spherical volumes, and in this talk I will show that Gram's relation is the unique linear relation for angle vectors associated to a cone valuation. Our proof goes by way of establishing a connection with the combinatorics of zonotopes. I will then introduce flag-angle vectors as a counterpart to flag-$f$-vectors of polytopes, and determine their linear relations by coalgebra methods and a connection to the flag-vectors of lattices of flats. This is joint work with Sebastian Manecke and Raman Sanyal.

11 octobre 2018

14h Natan Rubin Ben-Gurion University

A stronger bound for weak epsilon-nets

We show that for any $n$-point set $P$ in the plan, there is a set $Q$ of cardinality $O(\epsilon^{-3/2})$ that pierces all the convex sets that contain at least $\epsilon n$ of the points of $P$. Such a set is commonly known as a weak $\epsilon$-net. This is the first improvement of the 25-year-old $O(\epsilon^{-2})$ bound of Alon, Barany, Furedi and Kleitman. The study of $\epsilon$-nets is central to Discrete and Computational Geometry.

15h30 Leonardo Martinez Sandoval Sorbonne Université

Further Consequences of the Colorful Helly's Theorem Hypothesis

The Colorful Helly Theorem is one of the most surprising and counter-intuitive generalizations of Helly's theorem. To state it, we start with a family $F$ of convex sets in $R^d$ split into the (non-neccesarily disjoint) union $F = F_1 \cup \dots \cup F_{d+1}$. We think of each $F_i$ as a color class. We say that this family satisfies the colorful hypothesis if every colorful $(d+1)$-subfamily (consisting of exactly one set from each color) is intersecting. The result states that if the family satisfies the colorful hypothesis, then at least one of the color classes is intersecting. A natural question is immediate: Why this happens for only one color class? What happens with the remaining color classes?
An easy example shows that there might not be a second intersecting color class. One of our results is that either there is a second color class that can be pierced by few points, or else all the remaining color classes can be pierced by few lines. Here « few » is a number that depends only on d and not on $|F|$. This result is remarkable in view of the few transversal line results for convex sets for $d>2$. In more generality, we classify the families satisfying the colorful hypothesis in terms of their transversal structure by flats. We also give an example that matches our results qualitatively.
The proof is based on the Alon-Kleitman's approach for proving the $(p,q)$-theorem. This approach combines the existance of epsilon-nets, linear programming duality and the fractional Helly's theorem. In the literature there are no results for epsilon-nets with lines to general convex sets, or general fractional Helly-results for transversal lines. Nevertheless, a delicate approach by induction allows us to repeatedly use epsilon-nets with hyperplanes in order to bound some fractional transversal numbers that naturally arise in the problem. From here we proceed by a similar combination of tricks as in the Alon-Kleitman's approach.
This is a joint work with Edgardo Roldán-Pensado and Natan Rubin.

24 mai 2018

14h Olivier Devillers Loria, Nancy

Walking in Poisson Delaunay triangulations

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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

[transparents]

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.

Anciens organisateurs :

• Luca Castelli (LIX,École Polytechnique),
• Éric Colin de Verdière (CNRS, LIGM, U. Paris-Est Marne-la-Vallée),
• Marc Glisse (Geometrica, Inria Saclay),
• Xavier Goaoc (LIGM, U. Paris-Est Marne-la-Vallée),
• Nabil Mustafa (LIGM, U. Paris-Est Marne-la-Vallée, ESIEE),
• Steve Oudot (Geometrica, Inria Saclay),
• Arnau Padrol (IMJ-PRG, Université Pierre et Marie Curie),
• Vincent Pilaud (CNRS, LIX, École Polytechnique).
• Michel Pocchiola (IMJ-PRG, Université Pierre et Marie Curie).