KAIST Discrete Math Seminar

Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once allowed with subexponential-time or FPT-time is a central question. Recently, several independent results appeared regarding this question, implying negative answer toward the conjecture. They state that, for every 0<r<1, there is no r-approximation which runs in better than certain subexponential-function time. We outline the results in these papers and overview the important concepts and techniques used to obtain such results.

A small cover is a topological analogue of real toric varieties, and is an important object in toric topology. It is noted that the formula of the ℤ₂-cohomology ring of small cover is well-known. However, the integral cohomology ring of small covers has not been known well.

In this talk, we discuss about the Betti numbers and its torsion of the small covers associated to some nestohedra including graph associahedra. Interestingly, the Betti numbers can be computed by purely combinatorial method (in terms of graphs and hypergraphs). To our surprise, for specific families of graphs, these numbers are deeply related to well-known combinatorial sequences such as the Catalan numbers and Euler zigzag numbers.