PIMS Distinguished Speaker: Alexander E. Holroyd

  • Date: 03/19/2013
  • Time: 15:30
Lecturer(s):
Alexander E. Holroyd, Microsoft Research
Location: 

University of Victoria

Topic: 

Random Matching

Description: 

 Suppose that infinitely many red and blue points occur at random locations in Euclidean space, and consider translation-invariant schemes for perfectly matching red points to blue points. (Translation-invariance can be interpreted as meaning that the matching is constructed without favouring one spatial location over another.) What is the best possible cost of such a matching, measured in terms of the edge lengths? What happens if we insist that the matching is constructed without extra randomness, or if we forbid edge crossings, or if the points act as selfish agents? This last restriction can be formalized via the concept of stable marriage, the topic of the 2012 Nobel Prize in Economics. I will review recent progress and open problems on these questions, as well as variants including fair allocation, multi-colour matching and multi-edge matching.

Other Information: 

Location: MacLaurin, D116