pith. machine review for the scientific record. sign in

arxiv: 2604.21813 · v1 · submitted 2026-04-23 · 🧮 math.LO

Recognition: unknown

Projective Chromatic Numbers

Adrian Rettich , Luke Serafin
Authors on Pith no claims yet

Pith reviewed 2026-05-08 13:05 UTC · model grok-4.3

classification 🧮 math.LO MSC 03E15
keywords projective chromatic numbersdefinable graphswell-order of the realschromatic numberlocally countable graphsBorel graphsprojective hierarchydescriptive set theory
0
0 comments X

The pith

A definable well-order of the reals forces projective chromatic numbers to equal ordinary chromatic numbers for locally countable graphs.

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

The paper extends notions of definable graph coloring into the full projective hierarchy. It proves that the existence of a well-order of the reals definable at level n greater than or equal to 2 makes the smallest number of definable colors needed for a locally countable projective graph equal the smallest number of colors needed without any definability restriction. A similar equality holds for all locally countable Borel graphs once a level-2 definable well-order is assumed. This matters to a sympathetic reader because it shows how a set-theoretic regularity condition on the reals can transfer classical graph-theoretic facts into the definable setting without change. The work also examines whether standard dichotomies and conjectures about graphs survive the move to higher projective levels.

Core claim

For n greater than or equal to 2, the presence of a Delta-1-n definable well-order of the reals implies that the Delta-1-n chromatic number of any locally countable Delta-1-n definable graph G equals the ordinary chromatic number of G. In addition, a Delta-1-2 definable well-order implies the same equality for every locally countable Borel graph. The argument proceeds by extending earlier techniques for definable colorability from Borel and analytic graphs to the projective pointclasses.

What carries the argument

The Delta-1-n definable well-order of the reals, which supplies a uniform way to select or construct colorings that achieve the minimal number of colors while remaining inside the projective definable sets.

If this is right

  • Classical lower bounds on chromatic numbers for particular graphs transfer directly to their definable projective versions under the well-order hypothesis.
  • Known results on the chromatic numbers of Borel graphs extend to the Delta-1-2 definable setting whenever a level-2 well-order exists.
  • If a graph requires infinitely many colors in the ordinary sense, then it also requires infinitely many colors in any Delta-1-n definable coloring.
  • Dichotomy theorems such as the G0 dichotomy become candidates for extension to higher projective pointclasses under the same assumption.

Where Pith is reading between the lines

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

  • In set-theoretic models containing such well-orders, including many models of V equals L, projective definable graph coloring behaves exactly like ordinary coloring.
  • The result supplies a route for establishing the 2n+1 conjecture at projective levels by first assuming the relevant well-order and then applying classical arguments.
  • It leaves open whether the equality between definable and ordinary chromatic numbers can hold in the absence of any definable well-order.
  • The same mechanism may apply to other combinatorial properties of graphs that rely on selecting minimal witnesses, such as list-coloring or choice numbers.

Load-bearing premise

The existence of a well-order of the reals that itself belongs to the Delta-1-n pointclass.

What would settle it

A concrete locally countable Delta-1-n definable graph G together with a Delta-1-n definable well-order of the reals such that every Delta-1-n coloring of G uses strictly more colors than the ordinary chromatic number of G.

read the original abstract

We extend classical notions of definable colourability of graphs to the general projective setting and investigate whether known results, mainly about the $G_0$ dichotomy and the $2n + 1$ conjecture, hold in the context of higher projective pointclasses. We establish that for $n \ge 2$, the presence of a $\mathbf{\Delta}^1_n$-definable well-order of the reals implies $\chi_{\mathbf{\Delta^1_n}}(G) = \chi(G)$ for all locally countable $\mathbf{\Delta^1_n}$-definable graphs $G$, and that the presence of a $\mathbf{\Delta^1_2}$-definable well-order of the reals implies $\chi_{\mathbf{\Delta^1_2}}(G) = \chi(G)$ for all locally countable Borel graphs $G$.

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.

Referee Report

1 major / 2 minor

Summary. The paper extends classical notions of definable colourability to the projective hierarchy. It proves that for n ≥ 2, the existence of a Δ¹_n-definable well-order of the reals implies χ_Δ¹_n(G) = χ(G) for all locally countable Δ¹_n-definable graphs G, and that a Δ¹_2-definable well-order implies the same equality for all locally countable Borel graphs G. The results are presented as conditional implications rather than ZFC theorems.

Significance. If the proofs hold, the results are significant for descriptive set theory: they conditionally extend the G₀ dichotomy and the 2n+1 conjecture to higher projective pointclasses, showing that definable well-orders suffice to produce optimal colorings that achieve equality between the definable and ordinary chromatic numbers. This strengthens the understanding of how complexity shifts in the projective hierarchy affect graph-theoretic invariants for locally countable graphs.

major comments (1)
  1. [§3, Theorem 3.5] §3, Theorem 3.5: The construction of the lexicographically minimal coloring with respect to the Δ¹_n well-order is claimed to be Δ¹_n-measurable, but the argument does not explicitly verify that the well-order selects a coloring that remains within the pointclass when the graph has vertices of arbitrary countable degree; this step is load-bearing for the equality χ_Δ¹_n(G) = χ(G).
