No Countable Basis for Borel Directed Graphs of Dichromatic Number at Least Three

Tonatiuh Matos-Wiederhold

arxiv: 2604.05228 · v1 · submitted 2026-04-06 · 🧮 math.LO

No Countable Basis for Borel Directed Graphs of Dichromatic Number at Least Three

Tonatiuh Matos-Wiederhold This is my paper

Pith reviewed 2026-05-10 18:36 UTC · model grok-4.3

classification 🧮 math.LO

keywords Borel directed graphsdichromatic numberΣ¹₂-completeBorel homomorphismcountable basisdescriptive set theorygraph coloringNP-completeness

0 comments

The pith

Borel directed graphs with dichromatic number at least three form a Σ¹₂-complete class, so no countable basis exists for them.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the collection of Borel directed graphs whose vertices can be partitioned into two Borel acyclic sets is a Σ¹₂-complete set of objects. This is the same as saying that the problem of deciding whether any given Borel directed graph has Borel dichromatic number at least 3 is Π¹₂-complete. A sympathetic reader cares because the completeness result rules out any countable list of example graphs that could generate the entire class through Borel homomorphisms. The argument finishes the finite-threshold case for both chromatic and dichromatic Borel coloring by lifting a known classical hardness proof.

Core claim

The Borel directed graphs whose vertex set admits a partition into two Borel acyclic sets form a Σ¹₂-complete set; equivalently, that deciding whether a Borel directed graph has Borel dichromatic number at least 3 is a Π¹₂-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 Π¹₂. The proof lifts the classical NP-completeness reduction of Bokal, Fijavž, Juvan, Kayll, and Mohar to the Borel setting using Thornton's coding framework, and combines it with a reduction from undirected to directed coloring problems.

What carries the argument

Lifting of the classical NP-completeness reduction for directed graph coloring to the Borel setting via Thornton's coding framework, together with the undirected-to-directed reduction.

If this is right

For every finite k the set of Borel graphs or directed graphs that admit a Borel k-coloring is Σ¹₂-complete.
No countable basis exists under Borel homomorphisms for any of these finite-threshold classes.
Any basis for the class must itself be at least Π¹₂ in descriptive complexity.
The finite-threshold situation is strictly harder than the uncountable-threshold case, where single-element or continuum-sized bases are known to exist.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same lifting technique may apply to other Borel invariants such as list chromatic number or choice number.
The result indicates that effective classification of Borel graphs is blocked at countable complexity for all finite coloring thresholds.
One could test the boundary by checking whether specific uncountable bases from the literature can be reduced in complexity for the directed case.

Load-bearing premise

The classical NP-completeness reduction of Bokal et al. lifts to the Borel setting through Thornton's coding framework.

What would settle it

An explicit countable collection of Borel directed graphs such that every Borel directed graph with dichromatic number at least 3 admits a Borel homomorphism to one member of the collection.

Figures

Figures reproduced from arXiv: 2604.05228 by Tonatiuh Matos-Wiederhold.

