Logic Seminar
In the first half of the talk, I will give a high-level overview of Borel combinatorics and Linial's LOCAL model of distributed computing, and the surprising connection between the two fields. The second half of the talk will be centered around a particular instance of this connection. One of the most striking results of Borel combinatorics is Marks' determinacy method: Marks proved the existence of $d$-regular acyclic Borel graphs with Borel chromatic number $d+1$ using the Borel determinacy theorem. I will discuss how the adaptation of this method to the LOCAL world inspires a more general version, which leads to a very rich class of examples of $3$-regular acyclic Borel graphs. This yields new proofs of several known results. As a new application, I will show that it is hard to decide whether the Borel chromatic number of a Borel graph is $\leq 3$, even for acyclic $3$-regular graphs (that is, such graphs form a $\Sigma^1_2$-complete set).