{"id":"c9b656c3-1ba6-4c25-abeb-b1c6e9dc7477","arxiv_id":"2507.01498","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every fixed r and s, the minimum number of edges in a host hypergraph that forces a monochromatic r-uniform tight path on n vertices under any s-colouring grows only linearly in n.","lead":"This paper proves that the s-colour size-Ramsey number of the r-uniform tight path on n vertices is O(n) for every fixed r and s. This resolves a 2017 question of Dudek, La Fleur, Mubayi and Rödl and brings hypergraph tight paths in line with the classical linear-size behaviour of graph paths.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.24 cites Lemma 4.17 for a cleaning step that Lemma 4.17 does not cover, leaving a load-bearing gap in the proof of Lemma 4.25 and hence Theorem 5.1.","rationale":"The reader's weakest_assumption focused on Lemma 3.2 (existence of bounded-degree ε-expanders), which is a standard and true statement, even if cited to an unpublished manuscript. My stress-test found a more internal and directly load-bearing issue: Lemma 4.24's proof invokes Lemma 4.17 without satisfying its hypotheses. This is not a refutation of the central claim, since the needed cleaning statement is very likely provable by iterating Lemma 4.16, but it is a concrete gap that must be fixed for the main proof to be rigorous. The reader's verdict of CONDITIONAL is therefore appropriate, and my concern does not change that verdict; it does redirect attention to a different part of the proof. The central claim itself (linear size-Ramsey numbers for tight paths) remains well-supported by the overall structure, and I found no evidence of a fatal flaw.","tokens_in":32015,"tokens_out":58293,"duration_ms":553637,"concrete_test":"Attempt to prove the cleaning step used in Lemma 4.24 directly from Lemma 4.16: enumerate Types(h,r), apply Lemma 4.16 successively for each type τ, and compute the arity loss at each application. Verify that for d ≫ h,r,s the process ends with a binary subtree T′ such that all r-sets of leaves of the same type in T′ have the same colour. If this derivation can be completed, the gap is cosmetic; if not, Lemma 4.24 rests on an unproved assertion and Lemma 4.25 is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The contradiction at the end of Theorem 5.1 rests on Lemma 4.25 (disconnection is bounded), whose proof invokes Lemma 4.24. Inside Lemma 4.24, the proof says: 'By Lemma 4.17 applied to T, there is a balanced binary subtree T′ ≤ T of height h, such that r-sets of leaves of the same type have the same colour.' But Lemma 4.17 (Cleaning forests) is stated for an r-uniform hypergraph H of maximum degree at most Δ and a V(H)-forest F of balanced d-ary trees. For a single tree T, the natural H would be the complete r-uniform hypergraph on L(T), whose maximum degree is unbounded, and T is not a V(H)-forest with V(H)=L(T). The proof of Lemma 4.24 therefore uses Lemma 4.17 in a regime where its hypotheses are not satisfied. The desired statement is plausible: one could iterate Lemma 4.16 (the single-type Ramsey lemma) over all τ ∈ Types(h,r), starting with a sufficiently tall d-ary tree and reducing arity by a controlled amount at each step, to obtain a binary subtree on which all r-sets of the same type have the same colour. However, the paper does not provide this argument, and Lemma 4.24 as written is not directly supported. Since Lemma 4.24 is essential for Lemma 4.25, and Lemma 4.25 is the engine that produces the contradiction in Theorem 5.1, this is a load-bearing gap in the proof as presented.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that the s-colour size-Ramsey number of the r-uniform tight path P_n^{(r)} is O(n) for every fixed r and s, answering a question of Dudek, La Fleur, Mubayi and Rödl (2017). The proof constructs a bounded-degree expanding graph G and shows that an appropriate power G^p, viewed as an r-uniform hypergraph, is Ramsey for tight paths. The main technical engine is Theorem 5.1, which asserts the existence of bounded-degree r-uniform hypergraphs on n vertices in which every s-colouring contains a long monochromatic tight walk with bounded vertex multiplicity. The proof introduces ordered forests, types of leaf subsets, clean colourings, disconnected tree assignments, and versatile sets, and culminates in a structural contradiction (Lemma 4.25). The final section derives the size-Ramsey bound from Theorem 5.1 via a blow-up argument.","tokens_in":32300,"tokens_out":29997,"duration_ms":300743,"significance":"The result resolves an open problem from Dudek, La Fleur, Mubayi and Rödl (2017), extending the known case r = 3 and improving the best previous bound for r ≥ 4. The paper introduces a substantial new toolkit for hypergraph size-Ramsey problems, and the overall strategy is coherent and ambitious. If the technical gaps identified below are repaired, the paper would be a significant contribution to extremal combinatorics. The final blow-up argument is clean, and the dependence on expanders is standard; the paper also gives a concise reduction of the main theorem to a single structural statement (Theorem 5.1).","major_comments":[{"comment":"The proof of Lemma 4.24 applies Lemma 4.17 to the tree T, but Lemma 4.17 requires an r-uniform hypergraph H of maximum degree at most Δ and a V(H)-forest F. Here H is the complete r-uniform hypergraph on L(T), whose maximum degree is unbounded (it is binomial in |L(T)|), and T is not a V(H)-forest with V(H) = L(T). Since Lemma 4.25 and hence Theorem 5.1 rely on Lemma 4.24, this is a load-bearing gap. The desired statement is plausible and can be proved by iterating Lemma 4.16 over the finite set Types(h, r), reducing the arity by a controlled amount at each step; please provide this argument explicitly.","section":"Section 4.3, Lemma 4.24"},{"comment":"Observation 4.19 is false as stated: the claimed equivalence between e being an edge of G^t ⊗_r F and ||e||_G ≤ t fails for r-sets e with fewer than r distinct π0-values, because {v} need not be contained in any r-edge of G^t. For example, if G is a path, t = 1, and r = 3, then G^1 has no edges and no r-subset of L(F(v)) with π0(e) = {v} is an edge, yet ||e||_G = 0. The proof of Lemma 4.25 uses this false converse to conclude that the sequence P constructed from Lemma 4.24 is a tight walk in G^t ⊗ F. In the intended application (t = c_h ≥ 2 and G an expander with Δ ≫ r) the needed direction does hold, because every vertex has at least r vertices in its closed neighbourhood and all r-subsets of L(F(v)) are then contained in edges of G^{c_h}; but the paper must state and prove this, and the statement of Lemma 4.25 should be restricted to the range where the complete hypergraph on L(F(v)) embeds into G^t ⊗ F.","section":"Section 4.3, Observation 4.19 and Lemma 4.25"},{"comment":"Lemma 4.25 is stated for every non-negative integer t, but it is false for small t: if G is a path and t = 1 with r = 3, then G^1 ⊗ F has no edges, so every colouring is vacuously 1-disconnected regardless of the height of F. The proof implicitly assumes that every r-subset of leaves with constant π0 is an edge, which requires t large enough relative to the local structure of G. Since Theorem 5.1 only needs t = c_h for the large constants produced by the hierarchy, the lemma should be reformulated for that range, with the missing embedding argument supplied.","section":"Section 4.3, Lemma 4.25"}],"minor_comments":[{"comment":"In the proof of Lemma 3.9, 'we either get a colour 1 copy of K_d' should read 'colour d+1' (or 'colour s+1'), since the K_d in Lemma 3.8 is in the last colour, not colour 1.","section":"Lemma 3.9"},{"comment":"In the final paragraph of the proof of Theorem 5.1, 'a balanced d_h-ary V(G)-forest' and 'G^{d_h} ⊗ F_h' should be 'c_h-ary' and 'G^{c_h} ⊗ F_h', consistent with properties (F2) and (F5).","section":"Theorem 5.1"},{"comment":"The statement assumes r ≤ s, but the proof does not use this inequality. If the result is intended for all s, remove the restriction; otherwise, Theorem 5.1's application for r > s needs a short reduction (e.g., viewing an s-colouring as an r-colouring with unused colours).","section":"Lemma 4.25"},{"comment":"The notation G^k is defined as the r-uniform hypergraph power, but in Section 3 (Lemmas 3.7–3.9) it is used for the ordinary graph power; please disambiguate, for instance by writing G^k_{(r)} for the hypergraph in the Ramsey lemmas or by explicitly saying that Section 3 uses graph powers.","section":"Sections 2–3"}],"recommendation":"major_revision","confidential_remarks":"The paper's central claim is important and the overall strategy appears sound, but the proof as written has a load-bearing gap in Lemma 4.24 (invalid use of Lemma 4.17) and a false overgeneralization in Observation 4.19 / Lemma 4.25. Both appear repairable within the manuscript's scope: Lemma 4.24 can be proved by iterating Lemma 4.16, and Lemma 4.25 can be restricted to the parameter range used in Theorem 5.1 with a short embedding argument. I would encourage the editor to send the paper back for a careful revision rather than reject. The reliance on the authors' unpublished manuscript [38] for Lemma 3.2 is not circular, but including a full proof of the expander existence (or a published citation) would improve the paper's self-containedness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about arXiv:2507.01498. First, it proves the right theorem: linear s-colour size-Ramsey numbers for r-uniform tight paths for every fixed r and s, settling the 2017 question of Dudek, La Fleur, Mubayi and Rödl. Second, the proof is not yet fully clean—the application of Lemma 4.17 inside Lemma 4.24 appears to be outside that lemma's hypotheses, and this step powers the final contradiction in Theorem 5.1.\n\nWhat's genuinely new and good: for r ≥ 4 the previous bound was superlinear (Lu–Wang), so this is a real breakthrough, not an incremental improvement. The machinery—ordered forest families, types, k-disconnected colourings, augmentations, versatile sets—is substantial and most of it is carefully defined. The proof of Theorem 1.1 from the technical Theorem 5.1 is short and elegant, and the expander-power approach is a natural generalization of the graph-path argument. The paper also gives a good overview that makes the structure navigable. Reliance on the authors' own unpublished [38] for the existence of expanders is mild; the statement is standard and a sketch is given.\n\nSoft spots: the Lemma 4.24 issue is the main one. Lemma 4.17 requires a V(H)-forest, but T is rooted at its top, not at its leaves, and the complete hypergraph on L(T) has unbounded degree, so the lemma's hypotheses fail. The intended statement—a binary subtree on which all r-sets of the same type have the same colour—is plausible and can be obtained by iterating Lemma 4.16 over the finitely many types, but that argument isn't written down. Since Lemma 4.25 and hence Theorem 5.1 rest on Lemma 4.24, the proof as currently written has a load-bearing gap. I'd guess it's fixable, but it's real. There are also some smaller typos (Lemma 3.9's 'colour 1' vs 'colour d+1', the arity confusion in the Theorem 5.1 summary) and compressed justifications elsewhere, which together slow independent verification.\n\nWho should read it: anyone working on size-Ramsey numbers or Ramsey properties of expanders. It deserves a serious referee—a good referee will want to check Lemma 4.24 and the cleaning argument carefully. My recommendation: send it to peer review, with a note asking the referee to focus on Section 4.2 and Lemma 4.24. If the authors patch that gap, this will be a strong paper.","headline":"Major result—linear size-Ramsey for all tight paths—but there is a real gap in the proof of Lemma 4.24 that needs patching before the paper is complete.","tokens_in":32911,"tokens_out":4359,"would_cite":true,"duration_ms":51009,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C55","05C65","05D10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the s-colour size-Ramsey number of the r-uniform tight path on n vertices is linear in n for every fixed r and s, resolving a 2017 question.","keywords":["size-Ramsey number","tight paths","hypergraphs","Ramsey theory","expanders","multicolour Ramsey","ordered forests","monochromatic tight walk"],"falsifier":"A direct refutation would be a sequence of $r$-uniform hypergraphs with $O(n)$ edges and bounded maximum degree whose edges can be $s$-coloured so that every monochromatic tight path has $o(n)$ vertices. Concretely, finding such a construction for $r=3$, $s=2$ for infinitely many $n$ would contradict Theorem 1.1, since the theorem promises that every $O(n)$-edge bounded-degree host forces a monochromatic tight path of linear length.","tokens_in":31780,"feed_emoji":"🧩","tokens_out":12564,"duration_ms":122076,"temperature":0.7,"pith_summary":"This paper proves that the $s$-colour size-Ramsey number of the $r$-uniform tight path on $n$ vertices is linear in $n$ for every fixed $r$ and $s$: there is a hypergraph with only $O(n)$ edges whose every $s$-edge-colouring contains a monochromatic copy of the path. The result answers a 2017 question about hypergraph size-Ramsey numbers, and extends earlier work that settled the graph case and the $r=3$ hypergraph case to all uniformities and all numbers of colours. The proof builds the host from a bounded-degree expander graph raised to a large power, and shows through a hierarchy of ordered tree families that any colouring avoiding long monochromatic tight paths would carry an impossible amount of structure. The paper also states that the same machinery yields linear size-Ramsey bounds for powers of tight paths, tight hypergraph trees, and long subdivisions of bounded-degree hypergraphs.","feed_headline":"Tight paths in hypergraphs have linear size-Ramsey numbers","feed_subtitle":"O(n) edges always force a monochromatic copy of the n-vertex tight path, for every fixed r and s","key_machinery":"The argument is carried by a hierarchy of rooted, ordered forests attached to the vertices of a bounded-degree $\\varepsilon$-expander graph $G$. The host hypergraph is $G^{p'}$, the $r$-uniform hypergraph whose edges are $r$-tuples of vertices pairwise within distance $p'$ in $G$. A colouring with no long monochromatic tight path is shown to be $k$-disconnected: no short monochromatic tight walk joins two independent $(r-1)$-sets of leaves of the same 'type' in nearby trees. Ramsey properties of powers of expanders (Lemma 3.9) then force either a long monochromatic path in an auxiliary colouring or many disjoint monochromatic cliques; each clique is used to 'augment' the forest into taller trees that remain disconnected, while Lemma 4.25 bounds the possible height of any such disconnected family. The contradiction proves the existence of a long monochromatic tight walk in the original colouring.","core_discovery":"On the paper's own terms, the central claim is Theorem 1.1: for fixed integers $r,s \\ge 1$, the $s$-colour size-Ramsey number of the $r$-uniform tight path $P_n^{(r)}$ is $O(n)$. Equivalently, for any fixed uniformity and any fixed number of colours, an $n$-vertex hypergraph with $O(n)$ edges can be built that is Ramsey for that path in every colouring. The stronger technical engine is Theorem 5.1, which produces, for every $r \\ge 3$ and $s \\ge 2$, a bounded-degree $n$-vertex $r$-uniform hypergraph in which every $s$-colouring contains a monochromatic tight walk of length $\\Omega(n)$ that uses each vertex only a bounded number of times; a short blow-up argument converts such a walk into an actual tight path. This settles in the affirmative the 2017 question and supersedes the previous $O((n \\log n)^{r/2})$ upper bound for $r \\ge 4$.","pith_inferences":["Beyond the paper: the constants hidden in the $O(n)$ bound grow rapidly with $r$ and $s$, and known lower bounds suggest the linear coefficient genuinely depends on both parameters; determining the correct order in $r$ and $s$ is a natural next problem.","Beyond the paper: the expander-power construction is a plausible template for proving linear size-Ramsey bounds for other sparse hypergraph families, such as bounded-degree tight trees or grid-like hypergraphs, by adapting the tree-hierarchy and type machinery.","Beyond the paper: the contradiction is formulated in terms of monochromatic tight walks with bounded vertex repetition, a stronger notion than simple paths, so the method may transfer to 'blow-up Ramsey' problems or to structured walks in other sparse hypergraphs."],"forward_implications":["For every fixed $r$ and $s$, $\\hat{r}_s(P_n^{(r)}) = O(n)$, so the size-Ramsey number matches the order of the number of vertices of the target path.","The result holds for an arbitrary fixed number of colours, not just two, and the host hypergraph can be chosen with maximum degree bounded by a constant depending only on $r$ and $s$.","The earlier upper bound $O((n \\log n)^{r/2})$ for $r \\ge 4$ is improved to linear, and the $r=3$ case is recovered as a special case.","A monochromatic tight walk with bounded vertex repetition can be converted into a genuine monochromatic tight path, so the proof's walk-based formulation directly implies the path statement.","According to the paper, the same proof approach also gives linear size-Ramsey numbers for powers of tight paths, tight hypergraph trees, and long subdivisions of bounded-degree hypergraphs."],"supporting_citations":[{"why":"Posed the question this paper resolves and introduced the size-Ramsey problem for hypergraphs.","marker":"[21]"},{"why":"Supplies Lemma 3.2, the existence of arbitrarily large bounded-degree expanders used to build the host hypergraph.","marker":"[38]"},{"why":"Provides the path-partition lemma used in Lemma 3.3 to prove the bipartite Ramsey lemma for expander powers.","marker":"[6]"},{"why":"Gives the previous best upper bound for $r \\ge 4$ that Theorem 1.1 improves.","marker":"[39]"},{"why":"Established the $r=3$ case that this paper extends to all uniformities and colours.","marker":"[31]"},{"why":"Introduced the expander-power construction for path powers that supplies the structural template for the host hypergraph.","marker":"[12]"}],"fun_headline_variants":["Tight path size-Ramsey numbers are linear for all fixed r and s","O(n) edges suffice to force a monochromatic tight path","Linear size-Ramsey for tight paths answers 2017 question","Size-Ramsey of tight paths is O(n), settling Dudek et al"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that arbitrarily large connected expander graphs of bounded degree exist for every small expansion parameter; the paper cites this to an unpublished companion manuscript and offers only a brief probabilistic sketch, yet the host hypergraph cannot be built without such graphs.","fun_headline_variants_meta":{"raw":{"variants":["Tight path size-Ramsey numbers are linear for all fixed r and s","O(n) edges suffice to force a monochromatic tight path","Linear size-Ramsey for tight paths answers 2017 question","Size-Ramsey of tight paths is O(n), settling Dudek et al"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001077,"raw_usage":{"total_tokens":4459,"prompt_tokens":850,"completion_tokens":3609,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":466,"completion_tokens_details":{"reasoning_tokens":3538}},"tokens_in":466,"tokens_out":3609,"duration_ms":34559,"temperature":1.0,"reasoning_tokens":3538,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:54:03.574096+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct refutation would be a sequence of $r$-uniform hypergraphs with $O(n)$ edges and bounded maximum degree whose edges can be $s$-coloured so that every monochromatic tight path has $o(n)$ vertices. Concretely, finding such a construction for $r=3$, $s=2$ for infinitely many $n$ would contradict Theorem 1.1, since the theorem promises that every $O(n)$-edge bounded-degree host forces a monochromatic tight path of linear length.","supporting_citations":[{"cited_title":"Dudek, S","cited_arxiv_id":null,"evidence_quote":"Posed the question this paper resolves and introduced the size-Ramsey problem for hypergraphs."},{"cited_title":"Ben-Eliezer, M","cited_arxiv_id":null,"evidence_quote":"Provides the path-partition lemma used in Lemma 3.3 to prove the bipartite Ramsey lemma for expander powers."},{"cited_title":"Lu and Z","cited_arxiv_id":null,"evidence_quote":"Gives the previous best upper bound for $r \\ge 4$ that Theorem 1.1 improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Established the $r=3$ case that this paper extends to all uniformities and colours."},{"cited_title":"Clemens, M","cited_arxiv_id":null,"evidence_quote":"Introduced the expander-power construction for path powers that supplies the structural template for the host hypergraph."}],"review_version":1}