REVIEW 5 minor 13 references
Borel Kernels in Borel Directed Graphs
T0 review · 0 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read The paper proves that every locally countable Borel directed graph with finite Borel chromatic number has a Borel quasi-kernel—an independent set from which every vertex is at directed distance at most two—and uses this to reprove the known
desk verdict Clean new proof of Borel quasi-kernel for finite Borel chromatic number; the chromatic-bound part is an alternative proof of a known result. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is an induction on the Borel chromatic number that trims the lowest color class around a smaller quasi-kernel. The set $T$ of vertices outside the color-0 class $A$ that do not point into $A$ is Borel by local countability, so the induction applies to it. After obtaining its quasi-kernel $T'$, the proof defines $A'$ as the vertices of $A$ that point into $T'$ and discards them; this single deletion is what destroys all edges between the two independent pieces. The distance-to-$M$ argument then splits into the two structural cases, giving the bounded gap of 2 without any further coloring.
What would settle it
Run the construction on a locally countable Borel directed graph with Borel chromatic number 2, say the directed Schreier graph of the free part of the Bernoulli shift of the two-generator free group. The theorem predicts the trimmed set $M$ is independent and every vertex reaches it in at most two directed steps; a vertex at directed distance 3 would disprove it. For the numerical bound, an out-degree-2 Borel directed graph with Borel chromatic number 7 (or an out-degree-$n$ graph exceeding $\frac{(n+1)(n+2)}{2}$) would be a direct counterexample.
Extended reading notes
Core claim
Let $D$ be a locally countable Borel directed graph with Borel chromatic number $k+1$. The proof fixes a Borel proper coloring, takes $A$ to be the color-0 class, and lets $T$ be the set of vertices outside $A$ with no outgoing arc into $A$. By the induction hypothesis, the induced subgraph on $T$ has a Borel quasi-kernel $T'$. The paper then removes from $A$ all vertices that send an arc into $T'$, forming $A'$, and takes $M=(A\setminus A')\cup T'$. Independence holds because no arc runs from $A\setminus A'$ into $T'$ by definition of $A'$, and no arc runs from $T'$ into $A$ by definition of $T$. For recurrence, a vertex outside $M$ either lies in $T$ and uses the inductive gap-2 guarantee to reach $T'$, or lies outside $T$ and has an arc into $A$; if that
Load-bearing premise
The load-bearing premise is that the graph is locally countable and Borel, so the standard uniformization theorem for countable Borel relations guarantees that the sets $T$ and $A'$ built during the induction are Borel; if that premise gives way, the construction may stop being Borel.
Editorial extensions
If this is right
- Every locally countable Borel directed graph with finite Borel chromatic number has a Borel independent set that every vertex reaches in at most two directed steps, replacing the previous gap of chromatic number plus one.
- For a Borel directed graph generated by one Borel function, finite Borel chromatic number is equivalent to having an independent recurrent Borel set, and forces Borel chromatic number at most 3.
- For bounded out-degree n, there is a Borel set M with Borel chromatic number at most n+1 that dominates the whole graph at directed distance 1.
- Iterating that domination set gives the known bound (n+1)(n+2)/2 for Borel chromatic number of bounded out-degree n, as an alternative proof.
Reading between the lines
- The trimming construction is modular: the finite chromatic number only provides the starting coloring, so the same recursive step may transfer to other regularity notions (measurable, Baire property, or generic) wherever a uniformization theorem supplies the needed Borelness.
- The paper leaves open whether the gap can be reduced further; a positive answer for out-degree 2 would automatically strengthen the chromatic bound for all higher n through the same induction.
- The main theorem concerns quasi-kernels (gap 2), not kernels (gap 1). The examples discussed in the paper suggest that kernels are genuinely harder in the Borel setting, so the contribution is exactly that the fixed gap 2 is the right Borel analogue of the finite-graph semi-kernel theorem.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Borel directed graphs and proves two main results. Theorem 1.2 (Theorem 3.1) states that every locally countable Borel directed graph whose underlying graph has finite Borel chromatic number admits a Borel quasi-kernel: an independent Borel set M such that every vertex is at directed distance at most 2 from M. The proof proceeds by induction on the Borel chromatic number, removing a color class A, considering the set T of vertices outside A with no directed edge into A, and applying the induction hypothesis to the induced subgraph D[T]. Theorem 1.1 (Theorem 4.2) recovers Palamourdas' theorem: if a locally countable Borel directed graph has out-degree at most n, then the Borel chromatic number of its underlying graph is either infinite or at most (n+1)(n+2)/2. This is derived from Theorem 1.2 through a domination lemma (Theorem 4.1) and an induction on n.
Significance. The central result, Theorem 1.2, is a genuine improvement over Higgins' earlier bound, which produced an independent recurrent set with bounded gap chi_B+1. Reducing the gap to the optimal constant 2 for all locally countable Borel digraphs with finite Borel chromatic number is a strong and clean contribution. The proof of Palamourdas' bound is self-contained and considerably simpler than the original route, relying only on standard descriptive set theory, in particular Lusin-Novikov uniformization. The main induction is transparent and can be checked line by line; there are no fitted parameters, no circular dependencies, and no ad-hoc assumptions beyond the stated hypotheses. The paper is concise, but the ideas and formulations are clear.
minor comments (5)
- [Section 3, proof of Theorem 3.1] In the sentence defining T', the displayed assertion 'rho(x,T) <= 2' should read 'rho(x,T') <= 2'; otherwise the condition is vacuous because x itself lies in T. The same section also has 'direct distance' for 'directed distance'.
- [Section 4, proof of Theorem 4.1] The claim that N^-(M') is independent in the base case n=1 is true but requires justification: if x,y in N^-(M') and x -> y, then since x has out-degree at most 1 and must have an out-neighbor in M', one gets y in M', contradicting that M' is independent. Please add this one-line argument.
- [Section 4, Proposition 3.2] The coloring construction in (2) => (3) is terse. As written, 'color their in-neighborhood N^-(A union N^-(A)) by color 2' could suggest coloring all in-neighbors, including those already colored. It should be stated explicitly that at each stage only uncolored vertices are colored, and that a vertex is colored as soon as its unique out-neighbor has already been colored. With that clarification, the independence of each layer and the alternation of colors 1 and 2 gives a proper 3-coloring.
- [Section 4, proof of Theorem 4.2] Before invoking Theorem 4.1, the proof should split off the trivial case chi_B(D~)=infinity; Theorem 4.1 assumes finite Borel chromatic number. Similarly, when applying the induction hypothesis to D' = D[V\M], if chi_B(D~')=infinity then the desired conclusion is immediate. These case splits are implicit and do not affect the argument.
- [Section 1] There are several typographical errors: 'chormatic' should be 'chromatic', and 'considerd' should be 'considered'. These should be corrected in revision.
Circularity Check
No significant circularity; the main theorems are derived from self-contained inductions.
full rationale
The proof chain is self-contained. Theorem 3.1 proves the existence of a Borel quasi-kernel by induction on the finite Borel chromatic number, using only standard Lusin-Novikov uniformization to show that the auxiliary sets T and A′ are Borel. The induction hypothesis is applied to the induced subgraph D[T], whose chromatic number is genuinely one less because the restriction of the original coloring uses only k colors on T. The independence and gap-2 arguments are carried out directly from the definitions. Theorem 4.1 then follows from Theorem 3.1 plus induction on bounded out-degree, and Theorem 4.2 follows from Theorem 4.1 plus induction, with the n=1 case handled by Proposition 3.2. The paper explicitly presents Theorem 1.1 as an alternative proof of Palamourdas' theorem; it does not use Palamourdas' theorem as a premise. Citations to prior work (Kechris–Solecki–Todorcevic, Marks, Palamourdas, Meehan–Palamourdas, Higgins) are contextual or motivational, not load-bearing in the derivations. No fitted parameters, no renaming of known results, and no self-citation chain are present. The stated assumptions (local countability, finite Borel chromatic number, bounded out-degree) are structural hypotheses, not conclusions smuggled into the proof.
Assumptions & free parameters
assumptions (3)
- standard math Lusin-Novikov uniformization: a Borel relation with countable sections has Borel projection
- standard math Borel proper colorings restrict to induced subgraphs
- domain assumption Borel uniformization equivalence: locally countable Borel digraph of out-degree n equals n countable-to-1 Borel functions
Cite this review
Pith. "Pith review of Borel Kernels in Borel Directed Graphs." pith.science (2026). https://pith.science/paper/NUXEI6W2
@misc{pith2026250901948,
author = {Pith},
title = {Pith review of: Borel Kernels in Borel Directed Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/NUXEI6W2}},
note = {Machine review of arXiv:2509.01948}
}
abstract
We prove that there is a Borel quasi-kernel in any locally countable Borel directed graph with finite Borel chromatic number. We prove that the Borel chromatic number of a Borel directed graph with bounded out-degree $n$ is either infinite or less than or equal to $\frac{(n+1)(n+2)}{2}$. This is an alternative proof of Palamourdas' theorem.
Reference graph
Works this paper leans on
-
[1]
V. Chv\' a tal, L. Lov\' a sz, Every directed graph has a semi-kernel. in Hypergraph Seminar, p. 175, Springer, 1974
work page 1974
- [2]
- [3]
-
[4]
Gao, Invariant Descriptive Set Theory
S. Gao, Invariant Descriptive Set Theory. Monographs and Textbooks in Pure and Applied Mathematics, vol. 293, CRC Press, 2009
work page 2009
- [5]
-
[6]
C. Higgins, A note on forward-recurrent sets with bounded gaps, manuscript available at https://sites.google.com/view/cecelia-higgins/home , 2023
work page 2023
-
[7]
Kechris, Classical Descriptive Set Theory
A.S. Kechris, Classical Descriptive Set Theory. Graduate Texts in Mathematics, vol. 156, Springer-Verlag, 1995
work page 1995
-
[8]
A.S. Kechris, A. Marks, Descriptive graph combinatorics, manuscript available at https://www.pma.caltech.edu/documents/5616/combinatorics20book.pdf , 2020
work page 2020
Show all 13 references
-
[9]
Kechris, S
A.S. Kechris, S. Solecki, S. Todorcevic, Borel Chromatic Numbers, Adv. Math. 141 (1999), no.1, 1--44
1999
-
[10]
A. S. Marks, A determinacy approach to Borel combinatorics, J. Amer. Math. Soc. 29 (2016), 579--600
2016
-
[11]
Meehan, K
C. Meehan, K. Palamourdas, Borel chromatic numbers of graphs of commuting functions, Fund. Math. 253 (2021), 219--237
2021
-
[12]
Palamourdas, 1,2,3, ,2n+1, ! , Ph.D
K. Palamourdas, 1,2,3, ,2n+1, ! , Ph.D. Thesis, UCLA, 2012
2012
-
[13]
Richardson, On weakly ordered systems, Bull
M. Richardson, On weakly ordered systems, Bull. Amer. Math. Soc. 52 (1946), 113--116
1946
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.