GT et PÉC de l'équipe Combinatoire et Interactions
The Combinatoire et Interactions seminar runs every Monday from 10h45 to 11h45. There is also a reserved schedule for a "mini-school" from 9h30 to 10h30. Both events happen in room 076 on the ground floor of LaBRI (building A30).
When a talk is recored it is available (live and recorded) at
https://u-bordeaux-fr.zoom.us/j/83326403471?pwd=VLapX1qCOgASs3V8OktWtKEr8dn041.1
Meeting ID: 833 2640 3471
Passcode: 1251442
Contact the secretaries (Vincent Delecroix, Oscar Fontaine and Juliette Schabanel) if you want to propose a talk or to receive announcements.
For the list of previous talks, look at the menu "GT CI" on the right side of this page.
2025-2026
Lundi 15 septembre : Ludovic Morin
Title : The magic triangle & other stories
Summary : Let P_K(n,m) be the probability that the convex hull of n+m points drawn uniformly and independently in a convex set K of area 1 (in the plane) has exactly n vertices.
Initial works on this quantity go back to the end of the 19th century and Sylvester's four points problem that focuses on the set K that optimizes the probability P_K(4,0). It was solved by Blaschke in 1917, and since then, more general results have followed for P_K(n,0) when K is a parallelogram, a triangle or a circle, as well as other asymptotic results.
In particular, an important work of 2000 by Bárány et al. gives the exact probability that n i.i.d. uniform points in a triangle abc form a convex chain between a and b (\ie the n points are on the boundary of the convex hull of these n points together with a and b). Furthermore, the limit of such a convex chain as n\to+\infty is the parabola joining a to b that is tangent to both ac and cb.
In the first part of this presentation, after introducing this tool and its properties, I'll try to demonstrate how it relates to P_K(n,0).
In the second part of the talk, I will study a generalized version of this magic triangle : n+m uniform points are drawn in abc and we look at the probability that exactly n points among the n+m are on the boundary of the convex hull of these points together with a and b.
We give asymptotics of the probability of such an event and formulate convergence theorems for this convex hull for special values of m. Based on these recent results, we'll conclude this talk with a few conjectures on the study of P_K(n,m).
Joint work with Jean-François Marckert.
Lundi 22 septembre : Loïc Dubois
Title: Algorithms for Topological and Metric Surfaces
Abstract: I will present the results of my thesis: algorithms for geometric and topological problems.
In a first part, we consider the problem of untangling graphs on surfaces: given a drawing of a graph on a surface, possibly with crossings, remove all crossings by deforming the drawing continuously, or correctly assert that this is not possible. We give the first polynomial time algorithms for this problem. To do so we introduce a new kind of triangulations of surfaces that discretize negative-curvature surfaces in a better way than the state of the art. On these triangulations, we provide a combinatorial analog of the celebrated barycentric embeddings of Tutte.
In a more geometric setting, we give a new efficient algorithm for computing a Delaunay triangulation of an abstract piecewise-flat surface (a generalization of meshes). We also study the classical Delaunay flip algorithm, and prove, when the surface is a flat torus, the first worst-case bound that is tight up to a constant factor. On hyperbolic surfaces, we provide an implementation of the Delaunay flip algorithm, collected in a package of the standard library of computational geometry CGAL, along with convenient generation and visualization tools.
Lundi 29 septembre: à saisir
Lundi 6 octobre: Arnaud de Mesmay
Lundi 13 octobre: à saisir
Lundi 20 octobre: soutenance de thèse de Zoé Varin à 10h
Lundi 27 octobre: vacances universitaires Toussaint
Lundi 3 novembre: à saisir
Lundi 10 novembre: Andrew Elvey-Price
Lundi 17 novembre: à saisir
Lundi 24 novembre: Alice Contat
Lundi 1 décembre: à saisir
Lundi 8 décembre: à saisir
Lundi 15 décembre: à saisir
Lundi 22 décembre: vacances universitaires Noël
Lundi 29 décembre: vacances universitaires Noël