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.
Thinking about UNT?
It's easy to apply online. Join us and discover why we're the choice of over 46,000 students.
Apply now