{"id":"7e382518-d2a8-4e14-8ebe-61814ef2c4da","arxiv_id":"2509.01948","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Locally countable Borel directed graphs with finite Borel chromatic number admit Borel quasi-kernels; a new proof yields the known (n+1)(n+2)/2 chromatic bound for out-degree n.","lead":"This paper proves that any locally countable Borel directed graph with a finite proper coloring contains a Borel set of vertices that is independent and reaches every other vertex within two directed steps. It also gives a new, simpler proof of a known bound on the Borel chromatic number of out-degree-n graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The proof is self-contained and correct in its main steps. The only possible weak point is the reliance on Lusin-Novikov for Borelness of T and A', but this is exactly what local countability provides and is standard. I found no gap in the induction, independence, recurrence, or the later chromatic-number arguments. The paper's minor typos and compressed arguments (e.g., Proposition 3.2 coloring) do not change the conclusion. The reader's verdict ACCEPT with moderate confidence is appropriate.","tokens_in":5654,"tokens_out":30493,"duration_ms":339050,"concrete_test":"Exhaustively verify the purely finite analogue: for every directed graph on ≤5 vertices and every proper coloring, run the construction in Theorem 3.1 (A=color class, T, induction on D[T]) and confirm the output M is independent and satisfies ρ(x,M)≤2 for all x. This isolates the combinatorial core from Borel technicalities.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. I checked the central induction in Theorem 3.1: T and A' are Borel by Lusin-Novikov because D is locally countable; D[T] inherits local countability and has a Borel k-coloring, so the induction applies; the independence and gap-2 arguments cover all cases. The later Theorems 4.1 and 4.2 follow cleanly from Theorem 1.2, with only minor omissions such as the implicit case split when χB is infinite in Theorem 4.2 and typos like ρ(x,T) for ρ(x,T'), neither of which affects correctness.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5853,"tokens_out":17660,"duration_ms":172651,"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.","major_comments":[],"minor_comments":[{"comment":"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":"Section 3, proof of Theorem 3.1"},{"comment":"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":"Section 4, proof of Theorem 4.1"},{"comment":"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":"Section 4, Proposition 3.2"},{"comment":"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":"Section 4, proof of Theorem 4.2"},{"comment":"There are several typographical errors: 'chormatic' should be 'chromatic', and 'considerd' should be 'considered'. These should be corrected in revision.","section":"Section 1"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Ruijun Wang's paper has one genuinely new result: Theorem 1.2, the existence of a Borel quasi-kernel (independent, recurrent with gap 2) in any locally countable Borel digraph with finite Borel chromatic number. That improves Higgins' earlier gap chi_B+1. The proof, a straightforward induction on chi_B, checks out. The sets T and A' are Borel via Lusin-Novikov, the independence argument covers the three possible edge cases, and the gap-2 case split is exhaustive. The paper is honest that the chromatic bound in Theorem 1.1 is not new: it is an alternative proof of Palamourdas' theorem, and for n>=4 the Meehan-Palamourdas bound is better. So the contribution is the quasi-kernel theorem plus a clean route to the known bound.\n\nThe later sections are mostly fine. Proposition 3.2, giving the equivalence between finite chi_B, existence of an independent recurrent set, and chi_B<=3 for function-generated digraphs, is a nice touch. The induction in Theorem 4.1 uses out-degree reductions correctly: vertices at distance 2 from M' must have their out-neighbor outside A, so the out-degree drops. The largest gap is a missing one-line justification in the base case n=1: the claim that N^-(M') is independent is true only because a vertex at distance 1 from M' must have its unique out-neighbor in M', so two such vertices cannot be adjacent. Without that note the statement looks false in general (it is false for higher out-degree). Also, Theorem 4.2 does not explicitly split on chi_B(D)=infinity before applying Theorem 4.1; that's implicit and harmless. There are minor typos ('chormatic', rho(x,T) for rho(x,T')). None of this affects the central result.\n\nWho benefits: descriptive combinatorists working on Borel kernels or chromatic numbers of directed graphs. The main theorem is worth knowing, and the proof is short enough to include in a lecture. I'd send it to a serious referee; after a small revision to clarify the N^-(M') point, it should be acceptable.","headline":"Clean new proof of Borel quasi-kernel for finite Borel chromatic number; the chromatic-bound part is an alternative proof of a known result.","tokens_in":6283,"tokens_out":8204,"would_cite":true,"duration_ms":89567,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03E15","05C15","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["Borel quasi-kernel","Borel chromatic number","locally countable Borel directed graph","bounded out-degree","recurrent set","independent set","descriptive combinatorics","Borel uniformization"],"falsifier":"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.","tokens_in":5612,"feed_emoji":"📐","tokens_out":8539,"duration_ms":82363,"temperature":0.7,"texified_at":"2026-08-05T20:21:38.906792+00:00","pith_summary":"Directed graphs that are Borel can be colored with countably many colors, but a good coloring alone does not give a small independent set that is close to every vertex. This paper proves that any locally countable Borel directed graph whose underlying graph has finite Borel chromatic number contains a Borel quasi-kernel: an independent set $A$ such that every vertex reaches $A$ by a directed path of length at most two. That improves the earlier guarantee of a gap equal to the chromatic number plus one, replacing a number that can grow with the graph by the fixed constant two. The same construction gives an alternative proof of a known bound: a Borel directed graph of bounded out-degree $n$ either has infinite Borel chromatic number or has Borel chromatic number at most $\\frac{(n+1)(n+2)}{2}$.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":5555,"prompt_tokens":785,"completion_tokens":4770,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":785,"completion_tokens_details":{"reasoning_tokens":4006}},"feed_headline":"A quasi-kernel exists in every finite-color Borel directed graph","feed_subtitle":"A recursive coloring argument cuts the guaranteed distance to an independent set from chromatic-number-plus-one down to two.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces Borel chromatic numbers, the n+1 bound for bounded degree, and the question about functions with out-degree n.","marker":"[7]"},{"why":"Earlier result giving an independent recurrent Borel set with bounded gap chi_B+1, which Theorem 1.2 improves.","marker":"[4]"},{"why":"The theorem giving the (n+1)(n+2)/2 bound that the paper reproves via its quasi-kernel theorem.","marker":"[10]"},{"why":"Supplies the uniformization theorem that makes the sets T and A' Borel in the induction.","marker":"[5]"},{"why":"Establishes the finite directed graph quasi-kernel theorem whose Borel analogue is Theorem 1.2.","marker":"[1]"},{"why":"Improves the chromatic bound for n at least 4 and is the target the open out-degree-2 question would further improve.","marker":"[9]"}],"fun_headline_variants":["Borel quasi-kernel found in any finite-chromatic digraph","Finite Borel chromatic number guarantees a quasi-kernel","New proof: Borel quasi-kernels in locally countable graphs","Out-degree bound yields Borel chromatic number limit"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Borel quasi-kernel found in any finite-chromatic digraph","Finite Borel chromatic number guarantees a quasi-kernel","New proof: Borel quasi-kernels in locally countable graphs","Out-degree bound yields Borel chromatic number limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000171,"raw_usage":{"total_tokens":1042,"prompt_tokens":611,"completion_tokens":431,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":355,"completion_tokens_details":{"reasoning_tokens":362}},"tokens_in":355,"tokens_out":431,"duration_ms":4662,"temperature":1.0,"reasoning_tokens":362,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:01:41.215363+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Kechris, Classical Descriptive Set Theory","cited_arxiv_id":null,"evidence_quote":"Introduces Borel chromatic numbers, the n+1 bound for bounded degree, and the question about functions with out-degree n."},{"cited_title":"Gao, Invariant Descriptive Set Theory","cited_arxiv_id":null,"evidence_quote":"Earlier result giving an independent recurrent Borel set with bounded gap chi_B+1, which Theorem 1.2 improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The theorem giving the (n+1)(n+2)/2 bound that the paper reproves via its quasi-kernel theorem."},{"cited_title":"Haynes, S","cited_arxiv_id":null,"evidence_quote":"Supplies the uniformization theorem that makes the sets T and A' Borel in the induction."},{"cited_title":"Chv\\' a tal, L","cited_arxiv_id":null,"evidence_quote":"Establishes the finite directed graph quasi-kernel theorem whose Borel analogue is Theorem 1.2."},{"cited_title":"Kechris, S","cited_arxiv_id":null,"evidence_quote":"Improves the chromatic bound for n at least 4 and is the target the open out-degree-2 question would further improve."}],"review_version":1}