Finitely Dependent Coloring
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).
- Date:
- Speakers:
- Alexander Holroyd
- Affiliation:
- Microsoft Research
-
-
Alexander E. Holroyd
Senior Researcher
-
Jeff Running
-
-