Measurable Brooks's Theorem for Directed Graphs

Cecelia Higgins

arxiv: 2405.00991 · v4 · pith:S2JPBV34new · submitted 2024-05-02 · 🧮 math.LO · math.CO

Measurable Brooks's Theorem for Directed Graphs

Cecelia Higgins This is my paper

Pith reviewed 2026-05-24 01:36 UTC · model grok-4.3

classification 🧮 math.LO math.CO

keywords Borel directed graphsBrooks's theoremmeasurable dicoloringsGallai's theoremdescriptive set theoryBaire measurable coloringslist dicolorings

0 comments

The pith

Borel directed graphs of maximum degree d admit measurable d-dicolorings unless they contain the complete symmetric digraph on d+1 vertices.

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

The paper proves a measurable version of Brooks's theorem for directed graphs in the descriptive set theory setting. It establishes that any Borel directed graph on a standard Borel space with maximum degree at most d (for d at least 3) has a d-dicoloring that is measurable with respect to every Borel probability measure and Baire measurable with respect to every compatible Polish topology, provided it avoids one specific forbidden subgraph. This matters for a reader interested in graph coloring because it guarantees the existence of colorings that respect the underlying measurable or topological structure rather than requiring the axiom of choice alone. The result also includes a related statement that Borel directed graphs whose components are not Gallai trees are Borel degree-list-dicolorable.

Core claim

If D is a Borel directed graph on a standard Borel space X with maximum degree at most d greater than or equal to 3, and D does not contain the complete symmetric directed graph on d+1 vertices, then D admits a mu-measurable d-dicoloring for any Borel probability measure mu on X and a tau-Baire-measurable d-dicoloring for any Polish topology tau compatible with the Borel structure on X.

What carries the argument

A mu-measurable d-dicoloring (a coloring measurable with respect to a given Borel probability measure) or tau-Baire-measurable d-dicoloring (measurable in the Baire sense for a compatible Polish topology), which the Borel assumption on D makes possible.

If this is right

Borel directed graphs of bounded degree that avoid the forbidden subgraph have colorings definable from the Borel structure.
The same graphs admit list dicolorings when their connected components are not Gallai trees.
The theorem applies uniformly across all measures and all compatible topologies on the underlying space.
Classical Brooks and Gallai theorems for directed graphs lift to the measurable and Baire settings without additional set-theoretic assumptions.

Where Pith is reading between the lines

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

The result suggests that similar measurable lifts may exist for other classical theorems on directed graph colorings.
It connects the problem of measurable dicolorings to questions about the structure of connected components in Borel graphs.
One could test whether the d >= 3 condition can be relaxed or whether the forbidden subgraph is the only obstruction in the measurable category.

Load-bearing premise

The directed graph must be a Borel subset of the product space X times X.

What would settle it

A concrete Borel directed graph of maximum degree d that avoids the complete symmetric digraph on d+1 vertices yet possesses no mu-measurable d-dicoloring for some Borel probability measure mu.

read the original abstract

We prove a descriptive version of Brooks's theorem for directed graphs. In particular, we show that, if $D$ is a Borel directed graph on a standard Borel space $X$ such that the maximum degree of each vertex is at most $d \geq 3$, then unless $D$ contains the complete symmetric directed graph on $d + 1$ vertices, $D$ admits a $\mu$-measurable $d$-dicoloring with respect to any Borel probability measure $\mu$ on $X$, and $D$ admits a $\tau$-Baire-measurable $d$-dicoloring with respect to any Polish topology $\tau$ compatible with the Borel structure on $X$. We also prove a definable version of Gallai's theorem on list dicolorings for directed graphs by showing that any Borel directed graph of bounded degree whose connected components are not Gallai trees is Borel degree-list-dicolorable.

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 lifts the combinatorial Brooks theorem for digraphs to the measurable and Baire settings for Borel graphs, plus a companion Gallai list result.

read the letter

The core result is that a Borel directed graph on a standard Borel space with maximum degree at most d (d at least 3) admits a measurable d-dicoloring for any Borel probability measure, and a Baire-measurable one for any compatible Polish topology, unless it contains the symmetric complete digraph on d+1 vertices. It also gives a Borel list-dicoloring version of Gallai's theorem when components are not Gallai trees. Both statements appear new in the descriptive combinatorics literature for directed graphs. The work does the straightforward thing well: it takes the known finite combinatorial facts and carries them over under the usual Borel hypothesis that lets measurable colorings exist. The proof strategy is not visible in the abstract, but the statement itself is clean and matches the pattern of prior undirected measurable Brooks theorems. No internal contradictions or choice-principle issues jump out from the claim. The main soft spot is that we only have the abstract, so it is impossible to check how the directed case is handled in the actual argument or whether any extra technical lemmas are needed beyond the undirected toolkit. This is minor for a first read. The paper is aimed at people working in descriptive set theory and measurable graph theory. It is the sort of targeted extension that deserves a serious referee rather than a desk reject, even if the proofs turn out to need tightening.

