Facets of Complexity Monday Colloquium

Andrea Jiménez Universidad de Varparaíso, Chile

Groundstates of the Ising Model on antiferromagnetic triangulations

Abstract.

We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovasz and Plummer. The dual version is formulated as follows "Every triangulation of an orientable surface has exponentially many groundstates'', where groundstates are the states at the lowest energy in the antiferromagnetic Ising Model.According to physicists, this dual formulation holds. In this talk, I show a counterexample to the dual formulation, a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and, if time allows, some open problems. This is joint work with Marcos Kiwi and Martin Loebl.

Warut Suksompong National University of Singapore

The Price of Connectivity in Fair Division

Abstract.

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems. Joint work with Xiaohui Bei, Ayumi Igarashi, and Xinhang Lu.

Marcel Celaya ETH, Zürich

Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Abstract.

Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel.

Michaela Borzechowski Freie Universität Berlin

Unique Sink Orientations of Grids is in Unique End of Potential Line

Abstract.

The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. PUEOPL captures search problems where the instances are promised to have a unique solution. UEOPL captures total search versions of these promise problems. The promise problems can be made total by defining violations that are returned as a short certificate of an unfulfilled promise. GridUSO is the problem of finding the sink in a grid with a unique sink orientation. It was introduced by Gärtner et al. in 2008. We describe a promise preserving reduction from GridUSO to UniqueForwardEOPL, a UEOPL-complete problem. Thus, we show that GridUSO is in UEOPL and its promise version is in PUEOPL.

Christian Kipp Technische Universität Berlin

Affine Subspace Concentration Conditions for Polytopes

Abstract.

Given an n-dimensional polytope P and one of its facets F, the cone volume corresponding to F is the volume of conv(0,F). P is said to satisfy the subspace concentration condition w.r.t. a d-dimensional linear subspace L if the total cone volume of the facets with normal vectors in L is at most d/n*vol(P). The subspace concentration condition plays an important role in the context of the (discrete) logarithmic Minkowski problem, i.e., the question: What conditions ensure that a given list of normal vectors and cone volumes can be realized by a polytope? Recently, an affine version of the subspace concentration condition was introduced by Wu for certain lattice polytopes. In this talk, I will focus on the affine case and discuss possible generalizations. This is joint work with Ansgar Freyer and Martin Henk.

Andrei Comăneci Technische Universität Berlin

Tropical Medians by Transportation

Abstract.

The Fermat-Weber problem seeks a point that minimizes the average distance from a given sample. The problem was studied by Lin and Yoshida (2018) using the standard tropical metric with the purpose of analyzing phylogenetic data. In this talk, we argue that using a related asymmetric distance we have better geometric and algorithmic properties. The new formulation is strongly related to tropical convexity and is equivalent to a transportation problem. This gives a geometric perspective to the transportation problem, which was exploited by Tokuyama and Nakano (1995) to obtain efficient algorithms. At the end, we will see an application to computational biology: a new method for computing consensus trees. The talk is based on joint work with Michael Joswig.

Imre Bárány Alfréd Rényi Mathematical Institute of the Hungarian Academy of Science, Budapest

Cells in the box and a hyperplane

Abstract.

It is well known that a line can intersect at most 2n−1 cells of the n×n chessboard. What happens in higher dimensions: how many cells of the d-dimensional [0,n]^d box can a hyperplane intersect? We answer this question asymptotically. We also prove the integer analogue of the following fact. If K,L are convex bodies in R^d and K ⊂ L, then the surface area K is smaller than that of L. This is joint work with Péter Frankl.

Sandro Roch Technische Universität Berlin

Arrangements of Pseudocircles: On Digons and Triangles

Abstract.

A pseudocircle is a simple closed curve in the plane. An intersecting arrangement of pseudocircles is a finite collection of pseudocircles so that any two intersect in exactly two points where they cross. Grünbaum conjectured in the 1970's that in the case of simple arrangements there are at most 2n - 2 digon cells, i.e. cells which have exactly two crossings on its boundary. I will present a result by Agarwal et al. (2004) which proves this conjecture for the special case of cylindrical arrangements. Based on that we show that the conjecture also holds whenever the arrangement contains three pseudocircles which pairwise form a digon cell. Moreover, I will present a result concerning the number of triangles in digon free arrangements, which disproves another conjecture by Grünbaum. (joint with S.Felsner and M.Scheucher)

Marcel Celaya ETH, Zürich

Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Abstract.

Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel.

Jana Novotna University of Warsaw

Taming Creatures

Abstract.

