Two-Day Workshop on
Combinatorics and Geometry.

The CG:SHOP geometric optimization competition is a satellite event of SoCG held every year since 2019. The Shadoks team won first or second place in 5 of these events. In this talk, we discuss the general ideas used to obtain such results. Notably, we describe how to fine tune greedy heuristics to obtain good initial solutions and how to use local search and conflict optimization to improve existing solutions. We also show how integer programming may be used to improve both phases.

The simplex method is perhaps the most important algorithm for solving linear programming problems in practice. However, we do not understand why this algorithm is so efficient; it takes exponential time in the theoretical worst case but only linear time in practice. Then I will introduce the state-of-the-art theoretical models for explaining the simplex method's performance. Finally, we will discuss in what ways the state-of-the-art fails to be a proper scientific theory and what needs to happen before we can hope to achieve such a thing. Along the way we will learn about women's history and more broadly the social context of linear programming.

In this talk, we discuss two problems related to data approximation: set discrepancy and simplicial partitions. We present efficient algorithms to solve them in geometric settings. For the former we build an algorithm based on a new mathematical game that we introduce and the celebrated result from Lovett and Meka that solves the set discrepancy question for abstract set system. For the latter, we present a fast algorithm that heuristically minimizes a potential function that we show lead to low crossing number partitions when they exist. Based on joint work with Victor-Emmanuel Brunel, Monika Csikos and Nabil Mustafa.

Pick $n$ independent and uniform random points $U_1,\ldots,U_n$ in a compact convex set $K$ of $\R^d$ with volume 1, and let $P^{(d)}_K(n)$ be the probability that these points are in convex position. The Sylvester conjecture in $\R^d$ is that $\min_K P^{(d)}_K(d+2)$ is reached by the $d$-dimensional simplices $K$ (only). In this talk, we focus on a companion model, already studied in the 2d case, that we define in any dimension $d$: we say that $K$ has $F$ as a flat floor, if $F$ is a subset of $K$, contained in an hyperplan $P$, such that $K$ lies in one of the half spaces defined by $P$ (in words, $K$ lies above a flat floor $F$, included in $K$). We define $Q_K^F(n)$ as the probability that $U_1,\cdots,U_n$ together with $F$ are in convex position (that is, the $U_i$ are on the boundary of the convex hull ${\sf CH}(\{U_1,\cdots,U_n\}\cup F\})$). We first focus on the 2d case which is actually the key to a large number of results in the general framework, and then have a look at this problem for larger dimensions. In this case, we prove that, in any dimension, for all fixed $F$, $K\mapsto Q_K^F(2)$ reaches its minimum on the "mountains" with floor $F$ (mountains are convex hull of $F$ union an additional vertex), while the maximum is not reached, but $K\mapsto Q_K^F(2)$ has values arbitrary close to 1. If the optimisation is done on the set of $K$ contained in $F\times[0,d]$ (the "subprism case"), then the minimum is also reached by mountains, and the maximum by the "prism" $F\times[0,1]$.

A flip is a very basic local operation that transforms one geometric graph into another. I will review a few old and new results on flips in certain geometric graphs and present some challenging open problems.
Based on joint work with Oswin Aichholzer, Kristin Knorr, Johannes Obenaus, Rosna Paul, Alexander Pilz, and Birgit Vogtenhuber.

The intersection graph of a collection C of sets is the graph whose vertex set is C and in which two sets in C are connected by an edge if and only if they have nonempty intersection. String graphs, intersection graphs of continuous curves (“strings”) in the plane have been studied intensively since the 1960s, for their exciting algorithmic and combinatorial properties and their applications in chip design, network theory, graph drawing and elsewhere. After giving a whirlwind tour of string graph theory, I will present some recent results and annoying open problems. In particular, I will sketch the proof of the following theorem, joint with Jacob Fox and Andrew Suk. Given a set R of n red curves, and and a set B of n blue curves in the plane such that any two of them meet at most once, there are subsets R′ ⊂ R and B′ ⊂ B with |R′|, |B′| ≥ Ω(n) with the property that either every curve in R′ crosses every curve in B′, or every curve in R′ is disjoint from every curve in B′.

The crossing lemma for simple graphs gives a lower bound on the necessary number of crossings of any planar drawing of a graph in terms of its number of edges and vertices. Viewed through the lens of topology, this leads to questions about arcs and curves on surfaces such as how many crossings must a collection of m homotopically distinct curves on a surface of genus g induce? The talk will be about joint work with Alfredo Hubard where we explore some of these, using tools from hyperbolic geometry in the process.