Measurable Regular Subgraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910569979707392 |
|---|---|
| author | Bowen, Matt Conley, Clinton T. Weilacher, Felix |
| author_facet | Bowen, Matt Conley, Clinton T. Weilacher, Felix |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09597 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Measurable Regular Subgraphs Bowen, Matt Conley, Clinton T. Weilacher, Felix Logic Combinatorics 03E15, 05C70 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. |
| title | Measurable Regular Subgraphs |
| topic | Logic Combinatorics 03E15, 05C70 |
| url | https://arxiv.org/abs/2408.09597 |