pith. sign in

arxiv: 2604.02589 · v1 · submitted 2026-04-02 · 🧮 math.LO · math.CO

A Concise Proof of the L₀ Dichotomy

Tonatiuh Matos-Wiederhold This is my paper

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

classification 🧮 math.LO math.CO
keywords L0 dichotomyBorel chromatic numbercontinuous homomorphismsigma-idealFirst Reflection TheoremG0 dichotomyanalytic graphsfinite path approximations
0
0 comments X

The pith

A new proof shows that one fixed Borel graph of chromatic number three admits a continuous homomorphism into every analytic graph of chromatic number at least three.

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

The paper proves the L0 dichotomy by constructing a continuous homomorphism from a canonical Borel graph Lc into any analytic graph G whose Borel chromatic number is at least three. It does so by importing Bernshteyn's graph-theoretic method for the G0 dichotomy and replacing the original transfinite construction with a single Borel reflection argument. The central device is a sigma-ideal whose small sets consist of homomorphisms from finite path approximations that satisfy a bounded odd-walk condition on their vertex projections. Largeness of a family is shown to be preserved under a doubling operation, allowing the desired homomorphism to be recovered as the limit of a shrinking sequence of large families.

Core claim

There exists a Borel graph Lc of Borel chromatic number three such that for every analytic graph G with Borel chromatic number at least three there is a continuous homomorphism from Lc to G. The proof obtains this homomorphism as the limit of shrinking families of copies inside a sigma-ideal of small homomorphisms from finite path approximations, where smallness is witnessed by a bounded odd-walk condition; the key preservation of largeness under doubling follows directly from the First Reflection Theorem.

What carries the argument

The sigma-ideal of small sets of homomorphisms from finite path approximations into the target graph, with smallness witnessed by a bounded odd-walk condition on vertex projections.

If this is right

  • The L0 dichotomy holds without any transfinite analysis of decreasing omega1-sequences of analytic sets.
  • The continuous homomorphism is recovered directly as the limit of the shrinking large families once the sigma-ideal is in place.
  • The same reflection argument that works for G0 also works for L0, unifying the two dichotomies under one graph-theoretic framework.
  • Any target graph of Borel chromatic number at least three must contain a continuous copy of Lc obtained by iterating the doubling step.

Where Pith is reading between the lines

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

  • The bounded odd-walk condition may simplify homomorphism constructions for other Borel graphs beyond L0 and G0.
  • If the First Reflection Theorem applies uniformly, similar sigma-ideals could shorten proofs of related dichotomies in descriptive set theory.
  • The method suggests that chromatic-number thresholds in analytic graphs are controlled by the same finite-path approximation structure used here.

Load-bearing premise

Largeness is preserved under the doubling operation by exactly the same application of the First Reflection Theorem used in the G0 case, without extra set-theoretic assumptions or case distinctions.

What would settle it

A concrete analytic graph G of Borel chromatic number three for which no continuous homomorphism from Lc exists, or an explicit family whose largeness fails to be preserved by the doubling operation despite satisfying the bounded odd-walk condition.

Figures

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

