Descriptive Combinatorics

Department: 
Math
Course Number: 
8803-BER
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Not regularly scheduled

Topics class offered in FALL 2021 by Anton Bernshteyn.

Prerequisites: 

Knowledge of the fundamentals of graph theory will be assumed, as well as some basic familiarity with measure theory and point-set topology (although the necessary background from these areas will be reviewed in the course). No prior knowledge of descriptive set theory is required.

Course Text: 

J.A. Bondy and U.S.R. Murty. Graph Theory, Springer, 2008. A.S. Kechris. Classical Descriptive Set Theory, Springer, 1995. A.S. Kechris and A.S. Marks. Descriptive Graph Combinatorics (preprint), 2018. L. Lovász, Large Networks and Graph Limits, AMS, 2012. A.Tserunyan, Introduction to Descriptive Set Theory (preprint), 2018

 

Topic Outline: 

This course will concentrate on the recently emerged field of descriptive combinatorics, which studies the behavior of combinatorial structures—such as graphs and hypergraphs— under additional topological or measure-theoretic constraints. For example, suppose that G is an (infinite) graph with vertex set [0, 1]. A proper vertex coloring of G can then be thought of as a partition [0, 1] = X1 t . . . t Xk of the unit interval into “color classes” such that no edge of G joins two vertices from the same class. A typical descriptive combinatorics problem is to determine the minimum value of k for which there is such a coloring with the extra requirement that each set X1, . . . , Xk satisfies some regularity conditions (for instance, it is Borel, Lebesgue measurable, has the property of Baire, etc.). It turns out that such questions are not only interesting in their own right, but also provide powerful tools for approaching problems in other areas. For example, Borel graph colorings can be used to derive a number of fundamental dichotomies in descriptive set theory, while matchings in infinite graphs are intimately linked to Banach–Tarski type results. Most developments in descriptive combinatorics happened within the last 20 years, and the field is still full of exciting open problems, many of which will be discussed in this course. 

 

Tentative list of main topics. 

• Definable (Borel, analytic, etc.) graphs: definitions and examples. 

• Borel chromatic numbers. 

– Countable vs. uncountable Borel chromatic numbers.

 – The Kechris–Solecki–Todorcevic G0-dichotomy. 

– Consequences of the G0-dichotomy (the Luzin–Novikov theorem, Silver’s dichotomy). 

– The Feldman–Moore theorem and Borel edge-colorings. 

– A dichotomy theorem for Borel 2-colorings. 

• Bounded degree graphs. 

– Graphs of bounded degree: maximal independent sets and Borel (∆ + 1)-colorings. 

– Greedy algorithms on Borel graphs.

 – Marks’s determinacy method: acyclic graphs with Borel chromatic number ∆ + 1. 

• Measurable and Baire-measurable chromatic numbers. 

– The measurable Brooks’s theorem. 

– The 2χ − 1 bound for Baire-measurable chromatic numbers of locally finite graphs. 

– Measurable colorings of acyclic graphs. 

• Matching theory. 

– Baire-measurable version of Hall’s criterion. 

– Measurable perfect matchings in expanding graphs.

 – Applications to equidecomposition theory and Banach–Tarski paradoxes. 

• Further topics (time permitting): Borel flows and Borel circle squaring, measurable Vizing’s theorem, basics of cost theory, Borel Ramsey theory, connections with distributed algorithms, continuous combinatorics.