# Monday Lectures

Lecture at 14:15, Colloquium at 16:00, every Monday during the teaching period

→ Winter Semester 2020/21 Overview - all Monday Lectures of Winter Term 2020/21 will be given online

→ Summer Semester 2020 Overview - all Monday Lectures of Summer Term are cancelled

→ Winter Semester 2019/20 Overview

### Florian Frick (Carnegie Mellon University): New applications of the Borsuk--Ulam theorem

The classical Borsuk--Ulam theorem states that any continuous map from the d-sphere to d-space identifies two antipodal points. Over the last 90 years numerous applications of this result across mathematics have been found. I will survey some recent progress, such as results about the structure of zeros of trigonometric polynomials, which are related to convexity properties of circle actions on Euclidean space, a proof of a 1971 conjecture that any closed spatial curve inscribes a parallelogram, and finding well-behaved smooth functions to the unit circle in any closed finite codimension subspace of square-intergrable complex functions.

Location: online

### Pavle Blagojević (Freie Universität Berlin): Ten years in one lecture

Ten years ago, in February 2011, I joined the group of Günter M. Ziegler at Freie Universität Berlin. Now, ten years later, I will show you some of the problems in Geometric and Topological Combinatorics that intrigued us, some of which we managed to solve, and sketch some of the crucial ideas, methods, and the tools we had to develop in order to answer them. We will see how -- work on the Bárány-Larman conjecture on colored point sets in the plane gave birth to the Optimal colored Tverberg theorem, -- the constraint method collected all classical Tverberg type results under one roof and opened a door towards counter-examples to the topological Tverberg conjecture. Furthermore, we will illustrate how the search for convex partitions of a polygon into pieces of equal area and equal perimeter forced us to -- study the topology of the classical configuration spaces, -- construct equivariant cellular models for them, -- prove a new version of an equivariant Goresky-MacPherson formula for complements of arrangements, -- revisit a classical vanishing theorem of Frederick Cohen, and explain why these answers are related to the existence of highly regular embeddings and periodic billiard trajectories. Finally, we will talk about -- equi-partitions of convex bodies by affine hyperplanes, and -- greedy convex partitions of many measures. These results are joint work with, in chronological order, Günter M. Ziegler, Benjamin Matschke, Florian Frick, Albert Haase, Nevena Palić, Günter Rote, and Johanna K. Steinmeyer.

Location: online

### Michaela Borzechowski: One-Permutation-Discrete-Contraction is UEOPL-hard

The complexity class Unique End of Potential Line (UEOPL) was introduced in 2018 by Fearnley et al. and contains many interesting search problems. UEOPL captures problems that have either by definition a unique solution, like the Arrival problem, or that are promised to have a unique solution by some property, like the P-Matrix linear complementary problem. Furthermore the problems in UEOPL have the property that the candidate solutions can be interpreted as an exponentially large graph which form a line, i.e. each node has in and out degree at most 1. The solution of each problem is at the end of that line. In 2017, Daskalakis, Tzamos and Zampetakis proved the problem of finding a fixpoint of a contraction map in a continuous space whose existence is guaranteed by the Banach fixed point theorem to be CLS-complete. A discrete version of the contraction problem, called One-Permutation-Discrete-Contraction, is proven to be the first UEOPL-complete problem. This proof is particularly interesting because it is currently the only one of its kind and lays the groundwork for future UEOPL-completeness proofs. This talk will provide an overview of the reduction from the problem Unique-End-of-Potential-Line to One-Permutation-Discrete-Contraction as well as correcting some errors that were done in the original paper.

Location: online

### Shubhang Mittal:

Location: online

### Maria Dostert (Royal Institute of Technology): Exact semidefinite programming bounds for packing problems

In the first part of the talk, I present how semidefinite programming methods can provide upper bounds for various geometric packing problems, such as kissing numbers, spherical codes, or packings of spheres into a larger sphere. When these bounds are sharp, they give additional information on optimal configurations, that may lead to prove the uniqueness of such packings. For example, we show that the lattice E 8 is the unique solution for the kissing number problem on the hemisphere in dimension 8. However, semidefinite programming solvers provide approximate solutions, and some additional work is required to turn them into an exact solution, giving a certificate that the bound is sharp. In the second part of the talk, I explain how, via our rounding procedure, we can obtain an exact rational solution of a semidefinite program from an approximate solution in floating point given by the solver. This is a joined work with David de Laat and Philippe Moustrou.

Location: online

### CANCELED: Raman Sanyal (Goethe-Universität Frankfurt): From counting lattice points to counting free segments and back

This talk has been canceled on short notice, and will take place at a later time. Ehrhart theory, the art of counting lattice points in convex polytopes, is a cornerstone of the interplay of combinatorics and geometry. Many important combinatorial objects can be modelled as lattice points in polytopes and counting lattice points with respect to dilation yields deep results in combinatorics. Conversely, the combinatorics of polytopes provides a powerful framework for the computation of these counting functions with numerous algebraic/combinatorial consequnces and challenges. A lattice polytope is free if does not contain lattice points other than its vertices. Klain (1999) suggested a generalization of Ehrhart theory by counting free polytopes with $k$ vertices contained in dilates of a given polytope. For $k=1$, this is precisely Ehrhart theory. Determining these counting functions for $k > 1$ is quite challenging. For $k=2$ (free segments), this is related to counting lattice points visible from each other. In the talk I will discuss joint work with Sebastian Manecke on counting free segments in dilates of unimodular simplices. Our main tool is a number-theoretic variant of Ehrhart theory which can be computed using classical results from geometry. The talk will be scenic tour (with impressions from the unusual summer 2020).

Location: online

### Alp Müyesser: Rainbow factors and trees

Generalizing a conjecture of Aharoni, Joos and Kim asked the following intriguing question. Let H be a graph on m edges, and let G_i (1<=i<=m) be a sequence of m graphs on the common vertex set [n]. What is the weakest minimum degree restriction we can impose on each G_i to guarantee a rainbow copy of H? Joos and Kim answered this question when H is a Hamilton cycle or a perfect matching. We provide an asymptotic answer when H is an F-factor, or a spanning tree with maximum degree o(n/log n). This is joint work with Richard Montgomery and Yani Pehova.

Location: online

### Sampada Kolhatkar: Bivariate chromatic polynomials of mixed graphs

For a graph G=(V,E), the chromatic polynomial X_G counts the number of vertex colourings as a function of number of colours. Stanley’s reciprocity theorem connects the chromatic polynomial with the enumeration of acyclic orientations of G. One way to prove the reciprocity result is via the decomposition of chromatic polynomials as the sum of order polynomials over all acyclic orientations. From the Discrete Geometry perspective, the decomposition is as the sum of Ehrhart polynomials through real braid arrangement. Beck, Bogart, and Pham proved the analogue of this reciprocity theorem for the strong chromatic polynomials for mixed graph. Dohmen–Pönitz–Tittmann provided a new two variable generalization of the chromatic polynomial for undirected graphs. We extend this bivariate chromatic polynomial to mixed graphs, provide a deletion-contraction like formula and study the colouring function geometrically via hyperplane arrangements.

Location: online

### Jannik Peters: Efficiency and Stability in Euclidean Network Design

We study the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.[SPAA 2019] and investigate the creation of (beta,gamma)-networks, which are in beta-approximate Nash equilibrium and have a total cost of at most gamma times the optimal cost. In our model we have n agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple O(n^2)-time algorithm that computes a (beta,beta)-network with low beta for any given set of points. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve a conjecture about the Price of Anarchy.

Location: online

### Dante Luber: Boundary Complexes for Moduli Spaces of Curves

In 2016, Noah Giansiracua showed that a collection of boundary divisors in the moduli space of genus-0 n-pointed curves has nonempty intersection if and only if all pairwise intersections are nonempty. This result is equivalent to showing that the boundary complex associated to such a moduli space is a flag complex. Kyla Quillin extended Giansiracusa's result to most moduli spaces of genus-g n-pointed curves. We give a complete classification of all (g,n) pairs for which the boundary complex is a flag complex.

Location: online

### Matthias Himmelmann: Generalized Principal Component Analysis for Algebraic Varieties

The Buchberger-Möller algorithm is a famous symbolic method for finding all polynomials that vanish on a point cloud. It has even been extended to noisy samples. However, the resulting variety does not necessarily represent the topological or geometric structure of the data well. By making use of the Vandermonde matrix, it is possible to find polynomials of a prescribed degree vanishing on the samples. As this matrix is severely ill-conditioned, modifications are necessary. By making use of statistical and algebro-geometric techniques, an algorithm for learning a vanishing ideal that represents the data points‘ geometric properties well is presented. It is investigated that this method -- among various other desirable properties -- is more robust against perturbations in the data than the original algorithm.

Location: online

### Filippos Christodoulou: Design and Analysis of Combinatorial Problems in Random Intersection Graphs

Location: online

### Kemal Rose:

Location: online