A graph class is tame if it admits a polynomial bound on the number of minimal separators, and feral if it contains infinitely many graphs with exponential number of minimal separators. The former entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set, and many other problems, when restricted to an input graph from a tame class, by a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015]. In the talk, we show a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame and feral. To obtain the full dichotomy, we confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class C there exists a constant k such that no member of C contains a k-creature or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every graph G from C contains at most p(|V(G)|) minimal separators. Joint work with Jakub Gajarský, Lars Jafke, Paloma T. Lima, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza.

Marie Brandenburg Max Planck Institut Leipzig

Intersection Bodies of Polytopes

Abstract.

Intersection bodies are classical objects from convex geometry, that are constructed from given convex body. In the past, they have mainly been studied from the point of view of convex analysis. In this talk we investigate combinatorial and algebraic structures of intersection bodies of polytopes. We consider an algorithm to compute both the radial function and the algebraic boundary of these intersection bodies, and provide an upper bound for their degree. This is joint work with Katalin Berlow, Chiara Meroni and Isabelle Shankar.

Manuel Radons Technische Universität Berlin

Nearly flat polytopes in the context of Dürer's problem

Abstract.

Dürer's problem asks whether every 3-polytope P has a net. Is there always a spanning tree T of its edge graph, so that if we cut P along T the resulting surface can be unfolded into the plane without self-overlaps? A common technique in recent works is to fix a spanning tree and then study the deformations of the corresponding unfolding induced by an affine stretching or flattening of P. In the first part of my talk I will highlight landmark results by Ghomi, O'Rourke and Tarasov that emanated from this approach. In the second part I will present my own work on the unfoldability of nested prismatoids, which follows a similar ansatz.

Klaus Heeger Technische Universität Berlin

Stable Matchings Beyond Stable Marriage

Abstract.

Stable matchings are well-studied from computer science, mathematics, and economics. In the most basic setting, called Stable Marriage, there are two sets of agents. Each agent from one set has preferences over the agents from the other set. A matching assigns the agents into groups of two agents. A matching is called stable if there are no two agents preferring each other to the partners assigned to them. In this talk, we will review important parts of my forthcoming PhD thesis concerning the computational complexity of two extensions of this basic model: First, we assume that an instance of Stable Marriage is given, and the aim is to modify the instance (using as few "modifications" as possible) such that a given edge is part of some stable matching. Second, we assume that agents have preferences over sets of d-1 other agents (for some d>2). In this case, a matching matches agents into groups of size d, and a matching is stable if there are no d agents preferring to be matched together to being unmatched. While since 1991 this problem is known to be NP-complete, we study the case that the preferences of all agents are "similar".

Ji Hoon Chun Technische Universität Berlin

The Sausage Catastrophe in dimension 4

Abstract.

The Sausage Catastrophe (Jörg Wills) is the observation that in d = 3 and d = 4, the densest packing of n spheres is a sausage for small n and jumps to a full-dimensional packing for large n without passing through any intermediate dimensions. We denote the smallest value of n for which the densest packing is full-dimensional by k_d. We discuss some upper and lower bounds for k_3 and k_4, including k_3 ≤ 56 by Wills (1985) and k_4 < 375,769 by Gandini and Zucco (1992). We present some initial improvements to the upper bound for k_4 via extending the work of Gandini and Zucco.

Markus Schmid Humboldt-Universität zu Berlin

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

Abstract.

