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.

2018/2019

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