### Stefan Mengel (CNRS): A Biased Introduction to Decomposable Negation Normal Forms

Decomposable Negation Normal Forms (DNNF) are a class of Boolean circuits first introduced by Darwiche in 2001 in the context of artificial intelligence. Since then they have found applications as a flexible framework for encoding Boolean functions in other areas of computer science like theoretical computer science and database theory. In this talk, I will introduce DNNF, discuss some uses and sketch how one can show bounds on their size.

Location: online

### Lisa Sauermann (IAS, Princeton): On the extension complexity of low-dimensional polytopes

It is sometimes possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. In this talk, we discuss some results on the extension complexity of random d-dimensional polytopes (obtained as convex hulls of random points on either on the unit sphere or in the unit ball), and on the extension complexity of polygons with all vertices on a common circle. Joint work with Matthew Kwan and Yufei Zhao.

Location: online

### Markus Bläser (Universität Saarbrücken): Irreversibility of tensors of minimal border rank and barriers for fast matrix multiplication

Determining the asymptotic algebraic complexity of matrix multiplication is a central problem in algebraic complexity theory. The best upper bounds on the so-called exponent of matrix multiplication if obtained by starting with an "efficient" tensor, taking a high power and degenerating a matrix multiplication out of it. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over the complex numbers: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. Joint work with Vladimir Lysikov.

Location: online

### Sophie Spirkl (University of Waterloo): k-coloring graphs with forbidden induced subgraphs

A k-coloring of a graph G is a function c that assigns an integer between 1 and k to every vertex of G such that c(u) is not equal to c(v) for every edge uv of G. Deciding, given a graph G, whether G has a k-coloring, is NP-hard for all k at least 3. In this talk, we will consider what happens when we restrict the input, that is: For a graph H and integer k, what is the complexity of deciding if a given graph G with no induced subgraph isomorphic to H has a k-coloring? We know the answer for many pairs H and k. Possibly the most interesting open cases are those in which H is a path; I will talk about recent results and open questions related to this.

Location: online

### Tillmann Miltzow (Utrecht University): A practical algorithm with performance guarantees for the art-gallery problem

Given a closed simple polygon P, we say two points p,q see each other if the segment pq is fully contained in P. The art gallery problem seeks a minimum size set G⊂P of guards that sees P completely. The only known algorithm to solve the art gallery problem exactly is attributed to Sharir and uses algebraic methods. As the art gallery problem is ∃R-complete, it seems impossible to avoid algebraic methods without additional assumptions. To circumvent this problem, we introduce the notion of vision stability. In order to describe vision stability, consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is "blocked" by an angle δ by reflex vertices. A polygon P has vision stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot algorithm that computes an optimal guard set for vision-stable polygons using polynomial time besides solving one integer program. We implemented an iterative version of the vision-stable algorithm. Its practical performance is slower, but comparable to other state-of-the-art algorithms. Our iterative algorithm is a variation of the one-shot algorithm. It delays some steps and only computes them only when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-width of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admits an FPT algorithm when parametrized by the chord-width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices. Joint work by Simon Hengeveld & Tillmann Miltzow.

Location: online

### Mikkel Abrahamsen (University of Copenhagen): A framework for ∃R-completeness of two-dimensional packing problems

We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is ∃R-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that the following combinations of allowed pieces and containers are ∃R-complete: - simple polygons, each of which has at most 8 corners, into a square, - convex objects bounded by line segments and hyperbolic curves into a square, - convex polygons into a container bounded by line segments and hyperbolic curves. Restricted to translations, we show that the following combinations are ∃R-complete: - objects bounded by segments and hyperbolic curves into a square, - convex polygons into a container bounded by segments and hyperbolic curves. Joint work by Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. The paper has been accepted for FOCS.

Location: online

### Amitabh Basu (Johns Hopkins University Baltimore): Complexity of cutting plane and branch-and-bound algorithms - cancelled

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In the first part of the talk, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We focus on variables disjunctions and split disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by showing that there are instances of the stable set problem where CP does exponentially better than BB. We further show that if one moves away from 0/1 polytopes, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). Finally, we show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up). In the second part of the talk, we will discuss the conjecture that the split closure has polynomial complexity in fixed dimension, which has remained open for a while now even in 2 dimensions. We settle it affirmatively in two dimensions, and complement it with a polynomial time pure cutting plane algorithm for 2 dimensional IPs based on split cuts.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

### Mikkel Abrahamsen (University of Copenhagen): Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane - cancelled

We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a 4/3*1.2965-approximation algorithm. Joint work with Panos Giannopoulos, Maarten Löffler, and Günter Rote. Presented at ICALP 2019.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

### Alina Stancu (Concordia University Montréal): Examples and usage of discrete curvature in convex geometry problems - cancelled

Discretization of curvature has found numerous applications particularly in the modeling of moving smooth boundaries separating two different materials and image processing. Nonetheless, there are usually several ways to address discretization of curvature, even in the case of a 1-dimenional object (a curve) depending in essence of the role of the curvature in the physical process or the problem considered. I will present two models of discretization of curvature that I was personally involved with in relation to two geometric problems where the objects considered were also convex.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

### CANCELED: Zsolt Ádám Wagner (ETH Zürich): Recent developments in the container method

This colloquium talk is canceled.

### José Samper (Max Planck Institut Leipzig): Dual matroid polytopes and the independence complex of a matroid

A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton.

### Lionel Pournin (Université Paris 13): Recent results on the diameter of lattice polytopes

Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

### Yanitsa Pehova (University of Warwick): Characterisation of quasirandom permutations by a pattern sum

We say that a sequence {π _ i } of permutations is quasirandom if, for each k>1 and each σ∈ S _ k , the probability that a uniformly chosen k-set of entries of π _ i induces σ tends to 1/ k ! as i tends to infinity. It is known that a much weaker condition already forces π _ i to be quasirandom; namely, if the above property holds for all σ∈ S 4 . We further weaken this condition by exhibiting sets S⊆ S 4 , such that if randomly chosen four entries of π _ i induce an element of S with probability tending to | S |/24, then {π _ i } is quasirandom. Moreover, we are able to completely characterise the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

### Sándor Kisfaludi-Bak (Max Planck Institut Saarbrücken): Separators and exact algorithms for geometric intersection graphs

Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH).

### Michał Włodarczyk (Eindhoven): Losing treewidth by separating subsets: on approximation of vertex/edge deletion problems

Consider the problem of deleting the smallest set S of vertices (resp. edges) from a given graph G such that the induced subgraph (resp. subgraph) G \ S belongs to some class H . I will cover the case where graphs in H have treewidth bounded by t , and give a general framework to obtain approximation algorithms basing on two ingredients: 1) approximation algorithms for the k -Subset Separator problem, 2) FPT algorithms parameterized by the solution size. For the vertex deletion setting, this new framework combined with the current best result for k -Subset Vertex Separator, improves approximation ratios for basic problems such as k -Treewidth Vertex Deletion and Planar F Vertex Deletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. I will talk about what it means for several important graph classes and how the bounded treewidth property is exploited. I will present a sketch of the proof for the H Vertex Deletion algorithm and explain the differences between deleting vertices or edges.

### Gweneth Anne McKinley (MIT, Cambridge, USA): Super-logarithmic cliques in dense inhomogeneous random graphs

In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1] ^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G ( n , W ), that can be viewed as a generalization of the Erdös-Rényi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order log n for the size of the largest clique in G ( n , W ) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G ( n , W ) will be of order √ n almost surely. We also give a family of examples with clique number of order n ^ c for any c in (0,1), and some conditions under which the clique number of G ( n , W ) will be o (√ n ) or ω(√ n ). This talk assumes no previous knowledge of graphons.

### Haim Kaplan (Tel Aviv University): Privately Learning Thresholds

We study the problem of computing a point in the convex hull, and the related problem of computing a separating hyperplane, under the constraint of differential privacy . Intuitively, differential privacy means that our output should be robust to small changes in the input (for example to adding or deleting a point). We study the minimum size of the input needed to achieve such a private computation (sample complexity) and its time complexity. Even in one dimension the problem is non-trivial and we will first focus on this case. Several interesting open problems will be presented as well. No previous background on differential privacy will be assumed.

### Gorav Jindal (Aalto University, Helsinki): On the Complexity of Symmetric Polynomials

The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f _Sym in C [ x 1 , x 2 ,..., x n ], there exists a unique "witness" f in C [ y 1 , y 2 ,..., y n ] such that f _Sym= f ( e 1 , e 2 ,..., e n ), where the e_ i 's are the elementary symmetric polynomials. In this work, we study the arithmetic complexity L ( f ) of the witness f as a function of the arithmetic complexity L ( f _Sym) of f _Sym. We show that the arithmetic complexity L ( f ) of f is bounded by poly( L ( f _Sym),deg( f ), n ). Prior to this work, only exponential upper bounds were known for L ( f ). The main ingredient in our result is an algebraic analogue of Newton’s iteration on power series. As a corollary of this result, we show that if VP is not equal to VNP then there are symmetric polynomial families which have super-polynomial arithmetic complexity. This is joint work with Markus Bläser.

