Skip to content Skip to navigation
5/5/2017 02:00 pm
CoRE B (305)

On the Algorithmic Aspects of Turán's Theorem

Meng-Tsung Tsai, Dept. of Computer Science

Defense Committee: Prof. Martín Farach-Colton (Chair), Prof. Eric Allender, Prof. William Steiger, and Prof. Rezaul Chowdhury (Stony Brook U.)


Turán's Theorem gives an upper bound on the number of edges of n-node, K_r-free graphs, or equivalently it can be restated as that every n-node, m-edge graph has an independent set of size n^2/(n+2m). We illustrate how to apply Turán's Theorem to algorithmic problems in several ways.

The complexity of dictionary operations, insertion for example, in external memory is well studied. However, the complexity of a batch of n operations is less known, and is seldom as easy as summing up the complexity of individual operations. We obtain lower bounds for batched predecessors by showing the necessity of fetching a set of information that preserves some "independence", where Turán's Theorem applies. We also prove lower bounds for batched deletions in cross-referenced dictionaries based on the existence of an adversarial input that forbids some patterns, where Turán's Theorem again applies.

In addition, we demonstrate a class of inapproximability problems based on the APX-hardness of some building blocks. The NP-hardness of these building blocks are known, but whose NP-hardness reduction is not approximation-preserving. We note how to reformulate the reductions to be approximation-preserving with resorting to Turán's Theorem.