Figure 1
Figure 1. Figure 1: L c 3 for c(0) = 1, c(1) = 3, c(2) = 5. To develop some intuition on what (iii) says about a vertex v in L c n : the number |v| − 1 indicates that v was added that many stages ago in the recursion, at the position of pk in the path joining the two copies of the previous paths; the sequence t tells the story, in order, of which of the two [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

Carroy, Miller, Schrittesser, and Vidny\'anszky established the $L_0$ dichotomy: there is a Borel graph of Borel chromatic number three that admits a continuous homomorphism to every analytic graph of Borel chromatic number at least three. Their proof relies on a transfinite analysis of terminal approximations over a decreasing $\omega_1$-sequence of analytic sets. I give a new, substantially shorter proof of this result by adapting the graph-theoretic framework recently introduced by Bernshteyn for the $G_0$ dichotomy. The central device is a $\sigma$-ideal of \emph{small} sets of homomorphisms from finite path approximations into the target graph, where smallness is witnessed by a bounded odd-walk condition on vertex projections. The key lemma that largeness is preserved under the doubling operation is established via the First Reflection Theorem, replacing the original transfinite construction with a single Borel reflection argument. The continuous homomorphism from the canonical graph $\mathbb{L}_c$ into the target is then obtained as a limit of shrinking families of copies, in direct analogy with Bernshteyn's proof for $G_0$.

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

2 major / 2 minor

Summary. The paper presents a concise proof of the L0 dichotomy: there exists a Borel graph of Borel chromatic number 3 that admits a continuous homomorphism into every analytic graph of Borel chromatic number at least 3. It adapts Bernshteyn's graph-theoretic framework from the G0 case by introducing a σ-ideal of small sets of homomorphisms from finite path approximations into the target graph, where smallness is witnessed by a bounded odd-walk condition on vertex projections. The key lemma establishes that largeness is preserved under the doubling operation via a single application of the First Reflection Theorem, allowing the continuous homomorphism from Lc to be constructed as a limit of shrinking large families, thereby replacing the original transfinite analysis over an ω1-sequence of analytic sets.

Significance. If the central adaptation holds, the result is significant for providing a substantially shorter proof that avoids transfinite constructions and highlights the portability of Bernshteyn's framework across different chromatic-number dichotomies in descriptive set theory. The approach replaces a lengthy case analysis with a single Borel reflection argument, which—if verified—strengthens the conceptual unity between the G0 and L0 results without introducing new parameters or ad-hoc axioms.

major comments (2)
  1. [Key lemma and doubling operation] Key lemma (largeness preserved under doubling): The claim that the bounded odd-walk condition on projections allows the First Reflection Theorem to apply directly, without L0-specific case distinctions arising from 3-chromatic targets or potentially unbounded odd walks in finite-path projections, must be verified explicitly. This step is load-bearing because the continuous homomorphism from Lc is obtained as the limit of repeated doublings of large families; any gap here would require reverting to transfinite methods or additional analytic-set distinctions not present in the G0 adaptation.
  2. [Definition of the σ-ideal] Definition of the σ-ideal (§ on small sets of homomorphisms): It is not immediate that the bounded odd-walk condition generates a σ-ideal closed under the relevant operations for 3-chromatic graphs; an explicit check that countable unions of small sets remain small (or that the ideal property interacts correctly with the path-approximation projections) is needed to ensure the reflection argument goes through without hidden assumptions.
minor comments (2)
  1. [Notation and definitions] Notation: Ensure Lc is defined and used consistently when referring to the canonical graph, and clarify the precise meaning of 'finite path approximations' at first use.
  2. [Introduction] References: Include an explicit citation to Bernshteyn's G0 paper at the point where the framework is first adapted, rather than only in the abstract.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the detailed comments. The points raised about the key lemma and the definition of the σ-ideal are substantive and have prompted us to strengthen the exposition. We address each major comment below and have revised the manuscript to include the requested explicit verifications.

read point-by-point responses

  1. Referee: [Key lemma and doubling operation] Key lemma (largeness preserved under doubling): The claim that the bounded odd-walk condition on projections allows the First Reflection Theorem to apply directly, without L0-specific case distinctions arising from 3-chromatic targets or potentially unbounded odd walks in finite-path projections, must be verified explicitly. This step is load-bearing because the continuous homomorphism from Lc is obtained as the limit of repeated doublings of large families; any gap here would require reverting to transfinite methods or additional analytic-set distinctions not present in the G0 adaptation.

    Authors: The bounded odd-walk condition is formulated so that the projections of the homomorphism sets remain analytic and satisfy the hypotheses of the First Reflection Theorem uniformly. In the proof of the key lemma (Lemma 3.5), the condition ensures that any odd walk in the finite-path projections is bounded independently of the specific target graph, so the 3-chromatic case introduces no additional distinctions beyond those already controlled in the G0 setting. The doubling operation preserves largeness precisely because the reflection applies to the analytic set defined by the existence of an unbounded walk, which is ruled out by the smallness witness. We have added a new explanatory paragraph immediately following the statement of Lemma 3.5 that spells out this uniformity and the absence of case distinctions. revision: yes

  2. Referee: [Definition of the σ-ideal] Definition of the σ-ideal (§ on small sets of homomorphisms): It is not immediate that the bounded odd-walk condition generates a σ-ideal closed under the relevant operations for 3-chromatic graphs; an explicit check that countable unions of small sets remain small (or that the ideal property interacts correctly with the path-approximation projections) is needed to ensure the reflection argument goes through without hidden assumptions.

    Authors: We agree that the σ-ideal property requires explicit confirmation. Section 2 defines a set of homomorphisms to be small when there exists a fixed natural number N such that every homomorphism in the set has no odd walk longer than N on its vertex projections. We have inserted a new Lemma 2.4 that verifies closure under countable unions: given a countable family of small sets with respective bounds N_k, the union is small with bound max{N_k : k < ω} when the family arises from the doubling construction (the finite length of the path approximations ensures only finitely many distinct bounds appear in each relevant collection). The interaction with path-approximation projections is checked directly by observing that the projection maps preserve the odd-walk bound. This explicit verification has been added to the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity; adapts external Bernshteyn framework and standard First Reflection Theorem

full rationale

The derivation adapts Bernshteyn's external graph-theoretic framework for G0 and invokes the standard First Reflection Theorem to obtain the key lemma on largeness preservation under doubling. The continuous homomorphism from Lc is constructed as a limit of shrinking families in direct analogy with the cited external argument. No equation or step reduces the target statement to a quantity defined inside the paper, no self-citation chain is load-bearing, and no fitted parameter is renamed as a prediction. The argument remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The proof relies on standard ZFC set theory plus the First Reflection Theorem for analytic sets. No new free parameters are introduced; the sigma-ideal is defined from the target graph and the odd-walk condition. The only invented device is the specific notion of smallness via bounded odd walks, which is internal to the argument and has no independent evidence outside the proof.

axioms (1)
  • standard math First Reflection Theorem for analytic sets
    Invoked to establish that largeness is preserved under doubling without transfinite induction.
invented entities (1)
  • sigma-ideal of small sets of homomorphisms no independent evidence
    purpose: To replace the transfinite sequence of terminal approximations with a single reflection argument
    Defined by the bounded odd-walk condition on vertex projections; no external falsifiable prediction is given.

pith-pipeline@v0.9.0 · 5500 in / 1517 out tokens · 46697 ms · 2026-05-13T19:44:52.009929+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

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

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

7 extracted references · 7 canonical work pages

  1. [1]

    The G_0 -dichotomy

    Anton Bernshteyn. The G_0 -dichotomy. https://bahtoh-math.github.io/resources/KST.pdf, 2024. Accessed: 2024-08-27

    work page 2024

  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]

    Alexander S. Kechris. Classical Descriptive Set Theory . Springer-Verlag, New York, 1995

    work page 1995

  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. The graph-theoretic approach to descriptive set theory. The Bulletin of Symbolic Logic , 18:554--575, 2012

    work page 2012

  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

    work page 1982

  7. [7]

    Borel order dimension

    Dilip Raghavan and Ming Xiao. Borel order dimension. arXiv preprint arXiv:2409.06516, September 10 2024. Submitted 10 September 2024; version 1. URL: https://arxiv.org/abs/2409.06516

    work page arXiv 2024