Please email any errors or updates to our website support/editor.
PDF files require Adobe Acrobat Reader.
Friday, March 8, 2019 — 1:00 PM EST
Title: On the Hardness of 4-coloring a 3-colorable graph
Speaker: Akshay Ramachandran Affiliation: University of Waterloo Room: MC 5479Abstract: 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.
Friday, March 8, 2019 — 3:30 PM EST
Title: From graph theory to set theory and back
Speaker: Anton Bernshteyn Affiliation: Carnegie Mellon University Room: MC 5501Abstract:
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.