pith. sign in

arxiv: 2408.09597 · v1 · pith:RSZQ757Qnew · submitted 2024-08-18 · 🧮 math.LO · math.CO

Measurable Regular Subgraphs

Matt Bowen , Clinton T. Conley , Felix Weilacher This is my paper
classification 🧮 math.LO math.CO
keywords graphsmeasurableregularbaireborelcomputablesolutionadmits
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Measurable matchings in unbalanced graphs

    math.LO 2026-06 unverdicted novelty 8.0

    In Borel unbalanced bipartite multigraphs there exists a Borel matching covering μ-almost every vertex in the higher-degree part for any Borel probability measure μ.

  2. Measurable matchings in unbalanced graphs

    math.LO 2026-06 unverdicted novelty 7.0

    In Borel unbalanced bipartite multigraphs there exists a Borel matching covering μ-almost every vertex in the higher-degree part for arbitrary Borel probability measures μ.