Random planar triangulations constitute a natural model of random geometry, and have been thoroughly studied in the last 20 years. In my talk, I will present some convergence results for these models -- in the local limit sense, as introduced by Benjamini and Schramm.

I will present a survey of the results available, both in the case where triangulations are sampled from a uniform distribution, and for which many results are available as well as in the case where triangulations are sampled with a probability distribution driven by a statistical physics model, and for which many natural questions are still open problems.

This is based on joint work with Laurent Ménard and Gilles Schaeffer.

When t is an integer that ranges from 1 to d, we introduce "t-constructible" and "t-LC" d-manifolds, interpolating between the known families of constructible and LC d-manifolds (case t=1), and the family of all triangulated d-manifolds (in case t=d). All t-LC manifolds are also (t+1)-LC.

Benedetti--Ziegler proved that LC d-manifolds are exponentially many: specifically, less than 2^{N d^2}. We expand this result by showing that 2-LC d-manifolds are still exponentially many: specifically, less than 2^{N (d^3)/2}. This is probably best possible, because if there are more than exponentially many 3-spheres, their suspensions yield more than exponentially many 3-LC manifolds.

Joint work with Marta Pavelka

The Multicut problem is defined as follows. Given an edge-weighted graph G and pairs of vertices (s_1,t_1), ..., (s_k,t_k), compute a minimum-weight subset of edges whose removal disconnects each pair (s_i,t_i).

This problem is hard: It is NP-hard, APX-hard, and W[1]-hard in the number of pairs of terminals, even in very simple cases, such as planar graphs.

We will survey some recent results on this problem, on planar graphs and more generally on graphs embedded on a fixed surface: An exact algorithm, whose running time is a polynomial in the genus and the number of terminals; a matching lower bound assuming ETH; and an approximation scheme with running time O(n\log n) if the approximation factor, the genus, and the number of terminals are fixed.

All these results rely on topological methods: The subgraph of the dual of G, made of the edges dual to a multicut, has nice properties, which can be exploited using classical tools from algebraic topology such as homotopy, homology, and universal covers of surfaces.

Based on joint works with Vincent Cohen-Addad, Dániel Marx, and Arnaud de Mesmay.

Worst-case constructions have helped providing a deeper understanding of how the structural properties of the input affect the computational performance of linear optimization. Recent examples include the construction of Allamigeon et al. for which the primal-dual log-barrier interior point method performs an exponential number of iterations, and thus is not strongly polynomial. In a similar spirit, recent lower bounds on the number of simplex pivots required in the worst-case to perform linear optimization over a lattice polytope will be presented, as well as the first worst-case instances for geometric scaling methods that solve integer optimization problems by primal augmentation steps.

This talk is based on joint works with Shmuel Onn, George Manoussakis, Sebastian Pokutta, and Lionel Pournin.

Tropical convexity provides a geometric approach to games with mean-payoff. Indeed, the spaces of sub of super-fixed points of Shapley operators (serving to certify that one of the players is winning) coincide with tropical convex cones and their duals. In this way, mean-payoff games reduce to tropical convex programming.

We will introduce here a more expressive and self-dual notion of convexity, called ambitropical, and present its main properties. Ambitropical cones coincide with the fixed-point sets of Shapley operators, and also with hyperconvex sets ---a classical notion introduced by Aronszajn and Panitchpakdi -- equipped with a cone structure. There is a notion of ambitropical hull, unique up to isometry, leading to a new, explicit, construction of Isbell's injective closure, a.k.a. ``tight span'', in the special case of cones. There is also a polyhedral version of ambitropical cones: these are polyhedral complexes, whose cells are alcoved polyhedra of A_n-type, they are defined either by finite generating families or by finite external representations, and they are characterized by lattice properties.

This is based on joint work with Marianne Akian and Sara Vannucci.

Intersection patterns of convex sets in R^d have the remarkable property that for d + 1 ≤ k ≤ l, in any sufficiently large family of convex sets in R^d, if a constant fraction of the k-element subfamilies have nonempty intersection, then a constant fraction of the l-element subfamilies must also have nonempty intersection.

In this talk, I will discuss a similar phenomenon for topological set systems in R^d. Quantitatively, the bounds depend on how complicated the intersection of l sets can be, as measured by the sum of the first Betti numbers.

