Plenary speakers

Martina Juhnke, Universität Osnabrück, Monotone paths on polytopes: Positive and negative results

To solve a linear program, the simplex method follows a path in the graph of a polytope, on which a linear function increases. The length of this path is a key measure of the complexity of the simplex method. Our starting point is a conjecture by Jesús De Loera stating that the number of paths counted according to their length forms a unimodal sequence. We give examples (old and new) for which this conjecture is true but we disprove this conjecture by constructing counterexamples for several classes of polytopes. However, we show that De Loera is “statistically correct”: We prove that the length of a coherent path on a random polytope (with vertices chosen uniformly on a sphere) admits a central limit theorem. This is joint work with Germain Poullot.

Kolja Knauer, Universitat de Barcelona, Endomorphisms of Sparse Graphs

An endomorphism of a graph is a homomorphism from the graph to itself. Since endomorphisms are closed under composition, they form a monoid. It has been known since the 1960s that every finite monoid is isomorphic to the endomorphism monoid of some graph. This naturally led to the question of how restrictive a graph class \(\mathcal G\) can be while still realizing every monoid (from a given class) as the endomorphism monoid of a graph in \(\mathcal G\).

Particular attention has been devoted to sparse graph classes, such as planar graphs, minor-closed classes, and bounded-degree graphs. In this talk, I will survey some of the developments in this area and present two recent results that answer questions posed by Babai and Pultr in the 1980s:

1. Every commutative idempotent monoid (equivalently, every finite lattice) is isomorphic to the endomorphism monoid of a subcubic graph.
2. Every monoid is isomorphic to the endomorphism monoid of a regular graph.

Joint work with Gil Puig i Surroca.

Lisa Sauermann, Universität Bonn, Asymptotically-tight packing and covering with transversal bases in Rota’s basis conjecture

Rota’s basis conjecture from 1989 asserts that, given any n bases \(B_1,\dots,B_n\) of a vector space of dimension \(n\) (or, more generally, a matroid of rank \(n\)), one can find a collection of n disjoint transversal bases. In other words, this means that the union \(B_1 \cup \dots \cup B_n\) can be decomposed into \(n\) new bases of the vector space (or matroid), each consisting of exactly one element from each of the original bases \(B_1,\dots,B_n\). In this talk, we discuss some progress towards this famous conjecture, showing that the union \(B_1 \cup \dots \cup B_n\) contains \((1-o(1))n\) disjoint transversal bases, and also that the union \(B_1 \cup \dots \cup B_n\) can be covered by \((1+o(1))n\) transversal bases. Joint work with Richard Montgomery.

Dimitrios Thilikos, LIRMM, Montpellier, Deciding Asymptotic Properties of Minor-Closed Graph Classes

We examine the general problem of deciding properties of graph classes under the lens of quasi ordering relations. In particular, we consider properties of minor-closed graph classes whose finite descriptions are given by their obstruction sets. The question of whether such descriptions can be accompanied by polynomial-time decision algorithms can be viewed as a consequence of major questions in order theory. We present two instantiations of this general question for which such algorithms exist and can be explicitly constructed. In particular we examine asymptotic properties of minor-closed graph classes, such as growth constants and limiting densities.