{"id":"d4b241c7-976f-495c-9056-73af17b38244","arxiv_id":"1908.07264","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every growth function f, there are uncountably dichromatic digraphs of size continuum in which every (n+2)-dichromatic finite subdigraph has at least f(n) vertices, and it is consistent with arbitrarily large continuum that the same holds with optimal size for every infinite cardinal kappa up…","lead":"This math paper proves new results about the dichromatic number, a directed graph version of graph coloring. It constructs digraphs whose finite subdigraphs have arbitrarily slow growth of dichromatic complexity, and shows a forcing-based consistency result for all infinite cardinal sizes up to the continuum.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The final paragraph of §3.2 asserts that Lemma 3.11's proof transfers to the tail forcing P_{≥β} by looking only at the initial coordinate p(β); the compatibility of tail coordinates is never shown, and this is load-bearing for Theorem 3.6.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: the transfer of Lemma 3.11 to the whole tail forcing P_{≥β} is asserted rather than proved. I agree with that assessment. The first part of the paper (Theorem 3.1) appears mathematically solid; the construction on the product space and the coloring argument are coherent apart from notation ambiguities such as 2n versus 2^n. The ccc proof in Lemma 3.9 is also fillable by trimming to a fixed ground-set size before counting isomorphism types. The serious issue is the second part: the final paragraph of Section 3.2 reduces a condition in P_{≥β} to its first coordinate, but the proof of Lemma 3.11 needs to combine finitely many conditions q_{α_i} that force α_i∈U. In P_{κ,f} this is done by forming a union of finite digraphs, which is a valid condition. In P_{≥β} the tail coordinates must also be merged, and there is no proof that the relevant tail conditions are compatible. This is load-bearing because the final extension may contain uncountable subsets U not present in the intermediate model, and the entire point of the final paragraph is to show D still has a directed cycle on such U. The concern does not by itself show the theorem is false; it shows the proof is incomplete at a central step. Therefore the conditional verdict is appropriate, pending a concrete compatibility argument for tail coordinates.","tokens_in":7112,"tokens_out":36023,"duration_ms":395841,"concrete_test":"Isolate the two-step case Q=P_{κ,f} followed by tail R=P_{λ,g} (or any ccc factor). Let U be an R-name forced to be an uncountable subset of κ, and follow Lemma 3.11 inside Q*R. The test: for arbitrary r=(r_Q,r_R) forcing U uncountable, and q_α≤r forcing α∈U, show that one can choose m=q_α_i whose tail coordinates have a common extension q_R and whose first coordinates admit the directed-cycle union from Claim 3.12. If this requires a new compatibility argument not present in the paper (for example, root-coordinate compatibility in the tail Δ-system), then the final paragraph is unsupported; if no such q_R exists for a concrete tail, the transfer is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest point is the last paragraph of Section 3.2. Theorem 3.6 requires that in the final extension, the digraph D produced at stage β contains a directed cycle in every uncountable U⊆κ, including U that are names added by the later tail forcing P_{≥β}. The proof says Lemma 3.11 goes through 'by working formally with the whole P_{≥β} instead of just Q_β=P_{κ,f}' and that 'whenever we deal with a condition p ... we consider now just its initial coordinate p(β).' This ignores the tail coordinates. In Lemma 3.11, one chooses conditions q_α forcing α∈U, applies Δ-system/isomorphism to their finite digraphs, and forms q=C∪∪q_i. For P_{≥β}, a condition has tail coordinates as well; the chosen q_α may have incompatible tail coordinates, and no argument is given that finitely many of them have a common extension. The first-coordinate extension only ensures q(β)∈P_{κ,f}; it does not produce a condition q≤q_i in the iteration. Since the whole point is to handle new uncountable sets U introduced by the tail, this is not a cosmetic omission: the central consistency theorem depends on it. If the compatibility of tail coordinates cannot be proved (e.g., by choosing q_α with Δ-system-disjoint tail supports and compatible root values), the final paragraph's transfer fails.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7355,"tokens_out":23902,"duration_ms":231931,"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":[{"comment":"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.","section":"§3.2, final paragraph"},{"comment":"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.","section":"§3.1, Lemma 3.4"}],"minor_comments":[{"comment":"There is a reference to 'Observation 3.10' in the case n=0; this should be Observation 3.2.","section":"§3.1, proof of Lemma 3.4"},{"comment":"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_α).","section":"§3.2, Lemma 3.9"},{"comment":"The text contains a repeated fragment 'Pκ,fPκ,fPκ,f' in the definition of the poset; this is a typographical error.","section":"§3.2, definition of P_{κ,f}"},{"comment":"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.","section":"§3.2, Lemma 3.11"}],"recommendation":"major_revision","confidential_remarks":"The ZFC construction and the ccc lemma are likely correct and are a useful contribution. The main concern is the unproven preservation of the cycle-containment property through the tail forcing in Theorem 3.6; the final paragraph of Section 3.2 does not contain a proof, and the suggested 'initial coordinate' argument is not enough because the name U may depend on the tail coordinates. This is a serious gap, but it may be repairable with a more careful compatibility argument, so I recommend major revision rather than rejection. The indexing issue in Section 3.1 is minor but should be fixed. There is no circularity concern; the self-citation [5] is not load-bearing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nShort version: the ZFC construction in Section 3.1 is a genuine result and the proof is refreshingly simple. The forcing part is a good idea, but the final step has a gap that is not cosmetic. I would not let the current draft pass, but I would gladly referee it myself.\n\nThe first theorem (every f is realized as the growth rate of finite-subgraph dichromatic numbers for an uncountably dichromatic digraph of size c) is a clean product construction. The key observation—that vertices live in a product of finite cyclic coordinates and that any small induced subgraph has digirth larger than some coordinate length, giving a 2n-colouring—is elegant. The compactness remark for the countable case also works.\n\nThe second theorem is where I have a problem. The poset P_{κ,f} (finite digraphs on κ with f_p ≥ f, ordered by inclusion) is shown to be ccc with a nice Δ-system/isomorphism argument (Lemma 3.9). Lemma 3.11, that the generic union D satisfies χ(D[U]) = |U| for every uncountable U, is fine for the single poset. The proof picks conditions q_α, forms a Δ-system, and then takes the union of the finite digraphs. That union is a valid condition because the order is inclusion.\n\nThe issue is the last paragraph of Section 3.2. To get the theorem for the final iteration, the author needs Lemma 3.11 to hold for the whole tail forcing P_{≥β}, because new uncountable sets U appear after stage β. The text says the proof goes through 'by working formally with the whole P_{≥β}' and 'considering just its initial coordinate p(β).' That is not enough. In the iteration, a condition has many coordinates; the q_α chosen for α∈U may have incompatible values on the tail, and no argument is given that they have a common extension. The first coordinate alone does not determine compatibility. This is exactly the point that makes the result about the final extension, not just the intermediate one. Without a proof (e.g., a Δ-system on tail supports and compatible roots), Theorem 3.6 is unsubstantiated.\n\nThere are also minor issues: the reduction from arbitrary f to nondecreasing g in Theorem 3.1 is asserted but not derived, and the OCR typos (e.g., '2n' vs '2^n') do not help. These are small.\n\nIf the tail-forcing gap can be closed, the paper is a strong contribution to the infinite dichromatic number literature. As it stands, it is a good first half and an interesting but incomplete second half. I would send it to a serious referee, because the core ideas are worth the effort. If the author cannot supply the compatibility argument, Theorem 3.6 may be false.\n\nWho gets value: set-theoretic graph theorists, anyone working with uncountable chromatic/dichromatic numbers. I'd probably cite the first theorem, but I would wait for a revised version before relying on the consistency result.","headline":"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.","tokens_in":7926,"tokens_out":4022,"would_cite":true,"duration_ms":42024,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C15","03E35"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["dichromatic number","growth rate","finite subdigraphs","directed cycles","forcing","ccc poset","uncountable cardinal","continuum"],"falsifier":"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.","tokens_in":6869,"feed_emoji":"📈","tokens_out":15303,"duration_ms":140497,"temperature":0.7,"pith_summary":"The paper asks how slowly the dichromatic number (the minimum number of colours needed to colour the vertices so that no colour class contains a directed cycle) can grow among finite subdigraphs of a large digraph. It proves a directed analogue of a recent graph result: given any function $f:\\omega\\to\\omega$, there is an uncountably dichromatic digraph of size continuum whose $(n+2)$-dichromatic subdigraphs all have at least $f(n)$ vertices. It then shows by a ccc forcing construction that, consistently with arbitrarily large continuum, the same can be achieved for every uncountable cardinal $\\kappa\\le c$ by a $\\kappa$-dichromatic digraph on exactly $\\kappa$ vertices; in fact every uncountable induced subdigraph is then maximally dichromatic. The point is that the finite subdigraphs of a highly dichromatic digraph can be made arbitrarily sparse in dichromatic number, even at optimal size.","feed_headline":"Forcing gives prescribed dichromatic growth at each cardinal up to c","feed_subtitle":"Every prescribed threshold for finite dichromatic subdigraphs is met by digraphs of every size up to the continuum.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The graph-theoretic result that this paper's Theorem 3.1 is the directed analogue of; supplies the threshold formulation $f_D\\ge f$.","marker":"[2]"},{"why":"The forcing construction for uncountably dichromatic digraphs that the paper develops into a finite-support iteration; supplies the method behind Theorem 3.6.","marker":"[4]"},{"why":"Defines the dichromatic number of a digraph as the minimum number of acyclic parts needed to cover its vertices; the central parameter studied throughout.","marker":"[7]"}],"fun_headline_variants":["New digraphs hit every prescribed dichromatic growth bound","Forcing yields dichromatic digraphs of every prescribed size","Dichromatic growth made to order for every cardinal up to c","Prescribed dichromatic thresholds for digraphs of any size up to c"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["New digraphs hit every prescribed dichromatic growth bound","Forcing yields dichromatic digraphs of every prescribed size","Dichromatic growth made to order for every cardinal up to c","Prescribed dichromatic thresholds for digraphs of any size up to c"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000971,"raw_usage":{"total_tokens":4195,"prompt_tokens":1077,"completion_tokens":3118,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":693,"completion_tokens_details":{"reasoning_tokens":3044}},"tokens_in":693,"tokens_out":3118,"duration_ms":21359,"temperature":1.0,"reasoning_tokens":3044,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:22:44.032418+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On the growth rate of chromatic numbers of finite subgraphs","cited_arxiv_id":"1902.08177","evidence_quote":"The graph-theoretic result that this paper's Theorem 3.1 is the directed analogue of; supplies the threshold formulation $f_D\\ge f$."}],"review_version":1}