Logic Seminar

The famous 4-color theorem says you only need 4 colors to color the countries on a planar map without giving neighbors the same color. We can ask local versions of these problems– What if each country chooses its color independently after talking to its neighbors? What if the map represents a torus and only looks planar close up? What if we want to define a coloring of an infinite graph without the axiom of choice?

We will explore these questions for random maps related to percolation using factor of iid processes as a model for local algorithms. This talk is partly based on joint work done with Justin Hsu and Daniel Sium as part of CMU's SEMS program.