Finitely Dependent Coloring

  • Alexander Holroyd | Microsoft Research

Do local constraints demand global coordination? I’ll address a particularly simple formulation of this question: can the vertices of a graph be assigned random colours in a stationary way, so that neighboring colours always differ, but without long-range dependence? The quest to answer this has led to the discovery of a beautiful yet mysterious new stochastic process that seemingly has no right to exist, while overturning the conventional thinking on a fundamental 49-year old question. (Joint work with Tom Liggett.)

Speaker Details

Senior Researcher at Microsoft Research, Redmond. PhD: University of Cambridge (2000). Previous positions: UCLA (1999-2002), UC Berkeley (2002-2003), University of British Columbia (2002-2008). Awards: Rollo Davidson Prize (2004), Andre-Aisenstadt Prize (2007).

Watch Next