Referee Report

0 major / 2 minor

Summary. The paper proves a descriptive-set-theoretic version of Brooks's theorem for directed graphs: if D is a Borel directed graph on a standard Borel space X with maximum degree at most d ≥ 3, then unless D contains the complete symmetric directed graph on d+1 vertices, D admits a μ-measurable d-dicoloring for any Borel probability measure μ on X and a τ-Baire-measurable d-dicoloring for any compatible Polish topology τ. It also establishes a Borel version of Gallai's theorem, showing that any Borel directed graph of bounded degree whose connected components are not Gallai trees is Borel degree-list-dicolorable.

Significance. If the proofs are correct, the result provides a direct, general lift of the classical directed Brooks theorem into the measurable and Baire settings, which is a standard and useful contribution in descriptive combinatorics. The generality with respect to arbitrary measures and topologies, together with the companion Gallai-list result, strengthens the toolkit for studying definable colorings of Borel digraphs. No free parameters or ad-hoc axioms appear in the statement.

minor comments (2)

[§1] §1, first paragraph after the statement of the main theorem: the phrase 'complete symmetric directed graph' is used without an explicit definition or reference to the standard notation for the bidirected complete digraph; adding a parenthetical clarification would improve readability for readers outside the immediate subfield.
[§4] The proof of the Gallai-list result (presumably in §4 or §5) relies on the same Borel selection techniques as the Brooks result; a short remark comparing the two arguments would help readers see the extent of the overlap.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The report contains no major comments requiring a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents a direct existence proof in descriptive set theory for a measurable version of Brooks's theorem on directed graphs. The central result follows from the Borel hypothesis on the graph (standard for permitting measurable selections) combined with combinatorial arguments lifted from the classical theorem; no equations, fitted parameters, or predictions appear that reduce by construction to the inputs. No self-citation chains or ansatzes are load-bearing for the main claim, and the Gallai-list-coloring extension is likewise a direct definable lift. The derivation is therefore self-contained against external combinatorial and descriptive-set-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard framework of Borel sets, Polish spaces, and Borel probability measures; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract statement.

axioms (2)

standard math Existence of standard Borel spaces and Borel probability measures on them
Invoked to define the setting in which measurability of the coloring is required.
standard math Compatibility of Polish topologies with the Borel structure
Used to state the Baire-measurable coloring result.

pith-pipeline@v0.9.0 · 5679 in / 1418 out tokens · 30406 ms · 2026-05-24T01:36:17.725709+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.

Theorem 1.6: Borel digraph of max degree ≤ d ≥ 3 admits μ-measurable d-dicoloring unless it contains the complete symmetric digraph on d+1 vertices.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

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

Proofs rely on one-ended Borel functions and layer-by-layer list updates (Theorem 4.3, Prop 4.5).

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

2 extracted references · 2 canonical work pages

[1]

Brandt, Y

[BCG+24] S. Brandt, Y. J. Chang, J. Greb´ ık, C. Grunau, V. Rozhoˇ n, and Z. Vidny´ anszky,On homomor- phism graphs, Forum Math. Pi12(2024), e10. [Ber19] A. Bernshteyn,Measurable versions of the Lov´ asz local lemma and measurable graph colorings, Adv. Math.353(2019), 153–223. [Ber23] ,Distributed algorithms, the Lov´ asz local lemma, and descriptive comb...

work page 2024
[2]

[KST99] A. S. Kechris, S. Solecki, and S. Todorˇ cevi´ c,Borel chromatic numbers, Adv. Math.141(1999), 1–44. [Mar16] A. Marks,A determinacy approach to Borel combinatorics, J. Amer. Math. Soc.29(2016), 579–600. [Mar17] ,Uniformity, universality, and computability theory, J. Math. Log.17(2017), 1–50. MEASURABLE BROOKS’S THEOREM FOR DIRECTED GRAPHS 19 [Moh0...

work page arXiv 1999

[1] [1]

Brandt, Y

[BCG+24] S. Brandt, Y. J. Chang, J. Greb´ ık, C. Grunau, V. Rozhoˇ n, and Z. Vidny´ anszky,On homomor- phism graphs, Forum Math. Pi12(2024), e10. [Ber19] A. Bernshteyn,Measurable versions of the Lov´ asz local lemma and measurable graph colorings, Adv. Math.353(2019), 153–223. [Ber23] ,Distributed algorithms, the Lov´ asz local lemma, and descriptive comb...

work page 2024

[2] [2]

[KST99] A. S. Kechris, S. Solecki, and S. Todorˇ cevi´ c,Borel chromatic numbers, Adv. Math.141(1999), 1–44. [Mar16] A. Marks,A determinacy approach to Borel combinatorics, J. Amer. Math. Soc.29(2016), 579–600. [Mar17] ,Uniformity, universality, and computability theory, J. Math. Log.17(2017), 1–50. MEASURABLE BROOKS’S THEOREM FOR DIRECTED GRAPHS 19 [Moh0...

work page arXiv 1999