Caltech Home > PMA Home > Calendar > Logic Seminar
open search form
Wednesday, February 19, 2025
12:00 PM - 1:00 PM
Online Event

Logic Seminar

Locally checkable labeling problems in the Borel hierarchy
Felix Weilacher, Department of Mathematics, UC Berkeley,

Please note that the time is PST

A locally checkable labeling problem (LCL) on a group Γ asks one to find a labeling of the Cayley graph of Γ satisfying a fixed, finite set of "local" constraints. Typical examples include proper coloring and perfect matching problems. We consider the existence of solutions to LCLs in the setting of descriptive set theory. For example, given a free action of Γ on a Polish space X, we might be interested in solving a given LCL on each orbit in a continuous, Borel, measurable, etc. way.

Motivated by a result of Bernshteyn's linking continuous combinatorics and distributed computing, we are especially interested in the difference between the Borel and continuous settings. Gao, Jackson, Krohne, and Seward showed that Free Borel actions of Zn always admit Borel 3-colorings (of the natural induced graph) but that 4 colors are needed for continuous colorings when n>1. Brandt et al. demonstrated a similar separation for Fn, the free group on n generators, when n>1.

In an attempt to understand more finely the gap between Borel and continuous combinatorics, we consider the existence of Baire class m solutions to LCLs. For all n>1 and m∈ω, we extend Brandt et al.'s result by producing an LCL on Fn which always admits Baire class m+1 solutions, but not necessarily Baire class m solutions. There are only countably many LCLs, so it remains interesting question to determine the smallest α<ω1 for which the Baire class α and Borel combinatorics of Fn are identical.

For more information, please contact Math Dept. by phone at 626-395-4335 or by email at kechris@caltech.edu.