### Alan Arroyo (Institute of Science and Technology Austria): Obstructions in graph drawings

Many nice results in graph theory involve the characterization of a graph class in terms of a set of forbidden obstructions. In this talk I will consider the problem of understanding whether a class of graph drawings can be characterized by a set of forbidden obstructions. I will do an overview on interesting recent results that fall under this theme, but I will emphasize more on those related to geometric arrangements.

### Holger Dell (IT University of Copenhagen): Counting and sampling small subgraphs

In this talk, we discuss various algorithmic techniques used for counting and sampling subgraphs in a large input graph. The focus of the talk is on the mathematical foundations. We start with the beautiful technique of Color-Coding (Alon, Yuster, Zwick 1995), and we discuss various generalizations based on group algebras (Koutis 2008) and on the exterior algebra (Brand, D, Husfeldt 2018). These techniques are most useful for sampling, which is equivalent to approximate counting. On the other hand, the fastest known algorithm to exactly count subgraphs that are isomorphic to a graph H (Curticapean, D, Marx 2017) is based on the foundations of Lovász' theory of graph limits.

### Shahrzad Haddadan (MPI Saarbrücken): Algorithms for top-k Lists and Social Networks

Today’s massive and dynamic data sets have motivated many computer scientists and mathematicians to study classical problems in combinatorics and graph theory in various settings. In certain settings the algorithms’ access to the data is restricted while in others the resources are limited. In this talk we explore such settings in three directions: ranking of objects, property testing in social networks and finding communities in dynamic graphs. In the first part, we discuss algorithms on permutations as well as prefixes of permutations also known as top- k lists. The study of later particularly arises in big data scenarios when analysis of the entire permutation is costly or not interesting. We start by discussing random walks on the set of full rankings or permutations of n objects, a set whose size is n !. Since 1990s to today, various versions of this problem have been studied, each for different motivation. The second part of the talk is devoted to property testing in social networks: given a graph, an algorithm seeks to approximate several parameters of a graph just by accessing the graph by means of oracles and while querying these oracles as few times as possible. We introduce a new oracle access model which is applicable to social networks, and assess the complexity of estimating parameters such as number of users (vertices) in this model. In the third part of the talk, we introduce a new dynamic graph model which is based on triadic closure: a friendship is more likely to be formed between a pair of users with a larger number of mutual friends. We find upper bounds for the rate of graph evolution in this model and using such bounds we devise algorithms discovering communities. I will finish this talk by proposing new directions and presenting related open problems.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

### Andrei Asinowski (Universität Klagenfurt): Vectorial kernel method and patterns in lattice paths

A directed lattice path is a polygonal line which starts at the origin and consists of several vectors of the form (1, y) (where y belongs to a fixed set of integers) appended to each other. Enumeration of different kinds of lattice paths (walks/bridges/meanders/excursions) was accomplished by Banderier and Flajolet in 2002. We refine and generalize their results by studying lattice paths that avoid a fixed pattern (or several patterns). To this end, we develop a "vectorial kernel method" – a unified framework for enumeration of words generated by a counter automaton. Another improtant tool is the "autocorrelation polynomial" that encodes self-overlappings of a pattern, and its generalization: the "mutual correlation matrix" for several patterns. (This talk is based on joint works with Cyril Banderier, Axel Bacher, Bernhard Gittenberger and Valerie Rointer.)

### Eric Fusy (École Polytechnique Paris): Bijections between families of walks using oriented planar maps

When counting walks (with a given step-set), an equi-enumeration phenomenom is often observed between a stronger constraint on the domain and a stronger constraint on the position of the endpoint (a classical one-dimensional example is the fact that positive walks of length 2 n are in bijection with walks of length 2 n ending at 0, both being counted by the central binomial coefficient). I will show examples of such relations for 2 d walks where the equi-enumeration can be bijectively explained using planar maps endowed with certain orientations (Schnyder woods, bipolar orientations).

### Lukas Kühne (Hebrew University of Jerusalem): Matroid representations by c-arrangements are undecidable

A matroid is a combinatorial object based on an abstraction of linear independence in vector spaces and forests in graphs. It is a classical question to determine whether a given matroid is representable as a vector configuration over a field. Such a matroid is called linear. This talk is about a generalization of that question from vector configurations to c-arrangements. A c-arrangement for a fixed c is an arrangement of dimension c subspaces such that the dimensions of their sums are multiples of c. Matroids representable as c-arrangements are called multilinear matroids. We prove that it is algorithmically undecidable whether there exists a c such that a given matroid has a c-arrangement representation. In the proof, we introduce a non-commutative von Staudt construction to encode an instance of the uniform word problem for finite groups in matroids of rank three. The talk is based on joint work with Geva Yashfe.

### Frank Sottile (Texas University): Irrational toric varieties and the secondary polytope

The secondary fan of a point configuration A in R^n encodes all regular subdivisions of A. These subdivisions also record all limiting objects obtained by weight degenerations of the irrational toric variety X_A parameterized by A. The secondary fan is the normal fan of the secondary polytope. We explain a functorial construction of R^n-equivariant cell complexes from fans that, when applied to the secondary fan, realizes the secondary polytope as the moduli space of translations and degenerations of X_A. This extends the work of Kapranov, Sturmfels and Zelevinsky (who established this for complex toric varieties when A is integral) to all real configurations A.

### Alexander Heaton (Max Planck Institut Leipzig): Applications of algebra to the geometry of materials

The upcoming Thematic Einstein Semester entitled "Geometric and Topological Structure of Materials" will focus on recent advancements in computational materials science. In this talk, we will present two interesting areas where algebra can play a role in future research. First, in the design and analysis of novel materials, questions of rigidity of frameworks arise. For generic configurations, matroid-theoretic and combinatorial techniques can be used to study rigidity. But the frameworks arising in applications are rarely generic, therefore deciding local rigidity presents a difficult computational problem which connects to the numerical algebraic geometry of varieties and semi-algebraic sets. Second, both point configurations and also polycrystalline materials give rise to cellular decompositions of 3-dimensional space. We will discuss how a Fourier-type analysis of these cells can be used to understand their approximate symmetry. The representation theory of SO(3) and its finite subgroups can be used to extract Fourier coefficients from the surface normal density of a given cell.

### Paweł Dłotko (Swansea University): Topology in Action

In this talk we will focus on a number of practical problems, originating from the theory of dynamical systems and materials science, all the way to medicine and data science. In all of them we will identify certain shapes that carry important information required to solve those problems. We will introduce standard and new tools of Topological Data Analysis and see how to apply them to the discussed scenarios.

### Marcel Celaya (Georgia Institute of Technology): The linear span of lattice points in a half-open lattice parallelepiped

The problem of deciding if there exists a lattice point inside a half-open parallelepiped on a given rational hyperplane is known to be NP-complete. In contrast, the question of deciding if all lattice points in a half-open parallelepiped lie on a given hyperplane has a much nicer answer. In this talk I will explain this answer in detail, and outline some applications.

### Svante Linusson (Königlich Technische Hochschule Stockholm): Limit shape of shifted staircase SYT

A shifted tableau of staircase shape has row lengths n,n-1,...,2,1 adjusted on the right side and numbers increasing along rows and columns. Let the number in a box represent the height of a point above that box, then we have proved that the points for a uniformly chosen random shifted staircase SYT in the limit converge to a certain surface in three dimensions. I will present this result and also how this implies, via properties of the Edelman–Greene bijection, results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. (Based on joint work with Samu Potka and Robin Sulzgruber.)

### Talks of the Einstein Workshop on Polytopes and Algebraic Geometry

Monday Dec. 2 (ZIB) Tuesday Dec. 3 (ZIB) Wednesday Dec. 4 (Hotel Steglitz Int.) 08.30 - 09.00 Registration 09.00 - 10.00 Benjamin Braun Johannes Hofscheier Winfried Bruns Coffee break 10.30 - 10.55 Andrés R. Vindas Meléndez Andrea Petracci Alessio D’Alì 11.00 - 11.25 Davide Bolognini María-Cruz Fernández-Fernández Eliana Duarte 11.30 - 11.55 Carlos Alejandro Alfaro Montufar Oguzhan Yürük Daniel Tamayo Jiménez Lunch 14.00 - 15.00 Alex Fink Thomas Kahle Alexander Borisov 15.10 - 15.35 Filip Cano Córdoba Karin Schaller Marta Panizzut Coffee break 16.10 - 17.10 Matthias Beck Matthias Schymura Fatemeh Mohammadi

Location: Freie Universität Berlin Zuse Institut Berlin Takustr. 7 14195 Berlin

### Manfred Scheucher (Techniche Universität Berlin): Topological Drawings meet SAT Solvers and Classical Theorems of Convex Geometry