**Figure 1.** Figure 1: The template gadget F. Shared vertices {a, b, c} correspond to hypergraph vertices; auxiliary vertices {a ′ , b ′ , c ′} are local to each gadget copy. Lemma 3.3 (Gadget property). A map σ : {a, b, c} → 2 extends to a 2-dicoloring of F if and only if σ is not constant (i.e., not all three shared vertices receive the same color). Proof. This is a finite verification; see [BFJ+04, Theorem 3.1]. Lemma 3.4 (Cl… view at source ↗

read the original abstract

I prove that the Borel directed graphs whose vertex set admits a partition into two Borel acyclic sets form a $\mathbf\Sigma^1_2$-complete set; equivalently, that deciding whether a Borel directed graph has Borel dichromatic number at least~$3$ is a $\mathbf\Pi^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\Pi^1_2$. The proof lifts the classical NP-completeness reduction of Bokal, Fijav\v{z}, 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\Sigma^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\v{c}evi\'c) and a continuum-size basis exists for Borel dichromatic number (Raghavan--Xiao).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper finishes the finite Borel (di)chromatic threshold story by proving Π¹₂-completeness for directed graphs with no Borel 2-dicoloring, hence no countable basis.

read the letter

The main point is that the set of Borel directed graphs admitting a partition into two Borel acyclic sets is Σ¹₂-complete. Equivalently, there is no countable family of Borel directed graphs that forms a basis for those with dichromatic number at least 3 under Borel homomorphisms. This rounds out the finite cases, matching what was already known for undirected graphs and contrasting with the uncountable thresholds that do have bases (Kechris-Solecki-Todorčević for chromatic number, Raghavan-Xiao for dichromatic number). The proof strategy lifts the classical NP-completeness of Bokal et al. via Thornton's coding framework and adds a simple undirected-to-directed reduction. That combination is the actual new content, and it is cleanly executed on the surface. The argument stays within standard techniques in the area and does not introduce unnecessary complications. The citation pattern is appropriate, drawing on the relevant prior completeness and basis results without overclaiming. The soft spot is the precise verification that the lifted reduction preserves the equivalence in both directions once everything is Borel. The stress-test concern about whether the directed gadgets allow extra Borel acyclic partitions (or fail to preserve acyclicity) is the one place where a referee would want explicit checks rather than the outline given in the abstract. If that correspondence holds without leakage, the completeness goes through; if not, the hardness direction weakens. Nothing in the strategy suggests it fails, but the details matter here. This is the kind of paper that belongs in a descriptive set theory or Borel combinatorics reading group. Readers already familiar with the undirected Borel chromatic results and Thornton's framework will get the most from it. It is worth sending to peer review because the result is sharp, the method is a direct and natural extension of existing work, and the gap it fills is real.

Referee Report

2 major / 2 minor

Summary. The paper proves that the collection of Borel directed graphs whose vertices admit a partition into two Borel acyclic sets is a Σ¹₂-complete set in the space of directed graphs; equivalently, the problem of deciding whether a Borel directed graph has Borel dichromatic number at least 3 is Π¹₂-complete. The argument proceeds by lifting the classical NP-completeness reduction of Bokal–Fijavž–Juvan–Kayll–Mohar for undirected graphs to the Borel setting via Thornton’s coding framework, followed by a reduction from the undirected to the directed case. As a consequence, no countable family of Borel directed graphs can form a basis for the class of graphs with dichromatic number ≥3 under Borel homomorphisms, and any basis must be at least Π¹₂-complex. This completes the finite-threshold picture, contrasting with the existence of bases at the uncountable threshold.

Significance. If the lifting argument is correct, the result supplies the missing finite-k case for both Borel chromatic and dichromatic numbers, establishing Σ¹₂-completeness and the non-existence of countable bases in a uniform way. It thereby sharpens the contrast with the Kechris–Solecki–Todorčević single-element basis for uncountable chromatic number and the Raghavan–Xiao continuum-sized basis for uncountable dichromatic number. The use of an external classical reduction plus an established coding framework is a strength when the adaptation is fully verified.

major comments (2)

[Section 3 (lifting argument)] The central hardness direction rests on the claim that the lifted directed graph G_x admits a Borel 2-dicoloring if and only if the classical instance x is satisfiable. The manuscript must supply an explicit verification that no extraneous Borel acyclic partition arises from the Thornton coding that would allow a dicoloring when the classical instance is unsatisfiable (or vice versa). Without a detailed case analysis of the gadgets under Borel measurability, the equivalence remains unconfirmed.
[Section 4 (directed reduction)] The reduction from undirected to directed coloring problems is described as “straightforward,” yet the directed gadgets must preserve acyclicity of the color classes in both directions while maintaining Borel measurability. A concrete check that the directed version does not introduce new Borel 2-dicolorings (or destroy existing ones) is required to ensure the Π¹₂-hardness carries over.

minor comments (2)

[Introduction] Notation for the space of Borel directed graphs and the precise definition of Borel homomorphism should be stated explicitly at the beginning of the technical sections rather than assumed from prior literature.
[Abstract] The abstract states that the result “completes the picture for finite Borel chromatic and dichromatic thresholds”; a short table or sentence summarizing the status for each finite k would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and for identifying points where the verifications in the lifting and reduction arguments require more explicit detail. We agree that the current manuscript's high-level descriptions leave the Borel-specific equivalences insufficiently confirmed, and we will revise accordingly to include the requested case analyses. This will strengthen the paper without altering its core claims.

read point-by-point responses

Referee: [Section 3 (lifting argument)] The central hardness direction rests on the claim that the lifted directed graph G_x admits a Borel 2-dicoloring if and only if the classical instance x is satisfiable. The manuscript must supply an explicit verification that no extraneous Borel acyclic partition arises from the Thornton coding that would allow a dicoloring when the classical instance is unsatisfiable (or vice versa). Without a detailed case analysis of the gadgets under Borel measurability, the equivalence remains unconfirmed.

Authors: We agree that the manuscript currently relies on a high-level invocation of Thornton's coding framework without providing a full gadget-by-gadget verification under Borel measurability. In the revised version we will add a detailed case analysis: for each gadget in the lifted graph G_x we will show (i) that any Borel 2-dicoloring induces a satisfying assignment when the classical instance is satisfiable, and (ii) that when the instance is unsatisfiable, no Borel acyclic partition of the vertices can exist, because any purported Borel coloring would have to violate the coding constraints in a measurable way that forces a cycle in one of the color classes. This analysis will explicitly rule out extraneous Borel partitions arising from the coding. revision: yes
Referee: [Section 4 (directed reduction)] The reduction from undirected to directed coloring problems is described as “straightforward,” yet the directed gadgets must preserve acyclicity of the color classes in both directions while maintaining Borel measurability. A concrete check that the directed version does not introduce new Borel 2-dicolorings (or destroy existing ones) is required to ensure the Π¹₂-hardness carries over.

Authors: We concur that labeling the reduction 'straightforward' is insufficient and that an explicit verification is needed to confirm preservation of acyclicity and Borel measurability in both directions. In the revision we will expand Section 4 with a concrete check of the directed gadgets: we will verify that a Borel 2-dicoloring of the directed graph exists if and only if one exists for the corresponding undirected graph, by showing that the orientation and auxiliary vertices do not create new Borel acyclic partitions nor destroy existing ones. Each gadget will be examined to ensure the acyclicity condition is equivalent on both sides under Borel functions. revision: yes

Circularity Check

0 steps flagged

No circularity; completeness via external lift of classical NP result and independent coding framework

full rationale

The derivation establishes Σ¹₂-completeness of the set of Borel directed graphs with dichromatic number ≥3 by lifting the known NP-completeness of Bokal-Fijavž-Juvan-Kayll-Mohar (external) via Thornton's coding framework (independent) and a straightforward undirected-to-directed reduction. No equation or step reduces the target completeness statement to a fitted parameter, self-definition, or load-bearing self-citation. The proof chain remains self-contained against external benchmarks and does not rename or presuppose its own conclusion.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the applicability of Thornton's coding framework to lift the cited classical reduction; both are external results whose correctness is presupposed.

axioms (1)

domain assumption Thornton's coding framework permits lifting classical NP-completeness reductions for directed graphs to the Borel setting.
Explicitly invoked as the mechanism for the main proof.

pith-pipeline@v0.9.0 · 5546 in / 1265 out tokens · 59695 ms · 2026-05-10T18:36:09.684268+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the set of nice codes for Borel directed graphs admitting a Borel 2-dicoloring is Σ¹₂-complete
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat ≃ Nat recovery unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

lifts the classical NP-completeness reduction of Bokal et al. to the Borel setting, using the coding framework of Thornton

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Mark Kayll, and Bojan Mohar

Drago Bokal, Ga s per Fijav z , Martin Juvan, P. Mark Kayll, and Bojan Mohar. The circular chromatic number of a digraph. Journal of Graph Theory , 46(3):227--240, 2004. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.20003, https://doi.org/10.1002/jgt.20003 doi:10.1002/jgt.20003

work page doi:10.1002/jgt.20003 2004
[2]

Miller, David Schrittesser, and Zolt \' a n Vidny \' a nszky

Rapha \" e l Carroy, Benjamin D. Miller, David Schrittesser, and Zolt \' a n Vidny \' a nszky. Minimal definable graphs of definable chromatic number at least three. Forum of Mathematics, Sigma , 9:e7, 2021. https://doi.org/10.1017/fms.2020.58 doi:10.1017/fms.2020.58

work page doi:10.1017/fms.2020.58 2021
[3]

Complexity of linear equations and infinite gadgets, 2025

Jan Greb \' k and Zolt \' a n Vidny \' a nszky. Complexity of linear equations and infinite gadgets, 2025. URL: https://arxiv.org/abs/2501.06114, https://arxiv.org/abs/2501.06114 arXiv:2501.06114

work page arXiv 2025
[4]

Kechris, Sławomir Solecki, and Stevo Todor c evi \'c

Alexander S. Kechris, Sławomir Solecki, and Stevo Todor c evi \'c . Borel chromatic numbers. Advances in Mathematics , 141(1):1--44, 1999

work page 1999
[5]

Benjamin D. Miller. Measurable chromatic numbers . Journal of Symbolic Logic , 73(4):1139 -- 1157, 2008. https://doi.org/10.2178/jsl/1230396910 doi:10.2178/jsl/1230396910

work page doi:10.2178/jsl/1230396910 2008
[6]

The dichromatic number of a digraph

V \'i ctor Neumann-Lara. The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B , 33(3):265--270, 1982. URL: https://www.sciencedirect.com/science/article/pii/0095895682900466, https://doi.org/10.1016/0095-8956(82)90046-6 doi:10.1016/0095-8956(82)90046-6

work page doi:10.1016/0095-8956(82)90046-6 1982
[7]

Borel order dimension

Dilip Raghavan and Ming Xiao. Borel order dimension, 2024. URL: https://arxiv.org/abs/2409.06516, https://arxiv.org/abs/2409.06516 arXiv:2409.06516

work page arXiv 2024
[8]

An algebraic approach to Borel CSPs , 2022

Riley Thornton. An algebraic approach to Borel CSPs , 2022. URL: https://arxiv.org/abs/2203.16712, https://arxiv.org/abs/2203.16712 arXiv:2203.16712 , https://doi.org/10.48550/arXiv.2203.16712 doi:10.48550/arXiv.2203.16712

work page doi:10.48550/arxiv.2203.16712 2022
[9]

Descriptive Aspects of Locally Checkable Labelling and Constraint Satisfaction Problems

Riley Thornton. Descriptive Aspects of Locally Checkable Labelling and Constraint Satisfaction Problems . Phd dissertation, University of California, Los Angeles, 2022. URL: https://escholarship.org/uc/item/3xh1z3qh

work page 2022
[10]

A complexity problem for Borel graphs

Stevo Todor c evi \'c and Zolt \' a n Vidny \' a nszky. A complexity problem for Borel graphs. Inventiones Mathematicae , 226(1):225--249, 2021. https://doi.org/10.1007/s00222-021-01047-z doi:10.1007/s00222-021-01047-z

work page doi:10.1007/s00222-021-01047-z 2021

[1] [1]

Mark Kayll, and Bojan Mohar

Drago Bokal, Ga s per Fijav z , Martin Juvan, P. Mark Kayll, and Bojan Mohar. The circular chromatic number of a digraph. Journal of Graph Theory , 46(3):227--240, 2004. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.20003, https://doi.org/10.1002/jgt.20003 doi:10.1002/jgt.20003

work page doi:10.1002/jgt.20003 2004

[2] [2]

Miller, David Schrittesser, and Zolt \' a n Vidny \' a nszky

Rapha \" e l Carroy, Benjamin D. Miller, David Schrittesser, and Zolt \' a n Vidny \' a nszky. Minimal definable graphs of definable chromatic number at least three. Forum of Mathematics, Sigma , 9:e7, 2021. https://doi.org/10.1017/fms.2020.58 doi:10.1017/fms.2020.58

work page doi:10.1017/fms.2020.58 2021

[3] [3]

Complexity of linear equations and infinite gadgets, 2025

Jan Greb \' k and Zolt \' a n Vidny \' a nszky. Complexity of linear equations and infinite gadgets, 2025. URL: https://arxiv.org/abs/2501.06114, https://arxiv.org/abs/2501.06114 arXiv:2501.06114

work page arXiv 2025

[4] [4]

Kechris, Sławomir Solecki, and Stevo Todor c evi \'c

Alexander S. Kechris, Sławomir Solecki, and Stevo Todor c evi \'c . Borel chromatic numbers. Advances in Mathematics , 141(1):1--44, 1999

work page 1999

[5] [5]

Benjamin D. Miller. Measurable chromatic numbers . Journal of Symbolic Logic , 73(4):1139 -- 1157, 2008. https://doi.org/10.2178/jsl/1230396910 doi:10.2178/jsl/1230396910

work page doi:10.2178/jsl/1230396910 2008

[6] [6]

The dichromatic number of a digraph

V \'i ctor Neumann-Lara. The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B , 33(3):265--270, 1982. URL: https://www.sciencedirect.com/science/article/pii/0095895682900466, https://doi.org/10.1016/0095-8956(82)90046-6 doi:10.1016/0095-8956(82)90046-6

work page doi:10.1016/0095-8956(82)90046-6 1982

[7] [7]

Borel order dimension

Dilip Raghavan and Ming Xiao. Borel order dimension, 2024. URL: https://arxiv.org/abs/2409.06516, https://arxiv.org/abs/2409.06516 arXiv:2409.06516

work page arXiv 2024

[8] [8]

An algebraic approach to Borel CSPs , 2022

Riley Thornton. An algebraic approach to Borel CSPs , 2022. URL: https://arxiv.org/abs/2203.16712, https://arxiv.org/abs/2203.16712 arXiv:2203.16712 , https://doi.org/10.48550/arXiv.2203.16712 doi:10.48550/arXiv.2203.16712

work page doi:10.48550/arxiv.2203.16712 2022

[9] [9]

Descriptive Aspects of Locally Checkable Labelling and Constraint Satisfaction Problems

Riley Thornton. Descriptive Aspects of Locally Checkable Labelling and Constraint Satisfaction Problems . Phd dissertation, University of California, Los Angeles, 2022. URL: https://escholarship.org/uc/item/3xh1z3qh

work page 2022

[10] [10]

A complexity problem for Borel graphs

Stevo Todor c evi \'c and Zolt \' a n Vidny \' a nszky. A complexity problem for Borel graphs. Inventiones Mathematicae , 226(1):225--249, 2021. https://doi.org/10.1007/s00222-021-01047-z doi:10.1007/s00222-021-01047-z

work page doi:10.1007/s00222-021-01047-z 2021