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
+ 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.