In a simple topological drawing of the complete graph $K_n$, vertices are mapped to points in the plane, edges are mapped to simple curves connecting the corresponding end points, and each pair of edges intersects at most once, either in a common vertex or in a proper crossing. We discuss an axiomatization of simple drawings and for various sub-classes and present a SAT model. With the aid of modern SAT solvers, we investigate some famous and important classical theorems from Convex Geometry (such as Caratheodory’s, Helly's, Kirchberger's Theorem, and the Erdös-Szekeres Theorem) in the context of simple drawings. This is joint work with Helena Bergold, Stefan Felsner, Felix Schröder, and Raphael Steiner. Research is in progress.

### Georg Loho (London School of Economics and Political Science): Signed tropical convexity

Convexity for the max-plus algebra has been studied from different directions including discrete geometry, scheduling, computational complexity. As there is no inverse for the max-operation, this used to rely on an implicit non-negativity assumption. We remove this restriction by introducing `signed tropical convexity'. This allows to exhibit new phenomena at the interplay between computational complexity and geometry. We obtain several structural theorems including a new Farkas lemma and a Minkowski-Weyl theorem for polytopes over the signed tropical numbers. Our notion has several natural formulations in terms of balance relations, polytopes over Puiseux series and hyperoperations.

### Ansgar Freyer (Technische Universität Berlin): Discrete analogs of an inequality by Meyer

In 1988, Mathieu Meyer presented a lower bound on the volume of a convex body in terms of the volumes of its sections with the coordinate hyperplanes. Our aim is to "discretize" this inequality by replacing the volume by the lattice point enumerator. It turns out that such a discrete analog cannot exist for general convex bodies. Moreover, it will not imply its continuous counterpart. We prove inequalities for the case of o-symmetric bodies (using arithmetic progressions) and unconditional bodies (by proving a universal bound for the lattice point enumerator of unconditional lattice polytopes). Moreover, the talk will touch on a reverse inequality and other related problems.

### Matthias Reitzner (Universität Osnabrück): Stars of Empty Simplices

Consider an n-element point set in general position in d-dimensional space. For a k-element subset the degree is the number of empty d-simplices with this k-set as base. We investigate the maximal degree of a random point set consisting of n independently and uniformly chosen points from a compact set.

### Raphael Steiner (Technische Universität Berlin): Majority Colorings of Sparse Digraphs

A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen and Wood proved that every digraph has a majority 4-coloring and conjectured that every digraph admits a majority 3-coloring. We verify this conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3. We obtain analogous results for list coloring: We show that every digraph with list chromatic number at most 6 or list dichromatic number at most 3 is majority 3-choosable. We deduce that digraphs with maximum out-degree at most 4 or maximum degree at most 7 are majority 3-choosable. On the way to these results we investigate digraphs admitting a majority 2-coloring. We show that every digraph without odd directed cycles is majority 2-choosable. We answer an open question posed by Kreutzer et al. negatively, by showing that deciding whether a given digraph is majority 2-colorable is NP-complete. Finally we deal with a fractional relaxation of majority coloring proposed by Kreutzer et al. and show that every digraph has a fractional majority 3.9602-coloring. We show that every digraph D with sufficiently large minimum out-degree has a fractional majority-(2+ε)-coloring. Joint work with Michael Anastos, Ander Lamaison and Tibor Szabó.

### Tibor Szabó (Freie Universität Berlin): Turán numbers, projective norm graphs, quasirandomness

The Turán number of a (hyper)graph H, defined as the maximum number of (hyper)edges in an H-free (hyper)graph on a given number of vertices, is a fundamental concept of extremal graph theory. The behaviour of the Turán number is well-understood for non-bipartite graphs, but for bipartite H there are more questions than answers. A particularly intriguing half-open case is the one of complete bipartite graphs. The projective norm graphs $NG(q,t)$ are algebraically defined graphs which provide tight constructions in the Tur\'an problem for complete bipartite graphs $H=K_{t,s}$ when $s > (t-1)!$. The $K_{t,s}$-freeness of $NG(q,t)$ is a very much atypical property: in a random graph with the same edge density a positive fraction of $t$-tuples are involved in a copy of $K_{t,s}$. Yet, projective norm graphs are random-like in various other senses. Most notably their second eigenvalue is of the order of the square root of the degree, which, through the Expander Mixing Lemma, implies further quasirandom properties concerning the density of small enough subgraphs. In this talk we explore how far this quasirandomness goes. The main contribution of our proof is the estimation, and sometimes determination, of the number of solutions of certain norm equation system over finite fields. Joint work with Tomas Bayer, Tam\'as M\'esz\'aros, and Lajos R\'onyai.

### Liana Yepremyan (University of Oxford): On the size Ramsey number of bounded powers of bounded degree trees

We say a graph G is Ramsey for a graph H if every red/blue edge-colouring of the edges of G contains a monochromatic copy of H. The size Ramsey number of a graph H is defined to be the minimum number of edges among all graphs which are Ramsey for H. The study of size Ramsey numbers originated by the work of Erdős, Faudree, Rousseau and Schelp from 1970's. This number was studied for graphs including paths, cycles, powers of paths and cycles, trees of bounded degree. For all mentioned graphs it was shown that the size Ramsey number grows linearly in the number of vertices ("is linear"). This line of research was inspired by a question of Beck who asked whether the size Ramsey number is linear for graphs of bounded degree. Later this was disproved by Rödl and Szemerédi. In this talk I will present our recent result showing that fixed powers of bounded degree trees also have linear size Ramsey number. Equivalently, this result says that all graphs of bounded degree and bounded treewidth have linear size Ramsey number. We also obtain off-diagonal version of this result. Many exciting problems remain open. This is joint work with Nina Kam\v{c}ev, Anita Liebenau and David Wood.

### Günter Rote (Freie Universität Berlin): Lattice paths with states, and counting geometric objects via production matrices

We consider paths in the plane governed by the following rules: (a) There is a finite set of states. (b) For each state q , there is a finite set S ( q ) of allowable "steps" (( i,j) , q ′). This means that from any point ( x , y ) in state q , we can move to ( x + i , y + j ) in state q ′. We want to count the number of paths that go from (0,0) in some starting state q 0 to the point ( n ,0) without ever going below the x -axis. There are strong indications that, under some natural technical conditions, the number of such paths is asymptotic to C ^ n /(√ n ^ 3 ), for some "growth constant" C which I will show how to compute. I will discuss how lattice paths with states can be used to model asymptotic counting problems for some non-crossing geometric structures (such as trees, matchings, triangulations) on certain structured point sets. These problems were recently formulated in terms of so-called production matrices. This is ongoing joint work with Andrei Asinowski and Alexander Pilz.

### Benjamin Hauskeller (Humboldt-Universität zu Berlin): Dynamic Query Evaluation with Sublinear Update Time

Dynamic Query Evaluation considers the problem of evaluating a database query on a database using the following framework: In a preprocessing phase the query and an initial database are used to build a data structure which can enumerate the query result on the current database. Upon updates to the database the data structure is adapted to the new database. Research is then interested in the time needed for the preprocessing, the handling of an update, and the maximal delay between tuples during enumeration. In this talk I will present a new class of queries that can be maintained with linear preprocessing time, sublinear update time and constant delay.

Location: Humboldt-Universität zu Berlin Institut für Informatik Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

### Alexandre Vigny (Universität Bremen): Query enumeration and nowhere dense classes of graphs

Given a query q and a relational structure D the enumeration of q over D consists in computing, one element at a time, the set q(D) of all solutions to q on D. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. Idealy, we would like to have constant delay enumeration after linear preprocessing. Since this it is not always possible to achieve, we need to add restriction to the classes of structures and/or queries we consider. In this talk I will talk about some restrictions for which such algorithms exist: graphs with bounded degree, tree-like structures, conjunctive queries... We will more specifically consider nowhere dense classes of graphs: What are they? Why is this notion relevant? How to make algorithms from these graph properties?

Location: Humboldt-Universität zu Berlin Institut für Informatik Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

### Otfried Cheong (Universität Bayreuth): Convex Covers and Translation Covers

In 1914, Lebesgue asked for a convex set of smallest possible area that can contain a congruent copy of every set of diameter one. The same question can be asked for other families T of planar shapes: What is the convex set of smallest possible area that contains a congruent copy of every element of T? Such a set is then called a convex cover for T, and we will see what smallest-area convex covers for some families of triangles look like. A translation cover for a family T of planar shapes is defined similarly: Z is a translation cover for T if every element of T can be translated into Z. Kakeya's celebrated needle problem, first posed in 1917, turns out to be a question about a smallest-area translation cover. We will see that the generalization of Kakeya's problem to other shapes is also a translation cover problem.

### Vortrag außer der Reihe: Vijay Vazirani (University of California, Irvine): Matching is as Easy as the Decision Problem, in the NC Model Achtung: Dieser Vortrag ist an einem Freitag!

Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms. Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem. Our result builds on the work of Anari and Vazirani (2018), which used planarity of the input graph critically; in fact, in three different ways. Our main challenge was to adapt these steps to general graphs by appropriately trading planarity with the use of the decision oracle. The latter was made possible by the use of several of the ideadiscovered over the last five years. The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, Goldwasser and Grossman (2015) gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits. A corollary of our reduction is an analogous algorithm for general graphs. This talk is fully self-contained. Based on the following joint paper with Nima Anari: https://arxiv.org/pdf/1901.10387.pdf

### Anita Liebenau (University of New South Wales, Sydney): Enumerating graphs and other discrete structures by degree sequence

How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence, where G(n,p) is the homogeneous random graph in which every edge is inserted with probability p? Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for the number of graphs with a given degree sequence, for a wide enough range of degree sequences. From these enumeration formulae one can then deduce asymptotic formulae for the second question. McKay and Wormald showed that the formulae for the sparse case and the dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent binomial variables Bin(n − 1, p'). In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings.

### Manfred Scheucher (Technische Universität Berlin): On Arrangements of Pseudocircles

Towards a better understanding of arrangements of circles and also to get rid of geometric difficulties, we look at the more general setting of ''arrangements of pseudocircles'' which was first introduced by Grünbaum in the 1970's. An arrangement of pseudocircles is a collection of simple closed curves on the sphere or in the plane such that any two of the curves are either disjoint or intersect in exactly two points, where the two curves cross. In his book, Grünbaum conjectured that every digon-free arrangement of n pairwise intersecting pseudocircles contains at least $2n-4$ triangular cells. We present arrangements to disprove this conjecture and give new bounds on the number of triangular cells for various classes of arrangements. Furthermore, we study the ''circularizability'' of arrangements: it is clear that every arrangement of circles is an arrangement of pseudocircles, however, deciding whether an arrangement of pseudocircles is isomorphic to an arrangement of circles is computationally hard. Using a computer program, we have enumerated all combinatorially different arrangements of up to $7$ pseudocircles. For the class of arrangements of $5$ pseudocircles and for the class of digon-free intersecting arrangements of $6$ pseudocircles, we give a complete classification: we either provide a circle representation or a non-circularizability proof. For these proofs we use incidence theorems like Miquel's and arguments based on continuous deformation, where circles of an assumed circle representation grow or shrink in a controlled way. This talk summarizes results from two articles, which are both joint work with Stefan Felsner: * Arrangements of Pseudocircles: Triangles and Drawings; short version in Proc. GD'17; full version available at arXiv (1708.06449) * Arrangements of Pseudocircles: On Circularizability; short version in Proc. GD'18; full version in DCG: Ricky Pollack Memorial Issue (doi:10.1007/s00454-019-00077-y)

### Rekha R. Thomas (University of Washington): Graph Density Inequalities and Sums of Squares

Many results in extremal graph theory can be formulated as inequalities on graph densities. While many inequalites are known, many more are conjectured. A standard tool to establish an inequality is to write the expression whose nonnegativity needs to be certified as a sum of squares. This technique has had many successes but also limitations. In this talk I will describe new restrictions that show that several simple inequalities cannot be certified by sums of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovasz and Szegedy. This is joint work with Greg Blekherman, Annie Raymond, and Mohit Singh.

### Simona Boyadzhiyska (Freie Universität Berlin): On counting problems related to (mutually) orthogonal Latin squares

An n×n array with entries in [n] such that each integer appears exactly once in every row and every column is called a Latin square of order n . Two Latin squares L and L' are said to be orthogonal if, for all x,y∈[n], there is a unique pair (i,j) such that L(i,j) = x and L'(i,j) = y; k Latin squares are mutually orthogonal if any two of them are orthogonal. After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will present an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds. This talk is based on joint work with Shagnik Das and Tibor Szabó.

### Emo Welzl (ETH Zürich): Connectivity of Triangulation Flip Graphs in the Plane

In a straight line embedded triangulation of a point set P in the plane, removing an inner edge and - provided the resulting quadrilateral Q is convex - adding the other diagonal is called an edge flip. The flip graph has all triangulations as vertices and a pair of triangulations is adjacent, if they can be obtained from each other by an edge flip. This presentation is towards a better understanding of this graph, with emphasis on its connectivity. It is known that every triangulation allows at least n/2-2 edge flips and we show (n/2-2)-vertex connectivity for flip graphs of all P in general position, n:=|P|. Somewhat stronger, but restricted to P large enough, we show that the vertex connectivity is determined by the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P. A corresponding result is shown for so-called partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. Here the flip operation is extended to bistellar flips (edge flip, and insertion and removal of an inner vertex of degree three). We prove (n-3)-edge connectedness for all P in general position and (n-3)-vertex connectedness for n large enough ((n-3) is tight, since there is always a partial triangulation which allows exactly n-3 bistellar flips). This matches the situation known (through the secondary polytope) for regular triangulations (i.e. partial triangulations obtained by lifting the points and projecting the lower convex hull). This is joint work with Uli Wagner, IST Austria.

### Matthias Beck (San Francisco State University): Lonely Runner Polyhedra

We study the Lonely Runner Conjecture, conceived by Wills in the 1960's: Given positive integers n_1, n_2, ..., n_k, there exists a positive real number t such that for all 1 ≤ j ≤ k the distance of tn_j to the nearest integer is at least 1/(k+1). Continuing a view-obstruction approach by Cusick and recent work by Henze and Malikiosis, our goal is to promote a polyhedral ansatz to the Lonely Runner Conjecture. Our results include geometric proofs of some folklore results that are only implicit in the existing literature, a new family of affirmative instances defined by the parities of the speeds, and geometrically motivated conjectures whose resolution would shed further light on the Lonely Runner Conjecture.

### Außer der Reihe: International Conference on: Network Games, Tropical Geometry, and Quantum Communication

This highly interdisciplinary conference is motivated by challenges arising in the analysis and the algorithmic treatment of next generation networks. Networks already have a close connection to algorithmic game theory, but we are convinced that future research in this area will benefit from additional geometric insights. Quantum communication networks promise notions of secure multi-partite communication. This international conference - bringing together leading experts in their fields - explores topics in network games, tropical geometry and quantum communication and their interrelation. It is part of the Thematic Einstein Semester of the newly installed MATH+ excellence cluster on application-oriented mathematics within the Berlin research landscape.

### Felix Schröder (Technische Universität Berlin): Lower Bounds on the p-centered coloring number

A p-centered coloring is a vertex-coloring of a graph G such that every connected subgraph H of G either receives more than p colors or there is a color that appears exactly once in H. The concept was introduced by Nešetřil and Ossona de Mendez as a local condition for measuring sparsity. We prove lower bounds on the p-centered coloring numbers. For outerplanar graphs, we show that their maximum p-centered coloring number is in Theta(p log p). We have examples of graphs of treewidth k needing (p+k choose k) colors, this matches the upper bound of Pilipczuk and Siebertz. We show that planar graphs may require Omega(p^2 log(p)) colors, while all of them admit a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^19) bound by Pilipczuk and Siebertz.

### William T. Trotter ( Georgia Institute of Technology): Stability Analysis for Posets

Trivially, the maximum chromatic number of a graph on n vertices is n , and the only graph which achieves this value is the complete graph K _ n . It is natural to ask whether this result is "stable", i.e., if n is large, G has n vertices and the chromatic number of G is close to n , must G be close to being a complete graph? It is easy to see that for each c>0, if G has n vertices and chromatic number at least n − c , then it contains a clique whose size is at least n −2 c . We will consider the analogous questions for posets and dimension. Now the discussion will really become interesting.

### Davide Lofano (Technische Universität Berlin): Collapsible vs Contractible

Probably the most studied invariant in Topological Data Analysis is the homology of a space. The usual approach is to triangulate the space and try to reduce it in order to make the computations more feasible. A common reduction technique is that of collapsing. In a collapsing process we perform a sequence of elementary collapses, where at each step we delete a free face and the unique facet containing it. If we are able to reduce a complex to one of its vertices then we say it is collapsible and its homology is trivial. Collapsibility implies that the space is contractible but the converse is not always true, probably the best known example is the Dunce Hat. We are going to explore the difference between these two concepts and look for minimal examples of contractible non collapsible complexes in each dimension and how often they arise.

### Matthew Kahle (Ohio State University): Configuration spaces of hard disks in an infinite strip

This is joint work with Bob MacPherson. We study the configuration space config(n,w) of n non-overlapping disks of unit diameter in an infinite strip of width w. Our main result establishes the rate of growth of the Betti numbers for fixed j and w as n → ∞. We identify three regions in the (j,w) plane exhibiting qualitatively different topological behavior. We describe these regions as (1) a “gas” regime where homology is stable, (2) a “liquid” regime where homology is unstable, and (3) a “solid” regime where homology is trivial. We describe the boundaries between stable, unstable, and trivial homology for every n ≥ 3.

### Fei Xue (Technische Universität Berlin): On the lattice point covering problem in dimension 2

We say that a convex body K has the lattice point covering property, if K contains a lattice point of Z^n in any position, i.e., in any translation and rotation of K. In this talk we discuss the lattice point covering property of some regular polygons in dimension 2.

### Boaz Slomka (Weizmann Institute of Science, Rehovot Israel): On Hadwiger's covering conjecture

A long-standing open problem, known as Hadwiger’s covering problem, asks what is the smallest natural number N(n) such that every convex body in {\mathbb R}^n can be covered by a union of the interiors of at most N(n) of its translates. In this talk, I will discuss some history of this problem and its close relatives, and present more recent results, including a new general upper bound for N(n).

### Tillmann Miltzow (Universität Utrecht): Smoothed Analysis of the Art Gallery Problem

In the Art Gallery Problem we are given a polygon P \subset [0,L]^2 on n vertices and a number k. We want to find a guard set G of size k, such that each point in P is seen by a guard in G. Formally, a guard g sees a point p \in P if the line segment pg is fully contained inside the polygon P. The history and practical findings indicate that irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation. Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude \delta of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an ER-complete problem was analyzed by Smoothed Analysis. This is joint work with Michael Dobbins and Andreas Holmsen.

### Matthias Köppe (University of California): Facets of cut-generating functionology

In the theory of valid inequalities for integer point sets in polyhedra, the traditional, finite-dimensional techniques of polyhedral combinatorics are complemented by infinite-dimensional methods, the study of cut-generating functions. I will give an introduction to these methods and will explain their connection to lattice-free convex bodies. I will present recent results involving inverse semigroups of partial maps, obtained jointly with Robert Hildebrand and Yuan Zhou, and highlight some open questions regarding computability and complexity.

### Torsten Mütze (Technische Universität Berlin): Combinatorial generation via permutation languages

In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an n-element set by adjacent transpositions; the binary reflected Gray code to generate all n-bit strings by flipping a single bit in each step; the Gray code for generating all n-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an n-element ground set by element exchanges due to Kaye. The first main application of our framework are permutation patterns, yielding new Gray codes for different pattern-avoiding permutations, such as vexillary, skew-merged, X-shaped, separable, Baxter and twisted Baxter permutations etc. We also obtain new Gray codes for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into n rectangles subject to different restrictions. The second main application of our framework are lattice congruences of the weak order on the symmetric group S_n. Recently, Pilaud and Santos realized all those lattice congruences as (n-1)-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc. Our algorithm generates each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian. This is joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams.

### Kolja Knauer (Aix-Marseille Université): Tope graphs of (Complexes of) Oriented Matroids

Tope graphs of Complexes of Oriented Matroids fall into the important class of metric graphs called partial cubes. They capture a variety of interesting graphs such as flip graphs of acyclic orientations of a graph, linear extension graphs of a poset, region graphs of hyperplane arrangements to name a few. After a soft introduction into oriented matroids and tope graphs, we give two purely graph theoretical characterizations of tope graphs of Complexes of Oriented Matroids. The first is in terms of a new notion of excluded minors for partial cube, the second is in terms of classical metric properties of certain so-called antipodal subgraphs. Corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we give a polynomial time recognition algorithms for tope graphs, which solves a relatively long standing open question. I will try to furthermore give some perspectives on classical problems as Las Vergnas simplex conjecture in terms of Metric Graph Theory. Based on joint work with H.-J; Bandelt, V. Chepoi, and T. Marc.

### Josué Tonelli-Cueto (Technische Universität Berlin): Condition meets Computational Geometry: The Plantinga-Vegter algorithm case

The Plantinga-Vegter algorithm is a subdivision algorithm that produces an isotopic approximation of implicit smooth curves in the plane (and also of surfaces in the three dimensional space). Despite remarkable practical success of the algorithm, little was known about its complexity. The only existing complexity analysis due to Burr, Gao and Tsigaridas provides worst-case bounds that are exponential both in the degree and the bit size of the input polynomial. Despite being tight, this worst-case bound doesn't explain why the algorithm is efficient in practice. In this talk, we show how condition numbers, combined with techniques from geometric functional analysis, help to solve this issue. This is joint work with Alperen A. Ergür and Felipe Cucker.

### Kaie Kubjas (Sorbonne Université Paris): Nonnegative rank four boundaries

Matrices of nonnegative rank at most r form a semialgebraic set. This semialgebraic set is understood for r=1,2,3. In this talk, I will recall what was previously known about this semialgebraic set and present recent results on the boundaries of the set of matrices of nonnegative rank at most four using notions from the rigidity theory of frameworks. These results are joint work with Robert Krone. In the nonnegative rank three case, all boundaries are trivial or consist of matrices that have only infinitesimally rigid factorizations. For arbitrary nonnegative rank, we give a necessary condition on zero entries of a nonnegative factorization for the factorization to be infinitesimally rigid, and we show that in the case of 5×5 matrices of nonnegative rank four, there exists an infinitesimally rigid realization for every zero pattern that satisfies this necessary condition. However, the nonnegative rank four case is much more complicated than the nonnegative rank three case, and there exist matrices on the boundary that have factorizations that are not infinitesimally rigid. We discuss two such examples.

### Matías Bender (Sorbonne Université Paris): Solving sparse polynomial systems using Gröbner basis

Solving systems of polynomial equations is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, computer vision, molecular biology and kinematics involve polynomial systems that are sparse that is, only a few monomials have non-zero coefficients. We focus on exploiting the sparsity of the Newton polytopes of the polynomials to solve the systems faster than the worst case estimates. In this talk, I will present a Gröbner basis approach to solve sparse 0-dimensional systems whose input polynomials have different Newton polytopes. Under regularity assumptions, we can have an explicit combinatorial bound for the complexity of the algorithm. This is joint work with Jean-Charles Faugère and Elias Tsigaridas.

### Sergio Cabello (Universität Ljubljana): Computational geometry, optimization and Shapley values

I will discuss three unrelated sets of results combining geometry and algorithms. First we will see classes of graphs defined using the intersection of geometric objects in the plane, and discuss classical optimization problems for them. Then we will consider approximation algorithms for the potato peeling problem: find a maximum-area convex body inside a given polygon. The problem amounts to finding a maximum clique in the visibility graph of random samples of points inside the polygon, and results from stochastic geometry are used to bound the size of the samples. Finally, we will discuss the efficient computation of Shapley values for coalitional games defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box.

### Patrick Morris (Freie Universität Berlin): Clique tilings in randomly perturbed graphs

A major theme in both extremal and probabilistic combinatorics is to find the appearance thresholds for certain spanning structures. Classical examples of such spanning structures include perfect matchings, Hamilton cycles and H -tilings, where we look for vertex disjoint copies of H covering all the vertices of some host graph G . In this talk we will focus on H -tilings in the case that H is a clique, a natural generalisation of a perfect matching. On the one hand there is the extremal question, how large does the minimum degree of an n -vertex graph G have to be to guarantee the existence of a clique factor in G ? On the other hand, there is the probabilistic question. How large does p need to be to almost surely ensure the appearance of a clique factor in the Erdős-Rényi random graph G ( n , p )? Optimal answers to these questions were given in two famous papers. The extremal question was answered by Hajnal and Szemerédi in 1970 and the probabilistic question by Johansson, Kahn and Vu in 2008. In this talk we bridge the gap between these two results by approaching the following question which contains the previous questions as special cases. Given an arbitrary graph of some fixed minimum degree, how many random edges need to be added on the same set of vertices to ensure the existence of a clique tiling? We give optimal answers to this question in all cases. Such results are part of a recent research trend studying properties of what is known as the randomly perturbed graph model, introduced by Bohman, Frieze and Martin in 2003. This is joint work with Jie Han and Andrew Treglown.

### Karim Adiprasito (Hebrew University of Jerusalem): Triangulated manifolds, Lefschetz conjectures and the revenge of marriages

Stanley gave us necessary conditions that f-vectors of simplicial polytopes must satisfy by relating the problem to the hard Lefschetz theorem in algebraic geometry, an insurmountably deep and intimidating theorem in algebraic geometry. McMullen conjectured that these conditions are necessary in general, posing before us the problem of proving the hard Lefschetz theorem beyond what algebraic geometers would dream of. I will talk about the revenge of combinatorics, and in particular discuss how Hall's marriage theorem (or rather, one of its proofs) provides a way to this deep algebraic conjecture. Based on arxiv:1812.10454

### Fei Xue (Technische Universität Berlin): On successive minima-type inequalities for the polar of a convex body

The second theorem of Minkowski on successive minima provides optimal upper and lower bounds on the volume of a symmetric convex body in terms of its successive minima. Motivated by conjectures of Mahler and Makai Jr., we study bounds on the volume of a convex body in terms of the successive minima of its polar body. In this talk, we will show the lower bound in the planar case, and the upper bound in the general case. This talk is based on joint work with Martin Henk.

### Peter Gritzmann (Technische Universität München): On dynamic discrete tomography: Constrained flow and multi assignment problemsfor plasma particle tracking

The talk deals with the problem of reconstructing the paths of a set of points over time, where, at each of a finite set of moments in time the current positions of the points in space are only accessible through a small number of their line X-rays. Such problems originate from the demand of particle tracking in plasma physics and can be viewed as constrained version of min-cost-flow and multi assignment problems. (Joint work with A. Alpers)

### Torsten Mütze (Technische Universität Berlin): On symmetric chains and Hamilton cycles

The n -cube is the poset obtained by ordering all subsets of {1,2,..., n } by inclusion. A symmetric chain is a sequence of subsets A k ⊆ A k +1 ⊆…⊆ A n-k with | A i |= i for all i=k ,…, n-k , and a symmetric chain decomposition, or SCD for short, of the n -cube is a partition of all its elements into symmetric chains. There are several known descriptions of SCDs in the n -cube for any n ≥1, going back to works by De Bruijn, Aigner, Kleitman and several others. All those constructions, however, yield the very same SCD. In this talk I will present several new constructions of SCDs in the n -cube. Specifically, we construct five pairwise edge-disjoint SCDs in the n -cube for all n ≥90, and four pairwise orthogonal SCDs for all n ≥60, where orthogonality is a slightly stronger requirement than edge-disjointness. Specifically, two SCDs are called orthogonal if any two chains intersect in at most a single element, except the two longest chains, which may only intersect in the unique minimal and maximal element (the empty set and the full set). This improves the previous best lower bound of three orthogonal SCDs due to Spink, and is another step towards an old problem of Shearer and Kleitman from the 1970s, who conjectured that the n -cube has ⌊ n /2⌋+1 pairwise orthogonal SCDs. We also use our constructions to prove some new results on the central levels problem, a far-ranging generalization of the well-known middle two levels conjecture (now theorem), on Hamilton cycles in subgraphs of the (2 n +1)-cube induced by an even number of levels around the middle. Specifically, we prove that there is a Hamilton cycle through the middle four levels of the (2 n +1)-cube, and a cycle factor through any even number of levels around the middle of the (2 n +1)-cube. This talk is based on two papers, jointly with Sven Jäger, Petr Gregor, Joe Sawada, and Kaja Wille (ICALP 2018), and with Karl Däubel, Sven Jäger, and Manfred Scheucher, respectively.

### Maria Bras Amorós (Universitat Rovira i Virgili Tarragona): On numerical semigroups

A numerical semigroup is a subset of the positive integers ( N ) together with 0, closed under addition, and with a finite complement in N ∪{0}. The number of gaps is its genus. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus g , denoted ( n g ) g ≥ 0 , has a Fibonacci-like asymptotic behavior. It is still not proved that, for each g , n g +2 ≥ n g +1 + n g or, even more simple, n g +1 ≥ n g . We will explain some classical problems on numerical semigroups as well as some of their applications to other fields and we will explain the approach of counting semigroups by means of trees.

### Carlos Amendola (Technische Universität München): Max-Linear Graphical Models via Tropical Geometry

Motivated by extreme value theory, max-linear graphical models have been recently introduced and studied as an alternative to the classical Gaussian or discrete distributions used in graphical modeling. We present max-linear models naturally in the framework of tropical geometry. This perspective allows us to shed light on some known results and to prove others with algebraic techniques. In particular, we rephrase parameter estimation for max-linear models in terms of cones in the tropical eigenspace fan. This is joint work with Claudia Klüppelberg, Steffen Lauritzen and Ngoc Tran.

### Penny Haxell (University of Waterloo): Algorithms for independent transversals vs. small dominating sets

An independent transversal (IT) in a vertex-partitioned graph G is an independent set in G consisting of one vertex in each partition class. There are several known criteria that guarantee the existence of an IT, of the following general form: the graph G has an IT unless the subgraph GS of G, induced by the union of some subset S of vertex classes, has a small dominating set. These criteria have been used over the years to solve many combinatorial problems. The known proofs of these IT theorems do not give efficient algorithms for actually finding an IT or a subset S of classes such that GS has a small dominating set. Here we present appropriate weakenings of such results that do have effective proofs. These result in algorithmic versions of many of the original applications of IT theorems. We will discuss a few of these here, including hitting sets for maximum cliques, circular edge colouring of bridgeless cubic graphs, and hypergraph matching problems.

### Ardalan Khazraei (Bonn): Cost-distance Steiner trees

In the well-known Steiner Tree problem, the objective is to connect a set of terminals at the least total cost. We can further constrain the problem by specifying upper bounds for the distance of each terminal to a chosen root terminal. Further, using the Lagrangianr elaxation of this restriction, we can penalize large distances in the objective function rather than applying strict distance constraints. We arrive at a special case of the so-called Cost-Distance Steiner Tree Problem in which we have a single weight function on the edges. In this talk, I will present several results from my master's thesis that concern the Cost-Distance Steiner Tree Problem. The NP-hardness of the Cost-Distance Steiner Tree Problem trivially follows from the fact that the regular Steiner Tree problem is the special case where we set demand weights (Lagrange multipliers) of the terminals to zero. I therefore proceed to prove that the problem remains NP-hard in three restricted cases that do not contain the regular Steiner Tree Problem as a special case. Then I improve on a previous constant-factor approximation for the single-weighted case by using a hybrid method of an approximate Steiner tree with a shortest-path tree replacing sections of the tree where path segments are used by many terminals with demand weights summing to higher than a tunable threshold. I also use a similar approach to extend Arora's dynamic-programming method for the two-dimensional geometric Steiner Tree Problem to the case with the penalizing terms in the objective function.

### Péter Pál Pach (Budapest University of Technology and Economics): The polynomial method and the cap set problem

In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z 4 n (Croot, Lev and myself) and Z 3 n (Ellenberg and Gijswijt) are exponentially small (compared to the size of the group). We will discuss lower and upper bounds for the size of the extremal subsets, including some recent bounds found by Elsholtz and myself. We will also mention some further applications of the method, for instance, the solution of the Erd ő s-Szemerédi sunflower conjecture.

### Marie Brandenburg (Freie Universität Berlin): Product-Mix Auctions, Competitive Equilibrium and Lattice Polytopes

In 2007, when the credit crisis began, the Bank of England approached the economist Paul Klemperer with the need of a new auction design that would enable them to give liquidity to all banks in an economically efficient way. Since then, Klemperer’s Product-Mix Auction design became more and more relevant, with particular interest in when competitive equilibrium exists, that is, when a set of (indivisible) goods can be split such that exactly one bid of each bidder is fulfilled. Originally being a question of economics, this can be translated into a question of specific lattice polytopes that rely on underlying graphs. I will present the Product-Mix Auction setting, the translation to polytopes and first results on when competitive equilibrium exists.

### Shagnik Das (Freie Universität Berlin): Randomly perturbed Ramsey problems

The combinatorial properties much-loved Erdős-Rényi random graph G ( n , p ), which has n vertices and whose edges are present independently with probability p , have been comprehensively studied in the decades since its introduction. In recent years, much research has been devoted to the randomly perturbed graph model, introduced in 2003 by Bohman, Frieze and Martin. In this talk we shall present and motivate this new model of random graphs, and then focus on the Ramsey properties of these randomly perturbed graphs. More precisely, given a pair of graphs ( F , H ), we ask how many random edges must be added to a dense graph G to ensure that any two-colouring of the edges of the perturbed graph has either a red copy of F or a blue copy of G . This question was first studied in 2006 by Krivelevich, Sudakov and Tetali, who answered it in the case of F being a triangle and H being a clique. We generalise these results, considering pairs of larger cliques, and, should the audience be willing (but even otherwise), shall take a quick look at some of the ideas required in our proofs. This is joint work with Andrew Treglown (Birmingham).

### Ander Lamaison (Freie Universität Berlin): Ramsey density of infinite paths

In a two-colouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+sqrt(8))/17=0.87226…, and constructing a two-colouring in which no denser path exists. This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang.

### Marijn Heule (University of Texas, Austin): Everything's Bigger in Texas: "The Largest Math Proof Ever"

Progress in satisfiability (SAT) solving has enabled answering long-standing open questions in mathematics completely automatically resulting in clever though potentially gigantic proofs. We illustrate the success of this approach by presenting the solution of the Boolean Pythagorean triples problem. We also produced and validated a proof of the solution, which has been called the ``largest math proof ever''. The enormous size of the proof is not important. In fact a shorter proof would have been preferable. However, the size shows that automated tools combined with super computing facilitate solving bigger problems. Moreover, the proof of 200 terabytes can now be validated using highly trustworthy systems, demonstrating that we can check the correctness of proofs no matter their size.

### Petr Gregor (Charles University, Prague): Incidence colorings of subquartic graphs and Cartesian products

Two incidences (u,e) and (v,f) of vertices u, v and edges e, f (respectively) are adjacent if u=v, or e=f, or uv is one of edges e, f. An incidence coloring of a graph G is a coloring of its incidences such that adjacent incidences have distinct colors. We show that every graph of maximal degree 4 has an incidence coloring with 7 colors. Furthermore, we present sufficient conditions for Cartesian product graphs to have incidence colorings with Delta+2 colors where Delta is the maximal degree. In particular, we confirm a conjecture of Pai et al. on incidence colorings of hypercubes. Joint work with B. Lužar and R. Soták.

### László Kozma (Freie Universität Berlin): Self-adjusting data structures: trees and heaps

Binary search trees (BSTs) and heaps are perhaps the simplest implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about them remain open. What is the best strategy for updating a BST in response to queries? Is there a single strategy that is optimal for every possible scenario? Are self-adjusting trees ("splay trees", Sleator, Tarjan, 1983) optimal? In which cases can we improve upon the logarithmic worst-case cost per operation? Our understanding of heaps is even more limited. Fibonacci heaps (and their relatives) are theoretically optimal in a worst-case sense, but they perform operations outside the "pure" comparison-based heap model (in addition to being complicated in practice). Is there a simple, "self-adjusting" alternative to Fibonacci heaps? Is there, by analogy to BSTs, a heap that can adapt to regularities in the input? Are the two problems related? In my talk I will present some old and new results pertaining to this family of questions.

### Sebastian Siebertz (Humboldt-Universität zu Berlin): First-order interpretations of sparse graph classes

The notions of bounded expansion and nowhere denseness capture uniform sparseness of graph classes and render various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce structurally bounded expansion and structurally nowhere dense graph classes, dfined as first-order interpretations of bounded expansion and nowhere dense graph classes. As a first step towards their algorithmic treatment, we provide a characterization of structurally bounded expansion classes via low shrubdepth decompositions, a dense analogue of low treedepth decompositions. We prove that structurally nowhere dense graph classes are vc-minimal.

Location: Humboldt-Universität zu Berlin Institut für Informatik Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

### Marcin Pilipczuk (University of Warsaw): The square root phenomenon: subexponential algorithms in sparse graph classes

While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches.

### Jean-Philippe Labbé (Freie Universität Berlin): (At least) three hard problems behind the multiassociahedron

The associahedron has a natural extension called the multiassociahedron. It is a vertex-decomposable simplicial sphere (in other words, a "combinatorially nice" sphere). Since at least 2003, people tried to construct simplicial polytopes, whose boundary is this simplicial complex, with limited success. In this talk, I will reveal (at least) three combinatorial "known-to-be-challenging" computational problems which should be indispensably faced to solve this problem.

### Jörg Rambau (Universität Bayreuth): Optimal Diplomacy

Picture yourself in a committee numerically evaluating a scientific proposal that you find worth funding: A rating of "0" means "easily achievable but not at all innovative", whereas "1" means "very innovative but totally unachievable". In both cases, funding is not recommended. In contrast, "1/2" means "innovative and achievable", in other words: worth funding. All intermediate values are possible. Any rating that is closer to "1/2" than to "1/4" and "3/4" is considered a vote for funding. The proposal passes if 50% of the members support funding, i.e., rate the proposal between "1/2 - 1/8" and "1/2 + 1/8". Now, there are 10 meetings ahead of you. You have an idea how the opinions of the committee members develop. How should your statements look like in the meetings one through ten if you want to have eventually as many supporters of the proposal as possible? This is an instance of the "Optimal Diplomacy Problem" (ODP), introduced by Hegselmann, König, Kurz, Niemann, and Rambau in 2010, published in 2015. How do opinions interact? How is the dynamics of opinions modeled mathematically? What does it mean to "influence others" in this dynamical system? How difficult is it to find optimal diplomacies? How can one compute or at least narrow down optimal diplomacies? What happens if not all informations about committee members are known to the diplomat? In this talk we will discuss our findings, techniques, and open questions based on the arguably most influential model: the Bounded-Confidence model by Hegselmann and Krause. We draw on joint work with Andreas Deuerling, Rainer Hegselmann, Stefan König, Julia Kinkel, Sascha Kurz, and Christoph Niemann.

### Till Fluschnik (Technische Universität Berlin): Fractals for Kernelization Lower Bounds

Kernelization is a key concept in fixed-parameter algorithmics for polynomial-time preprocessing of NP-hard problems. Herein one seeks to preprocess any instance of a parameterized problem with parameter k to an “equivalent” instance (the so-called (problem) kernel) with size upper-bounded by some function (preferably by some polynomial) in k. Ten years ago, with the development of the so-called composition technique, first NP-hard parameterized problems were proven to presumably admit no polynomial-size problem kernel. Since then the line of Research concerning "limits of kernelization" received a lot of attention. We contribute to this line and present a new technique exploiting triangle-based fractal structures (so called T-fractals) for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of graph problems dealing with some sort of cuts, hereby answering an open question stated in 2009. Our T-fractals---due to their fractal structure---admit easy-to-prove useful properties exploitable for constructing compositions. They also apply for planar as well as directed variants of the basic problems and also apply to both edge and vertex-deletion problems. This is joint work with Danny Hermelin, André Nichterlein, and Rolf Niedermeier. (Journal version appeared in SIAM Journal on Discrete Mathematics 2018.)

### Christoph Berkholz (Humboldt-Universität zu Berlin): A comparison of algebraic and semi-algebraic proof systems

In this lecture I will give an introduction to algebraic and semi-algebraic methods for proving the unsatisfiability of systems of real polynomial equations over the Boolean hypercube. The main goal of this talk is to compare the relative strength of these approaches using methods from proof complexity. On the one hand, I will focus on the static semi-algebraic proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, I will discuss polynomial calculus, which is a dynamic algebraic proof system that models Gröbner basis computations. I am going to present two recent results on the relative strength between algebraic and semi-algebraic proof systems:¹ The first result is that sum-of-squares simulates polynomial calculus: any polynomial calculus refutation of degree d can be transformed into a sum-of-squares refutation of degree 2d and only polynomial increase in size. In contrast, the second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equations that have polynomial calculus refutations of degree 3 and polynomial size, but require Sherali-Adams refutations of large degree and exponential size. ¹) this work was presented at STACS 2018; a preprint is available at https://eccc.weizmann.ac.il/report/2017/154/

### Alexander van der Grinten (Universität zu Köln): Scalable Katz Ranking Computation

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. We consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. For a certain class of inputs, this yields an optimal algorithm for Katz ranking computation. Furthermore, Experiments demonstrate that our algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Specifically, we provide efficient parallel CPU and GPU implementations of the algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.

Location: Humboldt-Universität zu Berlin Institut für Informatik Room 3.408 (House 3 / 4th Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

### Henning Meyerhenke (Humboldt-Universität zu Berlin): Algorithms for Large-scale Network Analysis

Network centrality measures indicate the importance of nodes (or edges) in a network. In this talk we will discuss a few popular measures and algorithms for computing complete or partial node rankings based on these measures. These algorithms are implemented in NetworKit, an open-source framework for large-scale network analysis, on which we provide an overview, too. One focus of the talk will be on techniques for speeding up a greedy (1-1/e)-approximation algorithm for the NP-hard group closeness centrality problem. Compared to a straightforward implementation, our approach is orders of magnitude faster and, compared to a heuristic proposed by Chen et al., we always find a solution with better quality in a comparable running time in our experiments. Our method Greedy++ allows us to approximate the group with maximum closeness centrality on networks with up to hundreds of millions of edges in minutes or at most a few hours. In a comparison with the optimum, our experiments show that the solution found by Greedy++ is actually much better than the theoretical guarantee.

Location: Humboldt-Universität zu Berlin Institut für Informatik Room 3.408 (House 3 / 4th Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

### Jan Goedgebeur (Ghent University): Obstructions for 3-colouring graphs with one forbidden induced subgraph

For several graph classes without long induced paths there exists a finite forbidden subgraph characterization for k-colourability. Such a finite set of minimal obstructions allows to provide a “no-certificate" which proves that a graph is not k-colourable. We prove that there are only finitely many 4-critical P 6 -free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-colouring P 6 -free graphs, which solves an open problem posed by Golovach et al. (Here, P 6 denotes the induced path on six vertices.) Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P 6 . This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand. In this talk we will mainly focus on the algorithmic results by presenting a new algorithm for generating all minimal forbidden subgraphs to k-colourability for given graph classes. This algorithm (combined with new theoretical results) has been successfully applied to fully characterise all forbidden subgraphs for k-colourability for various classes of graphs without long induced paths. (This is joint work with Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong.)

### Akiyoshi Tsuchiya (Osaka University): Polyhedral characterizations of perfect graphs

Perfect graphs are important objects in graph theory. The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. One of the most famous and most important results is the strong perfect graph theorem conjectured by Claude Berge and proved by Chudnovsky, Robertson and Thomas. This theorem characterizes perfect graphs. Our interest is to give other characterizations of perfect graphs. In this talk, we construct several lattice polytopes arising from a finite simple graph and characterize when the graph is perfect in terms of the lattice polytopes. This talk is based on joint work with Takayuki Hibi and Hidefumi Ohsugi.