Title: From graph theory to set theory and back
|Affiliation:||Carnegie Mellon University|
Many results in finite combinatorics can be extended to infinite structures via compactness---but this transfer is powered by the Axiom of Choice and leads, in general, to highly "pathological" objects. Hence, it is natural to wonder which combinatorial constructions can be performed in a more "well-behaved" fashion. For instance, given a graph on a probability space, when can it be properly coloured so that each colour class forms a measurable set? Questions of this type are addressed in a young area called descriptive combinatorics. In this talk I will give a general introduction to descriptive combinatorics and then outline a certain precise connection between colorings that are Baire measurable (i.e., "topologically well-behaved") and some well-studied concepts in finite graph theory.
200 University Avenue West
Waterloo, ON N2L 3G1