We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio O(\sqrt{log(opt)} log(n))$. An important aspect of our work --- that is relevant in its own right and of independent interest --- is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature (with respect to exact, parameterised and approximation algorithms), and are arguably among the most central graph parameters that are based on "linearisations" of graphs. Most importantly, we relate cutwidth with pathwidth via the locality number, which results in an approximation preserving reduction that improves the currently best known approximation algorithm for cutwidth. [This is based on joint work with Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, and Florin Manea, published in Proc. ICALP'19.]

Malte Renken Technische Universität Berlin

Connectivity Thresholds in Random Temporal Graphs

Abstract.

We consider a simple model of a random temporal graph, obtained by assigning to every edge of an Erdős–Rényi random graph G_n,p a uniformly random presence time in the real interval [0, 1]. We study several connectivity properties of this random temporal graph model and uncover a surprisingly regular sequence of sharp thresholds at which these different levels of connectivity are reached. Finally, we discuss how our results can be transferred to other random temporal graph models. Based on joint work with Arnaud Casteigts, Michael Raskin, and Viktor Zamaraev.

Benjamin Berendsohn Freie Universität Berlin

Search trees on graphs

Abstract.

Search trees on graphs (STGs) are a generalization of binary search trees (BSTs). Where the key space of a BST is a totally ordered set, the key space of a STG is a graph. STGs are a relatively recent notion, but have been studied previously under different names, including elimination trees, maximal tubings, and vertex rankings. We survey some results. On the computational side, we consider a model of computation for STGs analagous to the BST model, and study which known results for BSTs can be adapted. On the combinatorial side, we study the diameter of certain polytopes called graph associahedra, which can be defined via STGs.

Jonathan Leake Technische Universität Berlin

Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture

Abstract.

About 5 years ago, the Heron-Rota-Welsh conjecture (log-concavity of the coefficients of the characteristic polynomial of a matroid) was proven by Adiprasito, Huh, and Katz via the exciting development of a new combinatorial Hodge theory for matroids. In very recent work with Petter Brändén, we have given a new short "polynomial proof" of the Heron-Rota-Welsh conjecture. Our proof uses an extension of the theory of Lorentzian polynomials to convex cones. In this talk, I will briefly discuss the basics of Lorentzian (aka completely log-concave) polynomials, and then I will give an overview of our new proof of the Heron-Rota-Welsh conjecture.

Stefan Kuhlmann Technische Universität Berlin

Lattice width of lattice-free polyhedra and height of Hilbert bases

Abstract.

A polyhedron defined by an integral valued constraint matrix and an integral valued right-hand side is lattice-free if it does not contain an element of the integer lattice. In this talk, we present a link between the lattice-freeness of polyhedra, the diameter of finite abelian groups and the height of Hilbert bases. As a result, we will be able to prove novel upper bounds on the lattice width of lattice-free pyramids if a conjecture regarding the height of Hilbert bases holds. Further, we improve existing lattice width bounds of lattice-free simplices. All our bounds are independent of the dimension and solely depend on the maximal minors of the constraint matrix. The second part of the talk is devoted to a study of the above-mentioned conjecture. We completely characterize the Hilbert basis of a pointed polyhedral cone when all the maximal minors of the constraint matrix are bounded by two in absolute value. This can be interpreted as an extension of a well-known result which states that the Hilbert basis elements lie on the extreme rays if the constraint matrix is unimodular, i.e., all maximal minors are bounded by one in absolute value. This is joint work with Martin Henk and Robert Weismantel.

Davide Lofano Technische Universität Berlin

Hadamard Matrix Torsion

Abstract.

After a brief overview about torsion in homology and examples of complexes with small torsion and few vertices we will focus our attention on a particular series of examples. In particular, we will construct a series HMT(n) of 2-dimensional simplicial complexes with huge torsion, |H_1(HMT(n))|=|det(H(n))|=n^(n/2), where the construction is based on the Hadamard matrices H(n) and they have linearly many vertices in n. Our explicit series improves a previous construction by Speyer, narrowing the gap to the highest possible asymptotic torsion growth achieved by Newman via a randomized construction.

Letícia Mattos Freie Universität Berlin

Singularity of random symmetric matrices

Abstract.

Let M_n be a uniformly-chosen random symmetric n x n matrix with entries in {-1,1}. What is the probability for det(M_n)=0? A wellknown conjecture states that the probability of this event is asymptotically equal to the probability that two of the rows or columns of M_n are equal (up to a factor of +-1) and hence is equal to \Theta(n^2 2^{-n}). We developed an inverse Littlewood-Offord theorem in Z^n_p that applies under very mild conditions and made progress towards this conjecture, showing that the probability is bounded by exp(-c\sqrt{n}). Joint work with Marcelo Campos, Robert Morris and Natasha Morrison.

Simona Boyadzhiyska Freie Universität Berlin

Ramsey simplicity of random graphs

Abstract.

We say that a graph G is q-Ramsey for another graph H if any q-coloring of the edges of G yields a monochromatic copy of H. Much of the research related to Ramsey graphs is concerned with determining the smallest possible number of vertices in a q-Ramsey graph for a given H, known as the q-color Ramsey number of H. In the 1970s, Burr, Erdős, and Lovász initiated the study of another graph parameter in the context of Ramsey graphs: the minimum degree. A straightforward argument shows that, if G is a minimal q-Ramsey graph for H, then we must have δ(G) >= q(δ(H) - 1) + 1, and we say that H is q-Ramsey simple if this bound can be attained. In this talk, we will ask how typical Ramsey simplicity is; more precisely, we will discuss for which pairs p and q the random graph G(n,p) is almost surely q-Ramsey simple. This is joint work with Dennis Clemens, Shagnik Das, and Pranshu Gupta.

Raphael Steiner Technische Universität Berlin

The dichromatic number-a survey

Abstract.

The dichromatic number of a digraph is the smallest number of acyclic subsets of vertices (not spanning a directed cycle) that can be used to cover its vertex-set. This parameter is a natural extension of the chromatic number to directed graphs and has been introduced in 1980 by Erdös and Neumann-Lara. Since 2000, many groups of authors have studied this parameter intensively and in various settings. In this talk, I will give a small survey of this topic, which has concerned me quite a bit in the last 3-epsilon years. I will also mention own results obtained during my PhD at appropriate places.

Ansgar Freyer Technische Universität Berlin

Shaking a convex body in order to count its lattice points

Abstract.

We prove inequalities on the number of lattice points inside a convex body K in terms of its volume and its successive minima. The successive minima of a convex body have been introduced by Minkowski and since then, they play a major role in the geometry of numbers. A key step in the proof is a technique from convex geometry known as Blascke's shaking procedure by which the problem can be reduced to anti-blocking bodies, i.e., convex bodies that are "located in the corner of the positive orthant". As a corollary of our result, we will obtain an upper bound on the number of lattice points in K in terms of the successive minima, which is equivalent to Minkowski's Second Theorem, giving a partial answer to a conjecture by Betke et al. from 1993. This is a joint work with Eduardo Lucas Marín.

Gorav Jindal Technische Universität Berlin

Arithmetic Circuit Complexity of Division and Truncation

Abstract.

Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). This result is an exponential improvement over Strassen’s classic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)).The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute. We also prove that the truncations of even very simple algebraic functions are hard to compute,unless integer factoring is easy. This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found athttps://eccc.weizmann.ac.il/report/2021/072/ .

