No Countable Basis for Borel Directed Graphs of Dichromatic Number at Least Three
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911571381321728 |
|---|---|
| author | Matos-Wiederhold, Tonatiuh |
| author_facet | Matos-Wiederhold, Tonatiuh |
| contents | I prove that the Borel directed graphs whose vertex set admits a partition into two Borel acyclic sets form a $\mathbfΣ^1_2$-complete set; equivalently, that deciding whether a Borel directed graph has Borel dichromatic number at least~$3$ is a $\mathbfΠ^1_2$-complete problem. It follows that no countable family of Borel directed graphs can serve as a basis for this class under Borel homomorphism and, more generally, that any basis must be at least as complex as~$\mathbfΠ^1_2$.
The proof lifts the classical NP-completeness reduction of Bokal, Fijavž, Juvan, Kayll, and Mohar to the Borel setting, using the coding framework of Thornton. Combined with a straightforward reduction from undirected to directed coloring problems, this completes the picture for finite Borel chromatic and dichromatic thresholds: for every finite $k$, the set of Borel (directed) graphs admitting a Borel $k$-(di)coloring is $\mathbfΣ^1_2$-complete, and in particular admits no countable basis. This contrasts with the uncountable threshold, where a single-element basis exists for Borel chromatic number (Kechris--Solecki--Todorčević) and a continuum-size basis exists for Borel dichromatic number (Raghavan--Xiao). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05228 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | No Countable Basis for Borel Directed Graphs of Dichromatic Number at Least Three Matos-Wiederhold, Tonatiuh Logic I prove that the Borel directed graphs whose vertex set admits a partition into two Borel acyclic sets form a $\mathbfΣ^1_2$-complete set; equivalently, that deciding whether a Borel directed graph has Borel dichromatic number at least~$3$ is a $\mathbfΠ^1_2$-complete problem. It follows that no countable family of Borel directed graphs can serve as a basis for this class under Borel homomorphism and, more generally, that any basis must be at least as complex as~$\mathbfΠ^1_2$. The proof lifts the classical NP-completeness reduction of Bokal, Fijavž, Juvan, Kayll, and Mohar to the Borel setting, using the coding framework of Thornton. Combined with a straightforward reduction from undirected to directed coloring problems, this completes the picture for finite Borel chromatic and dichromatic thresholds: for every finite $k$, the set of Borel (directed) graphs admitting a Borel $k$-(di)coloring is $\mathbfΣ^1_2$-complete, and in particular admits no countable basis. This contrasts with the uncountable threshold, where a single-element basis exists for Borel chromatic number (Kechris--Solecki--Todorčević) and a continuum-size basis exists for Borel dichromatic number (Raghavan--Xiao). |
| title | No Countable Basis for Borel Directed Graphs of Dichromatic Number at Least Three |
| topic | Logic |
| url | https://arxiv.org/abs/2604.05228 |