REVIEW 2 major objections 4 minor 9 references
On the growth rate of dichromatic numbers of finite subdigraphs
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For every prescribed $f$, an uncountably dichromatic digraph of size continuum has all $(n+2)$-dichromatic subdigraphs of size at least $f(n)$; consistently, this holds at every uncountable cardinal up to the continuum.
desk verdict First theorem is clean and worth having; the consistency result, as written, rests on an unproved compatibility argument for tail coordinates in the final forcing iteration. 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 main object is the lexicographic product-like digraph on $V=\prod_{n<\omega}[0,g(n)-1]$, where $uv$ is an edge exactly when at the first coordinate where $u$ and $v$ differ, $v$ moves one step forward modulo the interval length. This coordinatewise structure makes the subdigraph on any cylinder $V_s$ a directed cycle of length $g(|s|)$, which provides the lower bound $f_D\ge f$ via a $2^n$-colouring by sign patterns of the first $n$ coordinates. For the consistency theorem, the mechanism is the poset $P_{\kappa,f}$ of finite digraphs on subsets of $\kappa$ with $f_p\ge f$; the ccc proof and the density proof both use first-order isomorphism of finite structures and semihomomorphisms (maps that preserve edges or identify vertices) to transfer dichromatic-number bounds from one finite condition to unions of conditions. The final iteration is a finite-support ccc iteration of all such factors, with the directed-cycle density argument repeated in the tail.
What would settle it
Try to construct an uncountable set $U$ in the final generic extension with $\chi(D[U])=1$, i.e. $D[U]$ acyclic; Theorem 3.6 asserts none exists, so any such $U$ refutes it. The concrete point to check is the asserted tail-forcing generalization of Lemma 3.11: when conditions are taken from the whole tail forcing rather than one factor, the chosen cycle length $m = n + \max_{k\le n}(f(k+1)-f(k))$ must still guarantee $f_q\ge f$ for the union $q$ of the picked conditions, including their later coordinates.
Extended reading notes
Core claim
The central discovery is that the dichotomy between 'large dichromatic number' and 'large finite thresholds' is flexible in both ZFC and forcing extensions. Theorem 3.1 constructs, for every non-decreasing $g$, a digraph $D$ on the product of finite intervals of lengths $g(n)$ with edges moving to the next residue at the first differing coordinate; this $D$ has $\chi(D)>\aleph_0$ and $f_D\ge f$. Theorem 3.6 then establishes the consistency statement: a ccc forcing of size $c$ preserves cardinals and the continuum, and in the extension, for every uncountable $\kappa\le c$ and every $f$ there is a digraph $D$ on $\kappa$ with $f_D\ge f$ and $\chi(D[U])=|U|$ for every uncountable $U$. In particular, in the extension every such $D$ is $\kappa$-dichromatic. The proof routes the finite-structure control through finite conditions $P_{\kappa,f}$ that satisfy $f_p\ge f$, shows $P_{\kappa,f}$ is ccc via the $\Delta$-system and semihomomorphism arguments, and finally asserts that the cycle-forcing density argument works for the whole tail of the forcing iteration.
Load-bearing premise
Everything rests on the assumption that forcing a directed cycle into every uncountable subset still works after the later stages of the iteration have been added, because the final theorem must cover sets that only appear in the full extension.
Editorial extensions
If this is right
- For every $f:\omega\to\omega$, an uncountably dichromatic digraph of size $2^{\aleph_0}$ exists whose $(n+2)$-dichromatic subdigraphs all have at least $f(n)$ vertices (Theorem 3.1).
- By compactness and disjoint unions, the same growth control is possible for a countably infinite digraph: for every $f$ there is an $\aleph_0$-dichromatic digraph on $\omega$ with $f_D\ge f$ (Remark 3.5).
- There is a ccc forcing of size $c$ preserving cardinals and the continuum such that, in the extension, for every uncountable $\kappa\le c$ and every $f$ there is a $\kappa$-dichromatic digraph on $\kappa$ with $f_D\ge f$ (Theorem 3.6).
- In that extension, every uncountable induced subdigraph $D[U]$ of such a digraph satisfies $\chi(D[U])=|U|$, so the digraphs are optimal in size and every uncountable part is as dichromatic as its cardinality allows.
Reading between the lines
- Beyond the paper: the coordinatewise 'next residue' construction in Theorem 3.1 may yield digraphs that simultaneously control directed girth and all finite dichromatic thresholds, since Observation 3.2 already gives exact digirth bounds on cylinder subdigraphs.
- Beyond the paper: the finite-support iteration of factors $P_{\kappa,f}$ looks like a general template for forcing 'every uncountable subset contains a copy of a finite configuration' properties, since the density argument uses only the initial coordinate of a condition.
- Beyond the paper: a natural question the paper leaves open is whether the ZFC construction can be carried out at cardinal $\aleph_1$ rather than continuum, matching the graph-theoretic result; the product-of-intervals construction is what forces size continuum, so a different method would be needed.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the growth rate of dichromatic numbers of finite subdigraphs of infinite digraphs, in analogy to a recent graph-theoretic theorem of Lambie-Hanson. In the first part, the author gives a ZFC construction, for every function f:ω→ω, of an uncountably dichromatic digraph D of size 2^ℵ0 such that every (n+2)-dichromatic subdigraph of D has at least f(n) vertices. The construction uses a product of directed cycles of prescribed lengths and a colouring argument based on the first coordinate where two vertices differ. In the second part, the author proposes a consistency result (Theorem 3.6): there is a ccc forcing P of size c such that in the extension, for every uncountable cardinal κ≤c and every f:ω→ω, there is a digraph D on κ with f_D≥f and with χ(D[U])=|U| for every uncountable U⊆V(D). The forcing is a finite-support iteration whose factors are posets P_{κ,f} of finite digraphs on κ with prescribed lower bounds for f; the key lemmas show that P_{κ,f} is ccc and that the generic digraph has the required cycle-containment property. The final step claims that this property survives the rest of the iteration by an adaptation of the proof of Lemma 3.11.
Significance. If Theorem 3.6 is correct, it is a strong directed analogue of Lambie-Hanson's recent result, showing that it is consistent with arbitrarily large continuum that for every infinite κ≤c there are κ-dichromatic digraphs of optimal size κ with arbitrarily prescribed slow growth of the dichromatic numbers of finite subdigraphs. The ZFC construction in Section 3.1 is simple and elegant, and the semihomomorphism and Δ-system arguments for the ccc and generic cycle-containment properties are natural and mostly check out. The paper also gives a useful general framework for forcing dichromatic-number statements. However, the proof of the key preservation step across the tail forcing is not supplied, and as written the consistency theorem is not established. The ZFC part appears defensible after a small indexing repair, but the forcing part needs substantial additional argument.
major comments (2)
- [§3.2, final paragraph] The transfer of Lemma 3.11 to the tail forcing P_{≥β} is not justified. In the proof of Lemma 3.11, conditions q_α are chosen so that q_α forces α∈U, then q = C ∪ ⋃ q_i is formed and shown to be a condition in P_{κ,f}. For the analogous argument in the tail forcing, the q_α must also be compatible in all coordinates above β. The name U may depend on the tail coordinates, so one cannot in general force α∈U while setting all tail coordinates equal to those of r. The sentence 'whenever we deal with a condition p in the original proof, we consider now just its initial coordinate p(β)' does not address this compatibility issue, and no argument is given that finitely many chosen q_α have a common extension in P_{≥β}. Since Theorem 3.6 requires the cycle-containment property for uncountable sets U that may be added by the later tail forcing, this gap is load-bearing for the main consistency result.
- [§3.1, Lemma 3.4] The statement 'f_D ≥ f' is not what the proof establishes. The proof shows that for every U with |V(U)| < g(n), χ(D[U]) ≤ 2n, which is equivalent to saying that every subdigraph of dichromatic number at least 2n+1 has at least g(n) vertices. It does not directly show f_D(n) ≥ f(n). The reduction from the theorem's target, that every (n+2)-dichromatic subdigraph has at least f(n) vertices, is asserted at the start of the proof but not derived. A correct derivation would define g(n) = max(f(2n-1), f(2n)) (with a suitable convention for negative arguments) and use the fact that a (t+2)-dichromatic digraph contains a (2n+1)-dichromatic subdigraph for n = floor((t+1)/2). Lemma 3.4 should be restated accurately and the reduction should be spelled out.
minor comments (4)
- [§3.1, proof of Lemma 3.4] There is a reference to 'Observation 3.10' in the case n=0; this should be Observation 3.2.
- [§3.2, Lemma 3.9] In the proof of Lemma 3.9, the first-order structure A_α is said to be on the ground set V(q_α), but q_α has not been introduced at that point; the intended object is V(p_α).
- [§3.2, definition of P_{κ,f}] The text contains a repeated fragment 'Pκ,fPκ,fPκ,f' in the definition of the poset; this is a typographical error.
- [§3.2, Lemma 3.11] In Lemma 3.11, the symbol U is used ambiguously as both a name for a subset of κ in the extension and as a set in the ground model; the quantifier over α should be made precise, for example by quantifying over α<κ for which there is a condition forcing α∈U.
Circularity Check
No circularity: the paper's constructions are self-contained ZFC proofs, with no load-bearing self-citation or fitted-input prediction.
full rationale
The paper proves Theorem 3.1 by explicitly constructing a digraph D on a product of finite intervals and verifying its dichromatic properties through direct coloring arguments (Lemma 3.3 and Lemma 3.4). Theorem 3.6 is proved by a finite-support ccc iteration whose factors are the posets P_{kappa,f}; Lemma 3.9, Lemma 3.11, and Claim 3.12 establish the ccc property and the cycle-containment property by delta-system and semihomomorphism arguments, all within the paper itself. The only self-citation is reference [5] in the introduction, where the author notes that a ZFC construction of digraphs with uncountable dichromatic number and no short directed cycles was previously shown in that paper; this citation is background and is not used in the proofs of Theorem 1.2 or Theorem 1.3. The final paragraph of Section 3.2 asserts that the proof of Lemma 3.11 transfers to the tail forcing P_{geq beta} by looking only at the initial coordinate p(beta). Even if this assertion is questionable as a matter of forcing correctness, it is not circular: it does not assume the desired conclusion or define a parameter in terms of the result. No prediction is fitted from data, and no uniqueness theorem is imported from the author's prior work. Hence the derivation chain is not circular, and the score is 0.
Assumptions & free parameters
assumptions (3)
- standard math ZFC (standard axioms of set theory including the Axiom of Choice)
- standard math Delta-system lemma and first-order compactness
- standard math Finite support iteration of ccc posets preserves ccc and cardinal arithmetic
Cite this review
Pith. "Pith review of On the growth rate of dichromatic numbers of finite subdigraphs." pith.science (2026). https://pith.science/paper/7G6HG7KS
@misc{pith2026190807264,
author = {Pith},
title = {Pith review of: On the growth rate of dichromatic numbers of finite subdigraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/7G6HG7KS}},
note = {Machine review of arXiv:1908.07264}
}
abstract
Chris Lambie-Hanson proved recently that for every function $ f:\mathbb{N}\rightarrow \mathbb{N} $ there is an $ \aleph_1 $-chromatic graph $ G $ of size $ 2^{\aleph_1} $ such that every $ (n+3) $-chromatic subgraph of $ G $ has at least $ f(n) $ vertices. Previously, this fact was just known to be consistently true due to P. Komj\'ath and S. Shelah. We investigate the analogue of this question for directed graphs. In the first part of the paper we give a simple method to construct for an arbitrary $ f:\mathbb{N}\rightarrow \mathbb{N} $ an uncountably dichromatic digraph $ D $ of size $ 2^{\aleph_0} $ such that every $ (n+2) $-dichromatic subgraph of $ D $ has at least $ f(n) $ vertices. In the second part we show that it is consistent with arbitrary large continuum that in the previous theorem "uncountably dichromatic" and "of size $ 2^{\aleph_0} $" can be replaced by "$\kappa $-dichromatic" and "of size $ \kappa $" respectively where $ \kappa $ is universally quantified with bounds $ \aleph_0 \leq \kappa \leq 2^{\aleph_0}$.
Reference graph
Works this paper leans on
-
[1]
P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems , Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99, DOI 10.1007/BF02020444. MR 193025 ↑1
-
[2]
On the growth rate of chromatic numbers of finite subgraphs
C. Lambie-Hanson, On the growth rate of chromatic numbers of finite subgraphs (2019). https://arxiv.org/abs/1902.08177 ↑1.1
work page Pith review arXiv 2019
-
[3]
P. Komjáth and S. Shelah, Finite subgraphs of uncountably chromatic graphs , J. Graph Theory 49 (2005), no. 1, 28–38, DOI 10.1002/jgt.20060. MR 2130468 ↑1
-
[4]
D. T. Soukup, Orientations of graphs with uncountable chromatic number , J. Graph Theory 88 (2018), no. 4, 606–630, DOI 10.1002/jgt.22233. MR 3818601 ↑1
-
[5]
Uncountable dichromatic number without short directed cycles
A. Joó, Uncountable dichromatic number without short directed cyc les (2019).https://arxiv.org/abs/1905.00782 ↑1
work page Pith review arXiv 2019
-
[6]
Komjáth, The chromatic number of infinite graphs—a survey , Discrete Math
P. Komjáth, The chromatic number of infinite graphs—a survey , Discrete Math. 311 (2011), no. 15, 1448– 1450, DOI 10.1016/j.disc.2010.11.004. MR 2800970 ↑
-
[7]
Neumann Lara, The dichromatic number of a digraph , J
V. Neumann Lara, The dichromatic number of a digraph , J. Combin. Theory Ser. B 33 (1982), no. 3, 265–270, DOI 10.1016/0095-8956(82)90046-6. MR 693366 ↑1
-
[8]
D. Bokal, G. Fijavž, M. Juvan, P. M. Kayll, and B. Mohar, The circular chromatic number of a digraph , J. Graph Theory 46 (2004), no. 3, 227–240, DOI 10.1002/jgt.20003. MR 2063373 ↑1
Show all 9 references
-
[9]
Severino, A short construction of highly chromatic digraphs without s hort cycles , Contrib
M. Severino, A short construction of highly chromatic digraphs without s hort cycles , Contrib. Discrete Math. 9 (2014), no. 2, 91–94. MR 3320450 ↑1 6
2014
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.