Oliver Club

Alexander HolroydUniversity of Washington
Local constraint solving - how to color without looking (much)

Thursday, October 26, 2017 - 4:00pm
Malott 532

How can individuals cooperate to satisfy local constraints without a central authority? Examples might include autonomous drones navigating in a swarm, or university departments scheduling their seminars. Individuals can make random choices and communicate with each other, but all must follow the same procedure.

How small can we make the "coding radius" - the distance to which an individual must communicate? In the setting of the integer line $\mathbf{Z}$, there is a surprising universal answer that applies to every non-trivial constraint problem. In $d$-dimensional Euclidean space, answers are available for the key case of proper coloring; it turns out that there is a huge difference between 3 and 4 colors. Finally, I'll mention how changing the question slightly has led to the discovery of an amazing mathematical object that seemingly has no right to exist.

Refreshments will be served at 3:30 PM.