Wednesday, February 12, 2025
12:00 PM -
1:00 PM
Online Event
Logic Seminar
Series: Logic Seminar Series
Σ12 -completeness results in Borel combinatorics via gadget reductions
Alex Kastner,
Department of Mathematics,
UCLA,
Please note that the time is PST
In 2021, Todorčević and Vidnyánszky proved that the problem of deciding whether a locally finite Borel graph has a proper Borel 3-coloring is Σ12-complete. Building off of an argument of Thornton, we discuss how the polynomial-time gadget reductions used to establish NP-completeness can often be turned into Borel reductions to establish Σ12-completeness results in Borel combinatorics.
Event Sponsors:
For more information, please contact Math Dept. by phone at 626-395-4335 or by email at kechris@caltech.edu.