2024/08/18 by Bowen, Matt, Conley, Clinton T., Weilacher, Felix
#03E15 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2408.09597
We show that every d-regular bipartite Borel graph admits a Baire measurable k-regular spanning subgraph if and only if d is odd or k is even. This gives the first example of a locally checkable coloring problem which is known to have a Baire measurable solution on Borel graphs but not a computable solution on highly computable graphs. We also prove the analogous result in the measure setting for hyperfinite graphs.