{"id":"2c5daa37-81f9-43c1-a38f-610eb59e55f6","arxiv_id":"1908.02442","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A game-theoretic argument proves Shelah's theorem: families of λ-labeled trees of sufficiently large cardinality contain a homomorphism between two distinct trees.","lead":"A new proof shows that if a cardinality condition (the partition relation κ→(ω)^{<ω}_λ) holds, any large family of λ-labeled trees contains a homomorphic pair. The proof uses games to encode tree homomorphisms and avoids the traditional better-quasi-ordering machinery.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the sketched general induction in Claim 3.1 checks out and the Gale–Stewart step is standard ZFC.","rationale":"The reader accepted the paper with high confidence and identified the same potential weak spots: the reliance on Gale–Stewart determinacy and the compressed induction in Claim 3.1. I examined both. The game's payoff is closed for player II, so Gale–Stewart applies in ZFC. The induction, though sketched, is sound: extending an interval by one vertex adds exactly one new top-row move and one new label-match; the former is supplied by the relevant winning strategy and the latter is precisely the shift-invariance property guaranteed by homogeneity. All other tree memberships and label matches are inherited from the two smaller intervals. The construction of the infinite play from all finite good intervals is also valid, and it indeed contradicts the winning strategies for player I. No counterexample, circular step, or unsupported assumption was found. The contribution is a correct new proof of a known theorem, with only minor presentation compression in the general diagram chase.","tokens_in":5163,"tokens_out":55272,"duration_ms":594220,"concrete_test":"Independently re-derive the general induction step of Claim 3.1 for arbitrary i,n by writing the triangular-array recurrence a_{r,s} explicitly; verify that the only conditions not inherited from the two length-n subintervals are membership of the top-right corner (given by the winning strategy) and the label equality f(⟨α_i,...,α_{n+i-1}⟩)=f(⟨α_{i+1},...,α_{n+i}⟩). If these are indeed the only new conditions, the 'general case is similar' claim is valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I do not find a load-bearing concern. The only delicate point is the sketched 'general case' in Claim 3.1. Formalizing the induction for an interval of length m+1: the two length-m subintervals cover every entry of the triangular array except the top-right corner x^0_m. Its tree-membership follows from the winning strategy Σ_{01}, because the preceding II-moves are legal by the shifted subinterval; the only new label-match condition is exactly the shift-invariance equation (1), f(⟨α_i,...,α_{n+i-1}⟩)=f(⟨α_{i+1},...,α_{n+i}⟩), which matches the final dashed arrow for game 0 after all earlier arrows are already justified. The same argument works for arbitrary i. The other potential weak point, Gale–Stewart determinacy of G(T,U), is standard in ZFC for closed games on arbitrary sets: player I's winning condition is open, so player II's is closed. No circularity, hidden assumption, or internal inconsistency emerges.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a new proof of Shelah's theorem on labeled trees: assuming the partition relation κ → (ω)^{<ω}_λ, every κ-sequence of λ-labeled trees contains two trees T_α, T_β (α<β) with a homomorphism T_α → T_β. The proof introduces a game G(T,U) in which player II builds a partial homomorphism by matching labels; Lemma 2.2 states that player II has a winning strategy exactly when a homomorphism exists. Lemma 2.4, via Gale-Stewart determinacy, turns the non-existence of homomorphisms into a family of winning strategies for player I in each pair T_α, T_β. Assuming no homomorphism exists, the author plays these strategies against each other to form triangular arrays of moves for each finite increasing sequence of ordinals, and uses the array to define a coloring f of [κ]^{<ω}. The partition relation yields an infinite homogeneous set H; homogeneity gives a shift-invariance equation (1). Claim 3.1 proves by induction that every finite interval in H is 'good' (all rules followed). Passing to the infinite limit then produces, for every adjacent pair in H, an infinite play in which player II follows all rules, contradicting that player I had a winning strategy. The paper is self-contained apart from standard Gale-Stewart determinacy.","tokens_in":5345,"tokens_out":15390,"duration_ms":150870,"significance":"The result is not new—Shelah's theorem is known—but the proof is. Its principal strengths are the clean game-theoretic reformulation, the avoidance of Nash-Williams' better-quasi-order theory, and the use of only ZFC plus the classical Gale-Stewart theorem for closed games. The strategy-combination argument (Figures 1 and 2) is elegant and gives a concrete mechanism through which the partition relation produces a homomorphism. If the proof is accepted, it will make Shelah's theorem accessible to a broader audience and may be adaptable to other Ramsey-type statements. The manuscript is well written and the mathematical claims are clearly stated; the proof appears sound. The minor presentation issues listed below do not affect correctness.","major_comments":[],"minor_comments":[{"comment":"The induction step is only shown for i=0, n=3, with the sentence 'The general case is similar.' Since this claim is the heart of the proof, please expand the general case explicitly, or at least state the precise induction hypothesis and the configuration of the sub-triangles for arbitrary i and n. As written, the reader must reconstruct the diagram chase for arbitrary shifts.","section":"Section 3, Claim 3.1"},{"comment":"The symbols x^i_j are used in the figures but never defined in the text. Please add a sentence defining x^i_j as the j-th move of player I in the game G(T_{α_i},T_{α_{i+1}}), or the appropriate convention, and clarifying how the triangular array is generated recursively.","section":"Section 3, notation"},{"comment":"The abstract contains a typo ('eve ry family').","section":"Abstract"},{"comment":"The claim that the shift-invariance version is easily proved equivalent to Silver's weak partition relation κ^w → (ω)^{<ω}_λ would benefit from a reference or a one-line proof sketch, since the equivalence is not immediate.","section":"Footnote 2"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a solid proof of a known theorem. No concerns about novelty disclosure: it correctly attributes the theorem to Shelah and cites Eklof-Shelah and Herden. The only point I would emphasize to the editor is that the proof's central combinatorial induction is sketched; in a final version, the authors should spell it out. This is a presentation matter, not a correctness issue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a clean, self-contained new proof of Shelah's labeled-tree theorem, and it does what it claims without relying on Nash-Williams bqo machinery. The proof is sound; I don't see a load-bearing gap.\n\nWhat's genuinely new is the game G(T,U) and the strategy-combination argument. Lemma 2.2 is essentially a restatement—a homomorphism is literally a positional winning strategy for player II in a closed game—but that restatement buys something: it converts a non-existence statement into a strategy for player I, and then the partition relation is used to combine those strategies into a homogeneous sequence. The triangular-array diagram is the right picture, and the shift-invariance observation is the key move. The paper is honest that this is a new proof of a known theorem, not a new theorem, and the significance is accordingly modest.\n\nSoft spots: the induction in Claim 3.1 is only sketched for the general case. The stress-test note is right that the case n=3 carries the idea and the general case really is similar, but a reader who wants to verify arbitrary shifts and intervals has to do real diagram chasing. That is a presentation gap, not a correctness gap. The other external ingredient, Gale-Stewart for closed games, is completely standard ZFC. The citation pattern is fine: Shelah's theorem, Eklof-Shelah, Herden for the converse, and the Moschovakis/Kechris references for the game absoluteness remark are all apt. No circularity.\n\nWho it's for: anyone who works in infinitary combinatorics or uses partition relations and wants to see the bqo theory stripped out. I'd be happy to see it published; it deserves a serious referee, and the referee's main job should be to push the author to expand the general-case sketch in Claim 3.1.","headline":"A sound, elegantly written new proof of a known theorem; the only real weakness is a sketched induction that deserves expansion.","tokens_in":5870,"tokens_out":1250,"would_cite":true,"duration_ms":12908,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03E05","03E55","03E60","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves Shelah's theorem on labeled trees by translating 'no homomorphism' into a winning strategy in a closed game.","keywords":["Shelah's theorem","labeled trees","tree homomorphisms","partition relations","closed games","game determinacy","large cardinals","better-quasi-orderings"],"falsifier":"Take a concrete family of $\\lambda$-labeled trees and run the Section 3 construction for a finite increasing tuple of length 4: write out the $3\\times3$ and $4\\times4$ move arrays from the winning strategies $\\Sigma_{\\alpha_i\\alpha_{i+1}}$, and check whether equality of the two $f$-values on overlapping intervals forces every dashed label-matching rule in the fourth triangle. Any $n\\ge3$ where this local check fails would break Claim 3.1 and point to the missing general case; no such example should exist if the proof is sound.","tokens_in":4969,"feed_emoji":"🌳","tokens_out":8944,"duration_ms":94748,"temperature":0.7,"pith_summary":"Shelah's theorem says that if a cardinal $\\kappa$ satisfies the partition relation $\\kappa\\to(\\omega)^{<\\omega}_\\lambda$, then every family of $\\lambda$-labeled trees indexed by $\\kappa$ contains a homomorphism $T_\\alpha\\to T_\\beta$ for some $\\alpha<\\beta<\\kappa$. This paper establishes that theorem by a new route. It avoids the established better-quasi-ordering machinery and instead characterizes the nonexistence of a tree homomorphism as the existence of a winning strategy for player I in a closed infinite game, then combines such strategies in a triangular array. The homogeneous set supplied by the partition relation makes the array cohere, forcing a contradiction. The proof matters because it isolates a simple game-theoretic mechanism behind a result that had appeared to require a heavier apparatus.","feed_headline":"Games prove Shelah's labeled-tree theorem","feed_subtitle":"If the family of trees is large enough, one must embed into another, with a proof based on games.","key_machinery":"The central object is the game $G(T,U)$, in which player I builds a branch in $T$ and player II must build the corresponding branch in $U$ with the same labels at every finite stage; player II wins exactly when a label-preserving tree homomorphism exists (Lemma 2.2). The proof's second mechanism is the triangular combination of several player-I winning strategies: for each increasing sequence $\\langle\\alpha_0,\\dots,\\alpha_n\\rangle$, the strategies $\\Sigma_{\\alpha_i\\alpha_{i+1}}$ are fed each other's outputs, and the resulting top row labels define a coloring $f:[\\kappa]^{<\\omega}\\to\\lambda$; the partition relation supplies an infinite homogeneous set whose shift-invariance property makes the induction in Claim 3.1 go through.","core_discovery":"The paper's central claim is Theorem 1.1: if $\\kappa\\to(\\omega)^{<\\omega}_\\lambda$ holds, then for every sequence $\\langle T_\\alpha:\\alpha<\\kappa\\rangle$ of $\\lambda$-labeled trees there are $\\alpha<\\beta<\\kappa$ with a homomorphism $T_\\alpha\\to T_\\beta$. The new content is that this can be proved by translating the absence of a homomorphism into the existence of a winning strategy for player I in the game $G(T_\\alpha,T_\\beta)$, invoking closed-game determinacy (Gale\\textendash{}Stewart) rather than better-quasi-ordering theory, and then deriving a contradiction by playing all the strategies against one another in a triangular array indexed by finite increasing sequences from $\\kappa$. Homogeneity of the coloring produced by this array gives a shift-invariance condition that forces every finite interval of the homogeneous set to be good, and the infinite play thereby obtained makes player II win each game, contradicting the chosen strategies.","pith_inferences":["The same triangular strategy-combination might be reusable for other embeddability theorems that are normally proved by better-quasi-ordering arguments, such as variants for trees with additional structure or for finitely many labels; the paper does not explore this.","Because the proof needs only closed determinacy, it is plausible that the argument formalizes in weak set theories, and for countable trees in second-order arithmetic, which would strengthen the case that the theorem does not secretly depend on the full theory of better-quasi-orderings; this is an extension, not a paper claim.","One could test the reach of the method by replacing $\\kappa\\to(\\omega)^{<\\omega}_\\lambda$ with weaker or modified partition relations and checking whether the strategy-combination still forces a homomorphism; the paper does not state such bounds."],"forward_implications":["For any $\\lambda$-labeled tree family indexed by a cardinal $\\kappa$ with $\\kappa\\to(\\omega)^{<\\omega}_\\lambda$, a homomorphism between two trees is guaranteed; no additional structural assumption on the trees is needed.","In the case $\\lambda=1$, the theorem reduces to the familiar fact that among infinitely many unlabeled trees one embeds into another, and the paper notes its game proof covers this case without appealing to tree ranks.","The game characterization makes the existence of a homomorphism absolute between transitive models of ZFC, since closed games are absolutely determined; the paper records this consequence as a remark.","The proof needs only closed determinacy, whereas previous proofs used better-quasi-ordering theory, so the theorem is shown to follow from a more basic Ramsey-theoretic property of $\\kappa$."],"supporting_citations":[{"why":"The original theorem, which this proof re-proves without better-quasi-ordering theory.","marker":"[5]"},{"why":"The source for the method of combining strategies in a triangular array, as in the first periodicity theorem.","marker":"[4]"},{"why":"Earlier formulation of the same result, cited in the introduction as the theorem's provenance.","marker":"[1]"},{"why":"Reference cited as containing proofs of both directions of the equivalence between the partition relation and tree homomorphisms.","marker":"[2]"}],"fun_headline_variants":["Game theory yields new proof of Shelah's tree theorem","Shelah's labeled trees: a game-theoretic proof of homomorphism","Games force a homomorphism in large labeled-tree families","Determinacy proves Shelah's theorem on labeled trees","New game-based proof for Shelah's labeled-tree result"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the standard fact that closed infinite games are determined, so the failure of a homomorphism can be converted into a winning strategy for player I; it also relies on the unstated generalization of the triangular diagram chase from $n=3$ to all $n$, flagged in the proof by 'The general case is similar.'","fun_headline_variants_meta":{"raw":{"variants":["Game theory yields new proof of Shelah's tree theorem","Shelah's labeled trees: a game-theoretic proof of homomorphism","Games force a homomorphism in large labeled-tree families","Determinacy proves Shelah's theorem on labeled trees","New game-based proof for Shelah's labeled-tree result"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00055,"raw_usage":{"total_tokens":2564,"prompt_tokens":826,"completion_tokens":1738,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":442,"completion_tokens_details":{"reasoning_tokens":1655}},"tokens_in":442,"tokens_out":1738,"duration_ms":14051,"temperature":1.0,"reasoning_tokens":1655,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:44:25.850246+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete family of $\\lambda$-labeled trees and run the Section 3 construction for a finite increasing tuple of length 4: write out the $3\\times3$ and $4\\times4$ move arrays from the winning strategies $\\Sigma_{\\alpha_i\\alpha_{i+1}}$, and check whether equality of the two $f$-values on overlapping intervals forces every dashed label-matching rule in the fourth triangle. Any $n\\ge3$ where this local check fails would break Claim 3.1 and point to the missing general case; no such example should exist if the proof is sound.","supporting_citations":[{"cited_title":"Better quasi-orders for uncountable cardina ls","cited_arxiv_id":null,"evidence_quote":"The original theorem, which this proof re-proves without better-quasi-ordering theory."},{"cited_title":"Moschovakis","cited_arxiv_id":null,"evidence_quote":"The source for the method of combining strategies in a triangular array, as in the first periodicity theorem."},{"cited_title":"Eklof and Saharon Shelah","cited_arxiv_id":null,"evidence_quote":"Earlier formulation of the same result, cited in the introduction as the theorem's provenance."},{"cited_title":"Die Wolfsburg,","cited_arxiv_id":null,"evidence_quote":"Reference cited as containing proofs of both directions of the equivalence between the partition relation and tree homomorphisms."}],"review_version":1}