Colloquium: Local Constraint Solving — How to Colour Without Looking (Much)

  • Date:
  • Location: Ångströmlaboratoriet, Lägerhyddsvägen 1
  • Lecturer: Alexander Holroyd
  • Contact person: Thomas Kragh
  • Seminarium

How can individuals cooperate to satisfy local constraints without a central authority?  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 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 colouring; it turns out that there is a huge difference between 3 and 4 colours.   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.