# Séminaires : Séminaire Francilien de Géométrie Algorithmique et Combinatoire

Combinatoire et Optimisation
Arnaud de Mesmay, Alfredo Hubard et Arnau Padrol
Big Blue Button

Le Séminaire de Géométrie Algorithmique et Combinatoire vise à regrouper des exposés dans ce domaine au sens le plus large, et dans les disciplines connexes en mathématiques et informatique. Il est ouvert à tous les chercheurs et étudiants intéressés. Les exposés sont destinés à un public large.

## Séances à suivre

+ Séances antérieures

### Séances antérieures

+ Monique Teillaud Triangulations in CGAL - To non-Euclidean spaces and beyond! 16/12/2021 14:00 IHP
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.
+ Matej Stehlik Edge-critical subgraphs of Kneser graphs 16/12/2021 15:30 IHP
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.
+ Zuzana Patáková On Radon and fractional Helly theorems 20/05/2021 14:00 ZOOM ID: 787 498 6280
Radon theorem plays a basic role in many results of combinatorial convexity. It says that any set of d+2 points in R^d can be split into two parts so that their convex hulls intersect. It implies Helly theorem and as shown recently also its more robust version, so-called fractional Helly theorem. By standard techniques this consequently yields an existence of weak epsilon nets and a (p,q)-theorem. We will show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. More precisely, given an intersection-closed family F of subsets of R^d, we will measure the complexity of F by the supremum of the first d/2 Betti numbers over all elements of F. We show that bounded complexity of F guarantees versions of all the results mentioned above. Based on joint work with Xavier Goaoc and Andreas Holmsen.
+ Emo Welzl Triangulation Flip Graphs of Planar Point Sets 25/03/2021 14:00 ZOOM
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
+ Duncan Dauvergne The Archimedean limit of random sorting networks 25/02/2021 14:00 ZOOM ID: 787 498 6280
+ Raman Sanyal Inscribable polytopes, routed trajectories, and reflection arrangements. 28/01/2021 14:00 ZOOM
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ünbaum's quest for simplicial arrangements. This is based on joint work with Sebastian Manecke.
+ Andrey Kupavskii The extremal number of surfaces 10/12/2020 14:00 ZOOM https://us04web.zoom.us/j/77213636727?pwd=RnZmWWVTY0Z6VjM5Q1VYYytYMHZSdz09
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.
+ Steve Oudot The pre-image problem from a topological perspective 19/11/2020 14:00 Big Blue Button
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.
+ Sanjay Ramassamy Extensions of partial cyclic orders, boustrophedons and polytopes 23/01/2020 14:00 421
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).
+ Vincent PILAUD Quotientopes 23/01/2020 15:30 421
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.
+ János Pach Strings and Order 07/11/2019 14:00 201

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.

+ Eddie Aamari Estimating the reach of a manifold 07/11/2019 15:30 201

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.

+ Emeric Gioan The active bijection in hyperplane arrangements and oriented matroids 19/09/2019 14:00 01
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.
+ Federico Ardila The geometry of matroids 19/09/2019 15:30 01
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.