Events by date

Title: On the Hardness of 4-coloring a 3-colorable graph

Abstract: A consequence of the PCP theorem is that it is NP-hard to approximate the chromatic number of a general graph to within \n^{1-\eps} for any constant epsilon.

Title: From graph theory to set theory and back

Abstract:

Many results in finite combinatorics can be extended to infinite structures via compactness---but this transfer is powered by the Axiom of Choice and leads, in general, to highly "pathological" objects.