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

Equipe(s) Responsable(s)SalleAdresse
Luca Castelli, Marc Glisse et Arnau Padrol

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

Orateur(s)Titre Date DébutSalleAdresse
+ Séances antérieures

Séances antérieures

Orateur(s)Titre Date DébutSalleAdresse
+ 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.