Patrick Morris Freie Universität Berlin

Triangle factors in pseudorandom graphs

Abstract.

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szab ́o (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set. In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.

Davide Lofano Technische Universität Berlin

Random Simple-Homotopy Theory

Abstract.

A standard task in topology is to simplify a given finite presentation ofa topological space. Bistellar flips allow to search for vertex-minimaltriangulations of surfaces or higher-dimensional manifolds, and elementarycollapses are often used to reduce a simplicial complex in size andpotentially in dimension. Simple-homotopy theory, as introduced byWhitehead in 1939, generalizes both concepts.We take on a random approach to simple-homotopy theory and present aheuristic algorithm to combinatorially deform non-collapsible, butcontractible complexes (such as triangulations of the dunce hat, Bing'shouse or non-collapsible balls that contain short knots) to a point.The procedure also allows to find substructures in complexes, e.g.,surfaces in higher-dimensional manifolds or subcomplexes with torsion inlens spaces.(Joint work with Bruno Benedetti, Crystal Lai, and Frank Lutz.)

Aniket Shah Ohio State University

A q-analogue of Brion's identity

Abstract.

Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0.

Matthieu Rosenfeld LIRMM

Bounding the number of sets defined by a given MSO formula on trees

Abstract.

Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets, or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order n is at most 95^(n/13) and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second-order formula.I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain how to generalize this into a more general technique. I will end my talk by mentioning a few of the results obtained with this technique.

Joanna Lada Merton College Oxford

On colour-bias Hamilton cycles in dense graphs

Pavle Blagojević Freie Universität Berlin

Ten years in one lecture

Abstract.

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.

Maria Dostert Royal Institute of Technology

Exact semidefinite programming bounds for packing problems

Abstract.

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 E8 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.

Alp Müyesser

Rainbow factors and trees

Abstract.

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.

Jannik Peters

Efficiency and Stability in Euclidean Network Design

Abstract.

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.

Dante Luber

Boundary Complexes for Moduli Spaces of Curves

Abstract.

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.

Filippos Christodoulou

Design and Analysis of Combinatorial Problems in Random Intersection Graphs

Kemal Rose

Tillmann Miltzow Utrecht University

A practical algorithm with performance guarantees for the art-gallery problem

Abstract.

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.

José Samper Max Planck Institut Leipzig

Dual matroid polytopes and the independence complex of a matroid

Abstract.

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.

Yanitsa Pehova University of Warwick

Characterisation of quasirandom permutations by a pattern sum

Abstract.

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 σ∈S4. We further weaken this condition by exhibiting sets S⊆S4, 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.

Sándor Kisfaludi-Bak Max Planck Institut Saarbrücken

Separators and exact algorithms for geometric intersection graphs

Abstract.

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

Abstract.

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

Abstract.

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.

Gorav Jindal Aalto University, Helsinki

On the Complexity of Symmetric Polynomials

Abstract.

The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_Sym in C[x1,x2,...,xn], there exists a unique "witness" f in C[y1,y2,...,yn] such that f_Sym=f(e1,e2,...,en), 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

Abstract.

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.

Shahrzad Haddadan MPI Saarbrücken

Algorithms for top-k Lists and Social Networks

Abstract.

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.

Andrei Asinowski Universität Klagenfurt

Vectorial kernel method and patterns in lattice paths

Abstract.

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.)

Lukas Kühne Hebrew University of Jerusalem

Matroid representations by c-arrangements are undecidable

Abstract.

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.

Alexander Heaton Max Planck Institut Leipzig

Applications of algebra to the geometry of materials

Abstract.

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.

Marcel Celaya Georgia Institute of Technology

The linear span of lattice points in a half-open lattice parallelepiped

Abstract.

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.

Manfred Scheucher Techniche Universität Berlin

Topological Drawings meet SAT Solvers and Classical Theorems of Convex Geometry

Abstract.

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.

Ansgar Freyer Technische Universität Berlin

Discrete analogs of an inequality by Meyer

Abstract.

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.

Raphael Steiner Technische Universität Berlin

Majority Colorings of Sparse Digraphs

Abstract.

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ó.

Liana Yepremyan University of Oxford

On the size Ramsey number of bounded powers of bounded degree trees

Abstract.

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.

Benjamin Hauskeller Humboldt-Universität zu Berlin

Dynamic Query Evaluation with Sublinear Update Time

Abstract.

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.

Manfred Scheucher Technische Universität Berlin

On Arrangements of Pseudocircles

Abstract.

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)

