DCG-DISOPT seminar

The talks are usually on Mondays at 2:00pm in the Coffee room (MA B1 524), but do check the individual announcements.


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.