minor comments (2)
  1. [Introduction] The abstract and introduction refer to the '2n + 1 conjecture' without a precise statement or citation to the original formulation; adding this would improve readability for readers outside the immediate subfield.
  2. [§2] Notation for the projective chromatic number χ_Δ¹_n is introduced in §2 but used with slight variations in later sections; a single consolidated definition early in the paper would reduce ambiguity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We are grateful to the referee for their careful reading of the manuscript and for the positive recommendation of minor revision. The results are presented as conditional on the existence of a definable well-order, as noted in the referee summary. We address the single major comment below.

read point-by-point responses

  1. Referee: [§3, Theorem 3.5] §3, Theorem 3.5: The construction of the lexicographically minimal coloring with respect to the Δ¹_n well-order is claimed to be Δ¹_n-measurable, but the argument does not explicitly verify that the well-order selects a coloring that remains within the pointclass when the graph has vertices of arbitrary countable degree; this step is load-bearing for the equality χ_Δ¹_n(G) = χ(G).

    Authors: We thank the referee for identifying this point in the proof of Theorem 3.5. The construction defines the coloring c by assigning to each vertex x the least element (in the Δ¹_n well-order) of the set of colors not used by any neighbor of x. Because G is locally countable and Δ¹_n-definable, the forbidden colors at x form a countable set whose enumeration is Δ¹_n-uniform in x. The well-order then selects the minimal such color via a Δ¹_n predicate. We agree that the manuscript would benefit from an explicit paragraph spelling out this uniformization step and confirming that the resulting function c remains Δ¹_n-measurable even when degrees are unbounded. We will insert this clarification in the revised version of §3; the theorem statement itself is unaffected. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central result is stated as an explicit implication from the external hypothesis of a Δ¹_n-definable well-order of the reals (n≥2) to the equality χ_Δ¹_n(G)=χ(G) for locally countable Δ¹_n-definable graphs (and the analogous Δ¹_2 case for Borel graphs). This does not reduce the conclusion to the inputs by definition or construction; the well-order is a non-trivial set-theoretic assumption not derived from the chromatic numbers themselves. No load-bearing self-citations, fitted parameters renamed as predictions, or ansatzes smuggled via prior work are present in the stated claim. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard ZFC set theory plus the additional assumption of definable well-orders of the reals; no free parameters or invented entities appear in the abstract.

axioms (2)
  • standard math ZFC set theory
    Background foundation for all definitions and proofs in descriptive set theory.
  • domain assumption Existence of a Δ¹_n-definable well-order of the reals
    Key hypothesis used to derive the equality χ_Δ¹_n(G) = χ(G); stated explicitly in the abstract as the premise for the implications.

pith-pipeline@v0.9.0 · 5431 in / 1448 out tokens · 67390 ms · 2026-05-08T13:05:56.135163+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 3 Pith papers

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

  1. A locally countable graph of second projective class not generated by countably many projective functions

    math.LO 2026-05 unverdicted novelty 8.0

    A model of set theory is defined in which a countable Π¹₂ equivalence relation on a subset of the reals is not generated by projective functions.

  2. A locally countable graph of second projective class not generated by countably many projective functions

    math.LO 2026-05 conditional novelty 8.0

    A model of set theory exists with a countable Π¹₂ equivalence relation on reals not generated by countably many projective functions.

  3. A locally countable graph of second projective class not generated by countably many projective functions

    math.LO 2026-05 unverdicted novelty 7.0

    A model of set theory is defined in which a countable Π¹₂ equivalence relation on a subset of the reals is not generated by any countable family of projective or ROD functions.

Reference graph

Works this paper leans on

4 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    Bernshteyn, Descriptive Combinatorics and Distributed Algo- rithms, Notices of the American Mathematical Society 69.09 (2022)

    [Ber] A. Bernshteyn, Descriptive Combinatorics and Distributed Algo- rithms, Notices of the American Mathematical Society 69.09 (2022). [Con] C. T. Conley, A. S. Kechris, Measurable chromatic and independence numbers for ergodic graphs and group actions , Groups, Geometry, and Dynamics 7.1 (2013), 127–180. [FFZ] V. Fischer, S. D. Friedman, L. Zdomskyy, Ca...

    2022

  2. [2]

    Kanovei, V

    [KaV] V. Kanovei, V. Lyubetsky, Counterexamples to countable-section Π1 2 uniformization and Π1 3 separation, Annals of Pure and Applied Logic 167.3 (2016), 262–283. Projective Chromatic Numbers 21 [Kec] A. Kechris, Classical descriptive set theory , Springer Science & Busi- ness Media,

    2016

  3. [3]

    Kechris, S

    [KST] A. Kechris, S. Solecki, S. Todorevic, Borel Chromatic Numbers , https://core.ac.uk/download/pdf/82238512.pdf (1999). [Lyu] V. Lubetsky, The existence of a nonmeasurable set of type 𝐴2 implies the existence of an uncountable set of type 𝐶𝐴 that does not contain a perfect subset, Doklady Akademii Nauk SSSR 195 (1971), 548–550. Translated in Soviet Mat...

    work page arXiv 1999

  4. [4]

    [Sol] R. M. Solovay, The cardinality of Σ1 2 sets of reals , In: J. J. Bulloff, T. C. Holyoke, and S. W. Hahn (eds.) Foundations of Mathematics . Symposium papers celebrating the sixtieth birthday of Kurt Gödel. Berlin, Springer-Verlag, 1969

    1969