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

Logic Seminar

Σ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.

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