KAIST Discrete Math Seminar

One of the cornerstones of extremal graph theory is a result of Füredi, later reproved and given due prominence by Alon, Krivelevich and Sudakov, saying that if H is a bipartite graph with maximum degree r on one side, then there is a constant C such that every graph with n vertices and C n^{2 – 1/r} edges contains a copy of H. This result is tight up to the constant when H contains a copy of K_r,s with s sufficiently large in terms of r. We conjecture that this is essentially the only situation in which Füredi’s result can be tight and prove this conjecture for r = 2. More precisely, we show that if H is a C₄-free bipartite graph with maximum degree 2 on one side, then there are positive constants C and δ such that every graph with n vertices and C n^{3/2 – δ} edges contains a copy of H. This answers a question by Erdős from 1988. The proof relies on a novel variant of the dependent random choice technique which may be of independent interest. This is joint work with David Conlon.

In the k-cut problem, we are given an edge-weighted graph G and an integer k, and have to remove a set of edges with minimum total weight so that G has at least k connected components. This problem has been studied various algorithmic perspectives including randomized algorithms, fixed-parameter tractable algorithms, and approximation algorithms. Their proofs of performance guarantees often reveal elegant structures for cuts in graphs.
It has still remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this talk, I will give an overview on recent progresses on both exact and approximation algorithms. Our algorithms are inspired by structural similarities between k-cut and the k-clique problem.

Mathematical optimization is a field that studies algorithms, given an objective function and a feasible set, to find the element that maximizes or minimizes the objective function from the feasible set. While most interesting optimization problems are NP-hard and unlikely to admit efficient algorithms that find the exact optimal solution, many of them admit efficient “approximation algorithms” that find an approximate optimal solution.
Continuous and discrete optimization are the two main branches of mathematical optimization that have been primarily studied in different contexts. In this talk, I will introduce my recent results that bridge some of important continuous and discrete optimization problems, such as matrix low-rank approximation and Unique Games. At the heart of the connection is the problem of approximately computing the operator norm of a matrix with respect to various norms, which will allow us to borrow mathematical tools from functional analysis.

The infamous Erdős-Szekeres conjecture, posed in 1935, states that the minimum number ES(n) of points on a plane in general position (that is, no three colinear points) that guarantees a subset of n points in convex position is equal to 2^(n-2) + 1. Despite many years of effort, the upper bound of ES(n) had not been better than O(4^{n – o(n)}) until Suk proved the groundbreaking result ES(n)≤2^n+o(n) in 2016.
In this talk, we focus on a variant of this problem by Erdős, Tuza and Valtr regarding the number ETV(a, b, n) of points needed to force either an a-cup, b-cap or a convex n-gon for varying a, b and n. They showed ETV(a, b, n) > \sum_{i=n-b}^{a-2} \binom{n}{i-2} by supplying a set of points with no a-cup, b-cap nor a n-gon of that many number, and conjectured that the inequality cannot be improved. Due to their construction, the conjecture is in fact equivalent to the Erdős-Szekeres conjecture. However, even the simplest equality ETV(4, n, n) = \binom{n+1}{2} + 1, which must be true if the Erdős-Szekeres conjecture is, has not been verified yet. To the best of our knowledge, the bound ETV(4, n, n) ≤ \binom{n + 2}{2} – 1, mentioned by Balko and Valtr in 2015, is currently the best bound known in literature.
The talk is divided into two parts. First, we introduce the mentioned works on the Erdős-Szekeres conjecture and observe that the argument of Suk can be directly adapted to prove an improved bound of ETV(a, n, n). Then we show the bound ETV(4, n, n) ≤ \binom{n+2}{2} – C \sqrt{n} for a fixed constant C>0, improving the previously known best bound of Balko and Valtr.