The talks are usually on Mondays at 2:00pm in the Coffee room (MA B1 524), but do check the individual announcements.
2018/2019
June 4, 2019 (Tuesday) at 14:00, Dömötör Pálvölgyi (Eötvös University, Budapest)
“News about the chromatic number of the plane”
At least how many colors do we need to color all the points of the plane such that every pair of points at unit distance receive different colors? This question is known as the Hadwiger-Nelson problem and until one year ago it was only known that 4 colors are needed and 7 are enough. Then in April 2018 gerontologist de Grey showed in a breakthrough result that 4 colors are not enough. His proof was computer assisted, and a collaborative Polymath project was started to find a human-verifiable proof. I will give a short introduction to the classical results, then talk about the current ongoing research with plenty of open problems.
May 1, 2019 (Wednesday) at 13:00, Nóra Frankl (LSE)
“Nearly k-distance sets”
A set in Rd is a k-distance set if it determines at most k distances. Determining the largest cardinality mk(d) of a k-distance set is a famous and hard problem. We study an approximate version: We call a set S an ε-nearly k distance set if the distance between any two of its points is at least one and there are real numbers t1<t2<…<tk such that every distance determined by S falls in the ε-neighbourhood of some ti. We denote by Mk(d) the largest N, such that for any ε>0, there is an ε-nearly k-distance set in Rd. It turns out that for fixed k and large d, Mk(d) behaves similarly to mk(d), but Mk(d) is much greater than mk(d) for fixed d and large k. In particular we prove that mk(d)=Mk(d) if k≤3, or d is sufficiently large compared to k, and Mk(d)=Θ(kd). As a related problem, we study the maximum number of distances Mk(d,n) determined by n points in Rd that can fall in the union of k given unit intervals of length one . For k=1, d=2 this question was introduced by Erdős in the 80’s and since then generalisations have been studied by Erdős, Makai, Pach and Spencer. Among proving other bounds, we determine the value of Mk(d,n) asymptotically for fixed k and d with d>d(k).
April 16, 2019 (Tuesday) at 17:15, Gábor Tardos (Rényi Institute, Budapest)
“Generalizing the Erdos-Stone-Simonovits theorem for (vertex and) edge ordered graphs”
Turan-type extremal graph theory asks for the maximal number of edges in an n vertex simple graph avoiding a fixed forbidden subgraph. By adding a linear order on either the vertices or the edges of the graphs considered we can extend the theory by forbidding a subgraph in a given order. This yields extremal theories of vertex ordered and edge ordered graphs.
The most general result in the Turan-type extremal graph theory is the Erdos-Stone-Simonovits theorem connecting the asymptotic behavior of the extremal function of a graph to its chromatic number. With Janos Pach we generalized this result to vertex ordered graphs and with Daniel Gerbner, Abhishek Methuku, Daniel Nagy, Domotor Palvolgyi and Mate Vizer we managed to find the generalization to edge ordered graphs. For vertex ordered graphs the relevant parameter is the interval chromatic number, a notion much simpler than the standard chromatic number. For edge ordered graphs the corresponding parameter is the order chromatic number, a curious and interesting parameter that behaves in surprising ways.
March 6, 2019 (Wednesday) at 14:00, Márton Naszódi (EPFL)
“Approximate Carathéodory theorems for matrices”
John’s theorem states that if the Euclidean unit ball is the largest volume ellipsoid in a convex body K in Rd, then there is a set of unit vectors u1,…,um on the boundary of K such that the identity operator I on Rd is a positive linear combination of the diads ui ⊗ ui. With interesting geometric applications, it is natural to ask whether I can be approximated by a positive linear combination of only a few of these diads. Our main interest is whether such approximation results extend from diads to larger classes of matrices.
Joint work with Grigory Ivanov and Alexandr Polyanskii.
February 26, 2019 (Tuesday) at 11:15, Seffi Naor (Technion)
“Online Algorithms via Projections”
We consider the k-server problem on trees and HSTs and give an online algorithm based on Bregman projections. This algorithm has a competitive ratio that matches some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-descent-based continuous dynamics prescribed via a differential inclusion. We discuss the connections between this work and previous work on online primal-dual algorithms for several problems.
Joint work with Niv Buchbinder, Anupam Gupta, and Marco Molinaro.
February 11, 2019 (Monday) at 16:00, Zsolt Lángi (Budapest University of Technology and Economics)
“The isoperimetric ratio decreases in the Eikonal abrasion model”
A few years ago the strange elongated shape of the interstellar asteroid ‘Oumuamua raised a significant interest both in the scientific and public community. A possible explanation for this phenomenon was given by Domokos et al., who, using their already existing model for the abrasion of asteroids, pointed out that in this model shapes become more and more aspherical. To establish the mathematical background of this statement and motivated by a question of Lovasz, in this talk we verify this statement from mathematical point of view, and show that the isoperimetric ratio decreases in the Eikonal abrasion model. The proof relies entirely on tools from convex geometry. In addition, we advertise a recently announced prize for determining the minimum total number of faces of a convex polyhedron of homogeneous density, having only one stable and one unstable equilibrium point with respect to its center of mass.
January 15, 2019 (Tuesday) at 14:00, Amin Karbasi (Yale)
“Relax: A Non-Convex Road for Solving Structured Combinatorial Problems”
The difficulty of searching through a massive amount of data in order to quickly make an informed decision is one of today’s most ubiquitous challenges. Many scientific and engineering models feature inherently discrete decision variables—from phrases in a corpus to objects in an image. The study of how to make near-optimal decisions from a massive pool of possibilities is at the heart of combinatorial optimization. Many of these problems are notoriously hard, and even those that are theoretically tractable may not scale to large instances. However, the problems of practical interest are often much more well-behaved and possess extra structures that allow them to be amenable to exact or approximate optimization techniques. Just as convexity has been a celebrated and well-studied condition under which continuous optimization is tractable, submodularity is a condition for which discrete objectives may be optimized.
In order to provide the tightest approximation guarantees for submodular optimization problems, we usually need to leave the space of discrete domains and consider their continuous relaxations. To this end, we will explore the notion of submodularity in the continuous domains and introduce a broad class of non-convex objective functions. Despite the apparent lack of convexity, we will see that first-order optimization methods can provide strong approximation guarantees. We then show that such continuous relaxations can be used as an interface to provide tight approximation guarantees for maximizing stochastic submodular set functions.
I will not assume any particular background on submodularity or optimization and will try to motivate and define all the necessary concepts during the talk.
December 17, 2018 (Monday) at 14:00, Konrad Swanepoel (LSE)
“Ordinary hyperplanes and hyperspheres”
Let S be a set of n points in real d-dimensional space such that any d of the points span a hyperplane. We say that a hyperplane is ordinary if it intersects exactly d+1 points of S. We show that for n sufficiently large depending on d, if S has only O(nd-1) ordinary hyperplanes, then all but O(1) points of S lie on a hyperplane or an elliptic normal curve or an acnodal rational normal curve. As a consequence, we determine the minimum number of ordinary lines for all sufficiently large n, thus proving a conjecture of Ball and Monserrat. This work generalizes results of Ball (d=3) and of Green and Tao (d=2). We have analogous results for ordinary hyperspheres, which generalize work of Lin, Makhul, Nassajian Mojarrad, Schicho, Swanepoel and De Zeeuw on ordinary circles. This is joint work with Aaron Lin.
December 10, 2018 (Monday) at 14:00, Nabil Mustafa (ESIEE Paris)
“Optimality of Geometric Local Search”
For many basic geometric combinatorial problems such as independent-set, dominating set and set-cover on disks, it is known that local-search with radius k gives a (1+1/√k)-approximation algorithm. In this talk, we show that the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient, of independent interest, is a new lower bound on locally expanding planar graphs. Our construction extends to other graph families with small separators.
December 3, 2018 (Monday) at 14:00, Andrew Suk (UCSD)
“Multicolor Ramsey numbers for semi-algebraic graphs”
The Ramsey number R(p; m) is the smallest integer n such that any m-coloring on the edges of the complete n-vertex graph contains a monochromatic copy of Kp. Here, we think of p as a fixed constant, and m tends to infinity. In his work related to Fermat’s Last Theorem, Schur proved that
2Ω(m) < R(3;m) < O(m!).
While small improvements have been made to the lower bound, the upper bound remains unchanged. It is an old problem of Erdős to decide whether R(p; m) = 2O(m), when p is fixed. In this talk, I will sketch a proof of this if we further assume that the edge colorings are semi-algebraic with bounded complexity.
This is joint work with Jacob Fox and Janos Pach.
November 26, 2018 (Monday) at 14:00, Bartosz Walczak (Jagiellonian University, Kraków)
“Sparse Kneser graphs are Hamiltonian”
For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,…,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k≥3, the odd graph K(2k+1,k) has a Hamilton cycle. The proof is based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words. As a byproduct, we obtain a new proof of the so-called Middle Levels Conjecture. This is joint work with Torsten Mütze and Jerri Nummenpalo.
November 21, 2018 (Wednesday) at 10:00, Raman Sanyal (Goethe-Universität Frankfurt)
“Cone valuations, Gram’s relation, and combinatorics”
The Euler-Poincare formula is a cornerstone of the combinatorial theory of polytopes. It states that the number of faces of various dimensions of a convex polytope satisfy a linear relation and it is the only linear relation (up to scaling). Gram’s relation generalizes the fact that the sum of (interior) angles at the vertices of a convex n-gon is (n-2)π. In dimensions 3 and up, it is necessary to consider angles at all faces. This gives rise to the interior angle vector of a convex polytope and Gram’s relation is the unique linear relation (up to scaling) among its entries. In this talk, we will consider generalizations of “angles” in the form of cone valuations. It turns out that the associated generalized angle vectors still satisfy Gram’s relation and that it is the only linear relation, independent of the notion of “angle”! To prove such a result, we rely on a very powerful connection to the combinatorics of zonotopes. The interior angle vector of a zonotope is independent of the chosen cone valuation and depends only on the associated lattice of flats. If time permits, we discuss flag-angles as a semi-discrete generalization of flag-vectors and their linear relations. This is joint work with Spencer Backman and Sebastian Manecke
November 5, 2018 (Monday) at 14:00, Imre Bárány (Rényi Institute, UCL)
“Theorems of Caratheodory, Helly, and Tverberg without dimension”
Caratheodory’s classic result says that if a point p lies in the convex hull of a set P ⊆ Rd, then it lies in the convex hull of a subset Q ⊆ P of size at most d+1. What happens if we want a subset Q of size k < d+1 such that p ∈ conv Q? In general, this is impossible as conv Q is too low dimensional. We offer some remedy: p is close to conv Q for some subset Q of size k, in an appropriate sense. Similar results hold for the classic Helly and Tverberg theorems as well. This is joint work with Karim Adiprasito, Nabil Mustafa, and Tamas Terpai.
October 31, 2018 (Wednesday) at 14:00, Géza Tóth (Rényi Institute)
“The crossing number of crossing-critical graphs”
A graph G is k-crossing critical if cr(G) ≥ k but if we delete any edge e of G, for the resulting graph G-e, cr(G-e) < k.
Richter and Thomassen proved 25 years ago, that if G is k-crossing critical, then cr(G) ≤ 2.5k+16. On the other hand, there are k-crossing critical graphs with crossing number k+√k.
We slightly improve the upper bound of Richter and Thomassen to roughly 2k.
October 22, 2018 (Monday) at 14:00, Shariar Shariari (Pomona College)
“Combinatorics of Posets of Subspaces”
Let V be a finite dimensional vector space over a finite field, and consider the poset of subspaces of V ordered by inclusion. The combinatorial properties of this partially ordered set often resemble those of the Boolean lattices, the subsets of a finite set ordered by inclusion. Often the case of subsets is easier to handle, but, there are situations where a combinatorial question is easier to answer for subspaces. In this talk, we discuss a few combinatorial problems in the poset of subspaces including forbidden configuration problems: Given a small poset P, what is the largest number of subspaces of V that do not contain a copy of P? The latter is joint work with Song Yu.
October 15, 2018 (Monday) at 14:00, Radoslav Fulek (IST Austria)
“Beyond stability of intersections in drawings of graphs”
A drawing D of a graph G on a surface is a weak embedding if D can be approximated by an arbitrarily close (in the supremum norm) embedding of G. A 2-dimensional simplicial complex K is orientably thickenable if K embeds into some orientable 3-dimensional manifold which is not fixed in advance. By a result of A. Skopenkov (1994), testing if a drawing of a graph on a closed orientable surface is a weak embedding can be reduced in polynomial time to orientable thickenability testing.
While we can test weak embeddability in quasi-linear time, testing orientable thickenability is in NP, and neither NP-hardness nor the existence of a polynomial time algorithm was established to the best of our knowledge. We show that some well-known generalizations of weak embeddability testing, whose complexity status is unknown, can also be reduced in polynomial time to orientable thickenability testing of 2-dimensional simplicial complexes, and in some interesting special cases, even to embeddability testing of collapsible 2-dimensional simplicial complexes in R3. The complexity status of the latter is an exciting open problem.
October 8, 2018 (Monday) at 14:00, Andrey Kupavskii (University of Birmingham)
“Crossing Tverberg theorem”
The famous Tverberg theorem states that, given a family of (d+1)n points in Rd in general position, one can find n vertex-disjoint d-simplices with vertices in P that all share a common point. We show that we can choose these simplices in such a way that, additionally, their boundaries mutually intersect. In particular, on any 3n points in general position on the plane one can find n mutually crossing triangles.
Joint work with R. Fulek, B. Gartner, P. Valtr and U. Wagner
October 8, 2018 (Monday) at 11:00, Michele Conforti (University of Padova)
“Scanning integer points with lex-cuts: A finite cutting plane algorithm for nonlinear programming over compact sets”
We consider the nonnegative integer points ordered by a lexicographic rule. To each such point x we provide an inequality description of the convex hull of the nonnegative integer points that dominate x in the lex-ordering. We use these inequalities (lex-cuts) as cutting planes to provide a finite cutting plane method to solve the integer program min{cx: x ∈ S ∩ Zn}, where S ⊂ Rn is a compact set and c ∈ Zn.
The family of lex-cuts contains the Chvátal-Gomory cuts, but does not contain and is contained in the family of split cuts. We analyze the worst-case behavior of our algorithm and propose some variants.
Joint work with Marianna De Santis, Marco Di Summa and Francesco Rinaldi.
October 3, 2018 (Wednesday) at 15:00, Natan Rubin (Ben-Gurion University) in BC 420!
“Piercing Convex Sets by Points”
We show that for any n-point set P in the plane, there is a set Q of cardinality O*(ε-3/2) that pierces all the convex sets that contain at least εn of the points of P. Such a set is called a weak ε-net.
This is the first improvement on the 25-year-old O(ε-2) bound of Alon, Bárány, Kleitman, and Füredi. The study of ε-nets is central to Discrete and Computational Geometry.
October 1, 2018 (Monday) at 16:00, Christian Sohler (TU Dortmund)
“Strong coresets for k-median and subspace clustering: Goodbye dimension”
I will start my talk with an introduction to the area of coresets for clustering problems, give basic definitions and explain how coresets can be used to obtain distributed and streaming algorithms. During my talk, I will mostly focus on a commonly used coreset definition that has been introduced by Har-Peled and Mazumdar: A coreset is a weighted set S of points such that for all sets C of k centers we have (1-ε) cost(P,C) ≤ cost(S,C) ≤ (1+ε) cost(P,C), where cost(P,C) is the sum of distances of the points in P to their closest center in C. Then I will present a new algorithm to compute coresets that have a similar for-all guarantee as in the above definition and that consist of a number of points that is independent of the size of the input point set P and the dimension of the input space d.
Joint work with David Woodruff.
October 1, 2018 (Monday) at 14:00, Andrzej Ruciński (Adam Mickiewicz University)
“Powers of Hamiltonian cycles in randomly augmented graphs”
In my talk I am going to discuss the existence of powers of Hamilton cycles in graphs with large minimum degree to which additional edges have been added randomly. In particular, for graphs with minimum degree at least kn/(k+1), the addition of just O(n) random edges ensures a creation of the (2k+1)-st power of a Hamilton cycle. This is joint work with Sylwia Antoniuk, Andrzej Dudek, Christian Reiher, and Mathias Schacht.
September 24, 2018 (Monday) at 14:00, Rom Pinchasi (Technion)
“Algebraic proof of a conjecture of Erdős and Purdy”
Erdős and Purdy conjectured that for n≥5 one cannot find a set of n red points in general position and another set of n-1 blue points such that every line determined by two red points passes also through a blue point. This conjecture is trivially true for n odd but turns to be very challenging for n even. This conjecture is a special (but important) case of the magic configuration conjecture of Murty. The conjecture of Murty was solved in 2008 in a topological setting. Here we present a purely algebraic proof of the conjecture of Erdős and Purdy. On the way we also prove a nice result on vectors in the two dimensional plane.