This is based on joint work with Andreas F. Holmsen and Zuzana Patáková (https://arxiv.org/abs/2103.09286).

Given matroids M, N on E, can we decompose E into common bases of M and N? This problem includes tractable cases (such as decomposing a digraph into r-arborescences or edge-colouring bipartite graphs), but in general it is NP-hard, as shown by Bérczi and Schwarcz (2021). It was proved by Harvey, Király and Lau (2011) that the problem has a polynomial reduction to the special case where N is a (unitary) partition matroid.

We consider the case where M is a graphic matroid and N is a partition matroid, which corresponds to decomposing a graph G with a given (not necessarily proper) edge-colouring into rainbow spanning trees. Here, a subgraph of G is rainbow if it contains at most one edge of each colour.

Answering a question of Bérczi and Schwarcz, we show that it is NP-hard to decide whether G can be decomposed into k rainbow spanning trees, for any k ≥ 2.

We next turn to the problem of covering a graph G by rainbow spanning trees. Assuming that G is the union of k ≥ 3 spanning trees, and restricting to the case where each colour class contains at most two edges, we give bounds on the number of rainbow spanning trees covering G in terms of k. With a slightly weaker bound, this result extends to the matroidal setting.

Joint work with Florian Hörsch and Matthias Kriesell.

For a convex function f on a convex domain P in R^d, perspectivization provides the tightest convexification for the disjunction of (0,0,0) and {(1,x,f(x)) : x in P}. But perspectivization leads to the use of conic solvers for reliability, while conic solvers have some shortcomings. Using d-dimensional volume as a measure of looseness, considering the case where P is a simplex, we investigate some lighter relaxations with an eye toward understanding when they are tight enough.

I will discuss joint works with subsets of Daphne Skipper, Emily Speakman and Luze Xu.

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the Simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a singly exponential upper bound. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. For an n variable linear program in standard form, the number of iterations of our algorithm is at most O(n1.5 log n) times the number of segments of any piecewise linear curve in the wide neighbourhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the 'max central path', a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths.

This is joint work with Xavier Allamigeon, Daniel Dadush, Bento Natura and László Végh.

A closed quasigeodesic on a convex polyhedron is a closed curve that is locally straight outside of the vertices, where it forms an angle at most π on both sides. While the existence of a simple closed quasigeodesic on a convex polyhedron has been proved by Pogorelov in 1949, finding a polynomial-time algorithm to compute such a simple closed quasigeodesic has been repeatedly posed as an open problem.

Our first contribution is to propose an extended definition of quasigeodesics in the intrinsic setting of (not necessarily convex) polyhedral spheres, and to prove the existence of a weakly simple closed quasigeodesic in such a setting. Our proof does not proceed via an approximation by smooth surfaces, but relies on an adapation of the disk flow of Hass and Scott to the context of polyhedral surfaces.

Our second result is to leverage this existence theorem to provide a finite algorithm to compute a weakly simple closed quasigeodesic on a polyhedral sphere. On a convex polyhedron, our algorithm computes a simple closed quasigeodesic, solving an open problem of Demaine, Hersterberg and Ku.

This is joint work with Jean Chartier.

Given a set system (X, S), constructing a matching of X with low crossing number with respect to S is a key tool in combinatorics and algorithms. In this talk I will present a new sampling-based algorithm which is applicable to finite set systems. As an immediate consequence, we get improved bounds for constructing low-crossing matchings for a slew of both abstract and geometric problems, including many basic geometric set systems, implying faster algorithms for constructing epsilon-approximations. Joint work with Monika Csikos.

Let F be a family of open sets in a d-dimensional manifold M. In this talk we shall study what conditions allow us to state something about the nerve N(F) of F.

In 1997 Matoušek used hypergraph Ramsey theorem to prove that if the intersection of each subfamily is a union of at most r sets, each of which is ⌈d/2⌉-connected, there is a number M such that all "empty simplices" of N(F) have dimension less than H. The use of Ramsey theorem implies that the bound on H is "purely theoretical" and it is definitely not sharp.

The purpose of this talk is to develop a geometric Ramsey method that allows us to bypass the hypergraph Ramsey argument and obtain sharp bounds in some cases. As a very special case, we show that if M is a surface, the bound on H is linear in the genus of M.

We shall also discuss various directions, in which the previous result can be (and was) generalized.

For a set P of n points in R^d, for any d ≥ 2, a hyperplane h is called k-rich with respect to P if it contains at least k points of P. We show that if the number of k-rich hyperplanes in R^d, d ≥ 3, is 'large', then there exists a (d-2)-flat that contains 'many' points of P. We also present upper bound constructions that give instances in which is our result tight. An extension of our analysis yields similar lower bounds for k-rich spheres.

The problem is closely related to the problem of bounding the number of incidences between n points and m hyperplanes. Our proof uses several geometric tools, including point-hyperplane duality and simplicial partitions.

Based on joint work with Micha Sharir.

It is known that the largest possible volume for the intersection of a d-dimensional unit hypercube with a hyperplane H through its center is the square root of 2. This happens when H is orthogonal to a diagonal of a square face of the hypercube. This question can be generalized by considering the hyperplanes H at a fixed distance t to the center of the hypercube. Vitali Milman asked which among these hyperplanes have an intersection of maximal volume with the hypercube and conjectured that this happens when H is orthogonal to a diagonal or a sub-diagonal of the hypercube, depending on the value of t. Several recent results on this question are presented in this talk. In particular, when t is large enough (and smaller than the circumradius of the hypercube), the maximal volume is achieved exactly when the hyperplane is orthogonal to a diagonal of the hypercube. For smaller values of t, local extremality results will be presented at the diagonals and sub-diagonals of the hypercube.

The greedy algorithm on matroids is an important tool in optimization and combinatorics alike. Edmonds generalized it to polymatroid polytopes, certain convex polytopes that generalize independent set polytopes of matroids. From a geometric perspective, the greedy algorithm traces, for any given objective function, a monotone path in the graph of the polymatroid polytope. The starting point of this talk is the observation that this path is precisely the simplex path for the shadow vertex pivot rule. We show that all monotone paths are greedy path and hence are parametrized by the so-called monotone path polytope. Monotone path polytopes for polymatroids are again polymatroids and in the case of matroids, are precisely the associated (complete) flag matroids. I will discuss the geometry and combinatorics of such flag polymatroids in particular in relation to pivot rule polytopes. It turns out that (complete) flag polymatroids are combinatorially equivalent to certain nestohedra and hence simple polytopes. If time permits, I will also discuss relations to sorting networks and the enumeration of Young tableaux.

This is joint work with Alex Black.

This talk deals with two fundamental objects of discrete mathematics that are closely related - (convex) polytopes and matroids. Both appear in many areas of mathematics, e.g., algebraic geometry, topology and optimization.

A classical question in polyhedral combinatorics is 'Does the vertex-edge graph of a d dimensional polytope determine its face lattice?'. In general the answer is no, but a famous result of Blind and Mani, and later Kalai gives a positive answer of that question for simple polytopes. In my talk I discuss this reconstructability question for the special class of matroid (base) polytopes. Matroids encode an abstract version of dependency and independency, and thus generalize graphs, point configurations in vector spaces and algebraic extensions of fields.

This is joint work with Guillermo Pineda-Villavicencio

In this talk, I will present a notion of signed tropical convexity whose building blocks are cubical complexes arising from the faces of a hypercube and discuss how this convexity is connected to the theory of oriented matroids. The max-plus semifield can be equipped with a natural notion of convexity called the "tropical convexity". This convexity has many similarities with the standard convexity over the non-negative real numbers. In particular, it has been shown that tropical polyhedra are closely related to their classical counterparts. However, the restriction to non-negative numbers implies that some properties of classical objects are lost in the tropical setting. For instance, two generic tropical lines in a real tropical plane may not intersect. In order to avoid this problem, one can work with signed tropical numbers. Recently, a definition of convexity over the signed tropical numbers, called the TO-convexity, was proposed by Loho and Végh. I will present a new version of signed tropical convexity, called the TC-convexity. The TC-convexity is based on a non-commutative addition of signed tropical numbers, which generalizes the composition operation of signed sets that is used to define oriented matroids. Our main result is a hyperplane separation theorem for the TC-convexity. In particular, the separation provides a new interpretation of the real Bergman fan of oriented matroids. In order to prove this theorem, we characterize the signed tropical hemi-spaces. We also give the analogues of the Carathéodory theorem and the Minkowski-Weyl theorem for the TC-convexity. To finish the talk, I will present some open problems about the arrangements of signed tropical lines.

This talk is based on a joint work with Georg Loho.

Fullerenes molecules have been the subject of intense study ever since their discovery in 1985. They can be modelled by 3-connected cubic plane graphs with all faces of size 5 and 6. I will give an overview of the main properties of these so-called fullerene graphs, focusing mainly on those of a geometric nature.

We present algorithmic, complexity, and implementation results on the problem of sampling points from a spectrahedron, that is, the feasible region of a semidefinite program. Our main tool is geometric random walks. We highlight (and analyze the complexity) of their realization based on certain primitive geometric operations, that in turn exploit the algebraic properties of spectrahedra and the polynomial eigenvalue problem. We focus on sampling from log-concave distributions and, if time permits, we will present applications of independent interest, like approximating the volume of a spectrahedron and computing the expectation of functions coming from robust optimal control.

This is joint work with Apostolos Chalkis and Vissarion Fisikopoulos.

We prove that if a family of compact connected sets in the plane has the property that every three members of it are intersected by a line, then there are three lines intersecting all the sets in the family. This answers a question of Eckhoff from 1993, who proved that under the same condition there are four lines intersecting all the sets. In fact, we prove a colorful extension of this result under weakened conditions on the sets, improving also results of Holmsen from 2013. Our proofs use the topological KKM theorem.

Joint with Daniel McGinnis.