Simona Boyadzhiyska Freie Universität Berlin

On counting problems related to (mutually) orthogonal Latin squares

Abstract.

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ó.

Felix Schröder Technische Universität Berlin

Lower Bounds on the p-centered coloring number

Abstract.

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.

Davide Lofano Technische Universität Berlin

Collapsible vs Contractible

Abstract.

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.

Fei Xue Technische Universität Berlin

On the lattice point covering problem in dimension 2

Abstract.

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.

Tillmann Miltzow Universität Utrecht

Smoothed Analysis of the Art Gallery Problem

Abstract.

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 bitsto 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 isthe 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.

Torsten Mütze Technische Universität Berlin

Combinatorial generation via permutation languages

Abstract.

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.

Josué Tonelli-Cueto Technische Universität Berlin

Condition meets Computational Geometry: The Plantinga-Vegter algorithm case

Abstract.

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.

Matías Bender Sorbonne Université Paris

Solving sparse polynomial systems using Gröbner basis

Abstract.

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.

Patrick Morris Freie Universität Berlin

Clique tilings in randomly perturbed graphs

Abstract.

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.

Fei Xue Technische Universität Berlin

On successive minima-type inequalities for the polar of a convex body

Abstract.

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.

Torsten Mütze Technische Universität Berlin

On symmetric chains and Hamilton cycles

Abstract.

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 Ak⊆Ak+1⊆…⊆An-k with |Ai|=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 (2n+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 (2n+1)-cube, and a cycle factor through any even number of levels around the middle of the (2n+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.

Carlos Amendola Technische Universität München

Max-Linear Graphical Models via Tropical Geometry

Abstract.

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.

Ardalan Khazraei Bonn

Cost-distance Steiner trees

Abstract.

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.

Marie Brandenburg Freie Universität Berlin

Product-Mix Auctions, Competitive Equilibrium and Lattice Polytopes

Abstract.

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.

Ander Lamaison Freie Universität Berlin

Ramsey density of infinite paths

Abstract.

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.

Petr Gregor Charles University, Prague

Incidence colorings of subquartic graphs and Cartesian products

Abstract.

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.

Sebastian Siebertz Humboldt-Universität zu Berlin

First-order interpretations of sparse graph classes

Abstract.

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.

Jean-Philippe Labbé Freie Universität Berlin

(At least) three hard problems behind the multiassociahedron

Abstract.

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.

Till Fluschnik Technische Universität Berlin

Fractals for Kernelization Lower Bounds

Abstract.

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.)

Alexander van der Grinten Universität zu Köln

Scalable Katz Ranking Computation

Abstract.

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.

Jan Goedgebeur Ghent University

Obstructions for 3-colouring graphs with one forbidden induced subgraph

Abstract.

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 P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-colouring P6-free graphs, which solves an open problem posed by Golovach et al. (Here, P6 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 P6. 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

Abstract.

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.

Facets of Complexity Monday Colloquium 📅