Descriptive Combinatorics and Distributed Algorithms

Explore the fascinating intersection of descriptive combinatorics and distributed algorithms in this 57-minute Association for Symbolic Logic Invited Address. Delve into Anton Bernshteyn's presentation at the Joint Mathematics Meetings, where he examines the coloring of infinite graphs, introduces the shift graph, and discusses key concepts in descriptive combinatorics. Learn about various results and applications, including extended Brooks' theorem, and investigate the relationships between continuous colorings, deterministic algorithms, measurable colorings, and randomized algorithms. Gain insights into the connections between these mathematical fields and their practical implications in computer science and graph theory.

Intro
Coloring infinite graphs
Example: the shift graph
Descriptive combinatories
A sample of results
Example: paths
From distributed algorithms to descriptive results
Application I: extended Brooks
Converse?
Continuous colorings and deterministic algorithms
Measurable colorings and randomized algorithms?