Measurable graph colorings | Department of Mathematics

Measurable graph colorings

Event Information
Event Location: 
GAB 461, 4-5 PM; Refreshments: GAB 472, 3:30 PM
Event Date: 
Monday, November 18, 2013 - 4:00pm

Theorems about colorings of finite graphs can often be transferred to infinite graphs using compactness. However, this style of argument uses the axiom of choice and cannot hope to produce colorings with nice properties such as being measurable with respect to some probability measure. In this talk, we study graphs whose vertices are the elements of some standard probability space and whose edge relation is Borel. The existence of measurable colorings of such graphs has been a converging point of interest for investigations in several areas including descriptive set theory, ergodic theory, probability, and the study of graph limits. In this context, we prove an analogue of Brooks's theorem in finite graph theory showing that a graph of degree less than or equal to d > 2 has a measurable d-coloring, provided the graph does not contain any cliques on d+1 vertices. We finish by discussing connections with some other problems in descriptive set theory.