{"id":"042dded8-fe1b-4dd3-a493-ffda799d599d","arxiv_id":"2608.06369","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For all sufficiently large n, every properly edge-coloured n-vertex complete graph has a rainbow path on n-1 vertices, resolving Andersen's conjecture and its Latin-square analogue for large n.","lead":"This paper proves that every properly edge-coloured complete graph on sufficiently many vertices contains a rainbow path that visits all but one vertex, settling Andersen's 1989 conjecture for all large graphs. It also confirms the Gyárfás-Sárközy conjecture on cycle-free transversals in Latin squares for large orders, via a new structure called a Hamilton router.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim rests on an unproved strengthening of Montgomery's matching theorem: BPW requires C1* plus W3, justified only by a personal communication.","rationale":"The reader's weakest-assumption analysis and my own reading converge on the same point: the proof is detailed and internally consistent, but its central theorem depends on an external strengthening of Montgomery's matching theorem that is not fully proved here and is supported by a citation to personal communication. I re-checked the main internal mechanisms that could have provided an independent, more serious objection. The Hamilton-router vertex counts in Lemma 3.8 are consistent once \"m−4qn vertices\" is read as the total size of the subdivided abstract router; the nibble argument in Theorem 2.7 has the expected constants; the stability reduction in Section 5 is coherent; and the n−1 versus n−100 wording in Theorem 4.1's 'furthermore' is a minor statement typo, not a load-bearing flaw, because the proof only needs it for m≥n. The Latin-square case in Theorem 1.4 has a small unstated deletion of the colours in D when |D|≤1, but this is easily repaired and does not affect the main rainbow-path theorem. No internal inconsistency was found that would overturn the paper's conclusion if Theorem 2.1 holds. The honest verdict is therefore unchanged: the paper should be accepted only after the promised proof of Theorem A.4 is supplied, and the current conditional status accurately reflects that dependency.","tokens_in":44668,"tokens_out":47803,"duration_ms":535116,"concrete_test":"Independently re-derive Theorem A.4 from [42]: starting from the proof of [42, Theorem 3.1] and using exactly C1*, C2–C6, and C7*, verify that the final absorption step produces an (n−1)-edge rainbow matching when |C(G)|=n−1. In particular, write out the \"very minor adjustments\" alluded to after W3 and check whether W3's 2k-edge gadgets can absorb every possible set of leftover colours without ever using a spare colour to seed or close the absorber. If any step in the absorption argument silently uses the existence of an unused colour outside the matching, BPW fails; if the derivation goes through, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single load-bearing concern is that Theorem 2.1 is not actually proved in this manuscript for the BPW regime. Section 2.3 concedes that Theorem 2.1 \"is not stated directly in [42], though it follows from its proofs with minor modification,\" and Appendix A supplies only the pseudorandomness-inheritance half. The BPW case needs Theorem A.4, a strengthening of [42, Theorem 3.1] in which C1 is weakened to C1* (allowing n−1 colours) and C7 is strengthened to C7*. The manuscript justifies this by stating that W3 permits the final (n−1)-edge matching to use all colours, with \"very minor adjustments,\" and adds that the proof \"will be updated in the published version of that proof,\" citing [44]. No formal proof of this modification appears in the manuscript. Since Theorem 4.1, and therefore Theorems 1.2–1.4, invokes BPW through Theorem 2.1, a failure or a subtle missing case in the C1* absorption step would leave the main theorem without a foundation. The rest of the paper—Hamilton routers, the nibble argument, and the stability reduction—is internally coherent on spot checks, but it cannot compensate for this unverified external strengthening.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for sufficiently large n, every properly edge-coloured complete graph on n vertices contains a rainbow path on n−1 vertices, and if the colouring uses at least n colours, a rainbow Hamilton path (Theorem 1.2). It also proves a directed analogue for optimally coloured complete digraphs (Theorem 1.4), confirming the Gyárfás–Sárközy conjecture for large n, and a near-spanning rainbow cycle result (Theorem 1.3). The proof introduces Hamilton routers—sparse structures that connect a collection of vertex-disjoint rainbow paths into a single cycle—and combines them with randomly partitioned vertex/colour sets, a nibble-type matching lemma, and a stability reduction. The main technical engine is Theorem 4.1, which proves the result for (n,ε)-typical digraphs, and Theorem 2.1, a randomized rainbow-matching tool imported from Montgomery's Ryser–Brualdi–Stein proof [42].","tokens_in":44867,"tokens_out":14838,"duration_ms":152318,"significance":"If the proof is completed, this resolves Andersen's 1989 conjecture for all large n and improves the best previous bounds (n−O(n^{1/2} log n)) to n−1; for large odd n it also settles Hahn's original Hamilton-path conjecture. The Hamilton router is a novel and promising tool, and the reduction from arbitrary proper colourings to typical digraphs via Lemma 5.3 is elegant. The paper is generally careful and detailed: the case split in Theorem 4.1, the router construction in Section 3, and the stability arguments in Section 5 are all presented with concrete estimates. However, the proof depends at a critical point on a strengthening of Montgomery's matching theorem that is not proved in the manuscript and is relegated to a personal communication; this prevents the paper from being fully self-contained and currently blocks verification of the central claim.","major_comments":[{"comment":"The randomized rainbow-matching theorem (Theorem 2.1) is the foundation of Theorem 4.1, and its BPW case is derived from Theorem A.4, a strengthening of [42, Theorem 3.1] in which C1 is weakened to C1* and C7 is strengthened to C7*. The manuscript does not prove Theorem A.4; it says only that the proof of [42] 'will be updated in the published version of that proof' and cites a personal communication [44]. Because Theorem 4.1(1) and (2) invoke BPW, this unverified external strengthening is load-bearing for Theorems 1.2 and 1.4. Please include a complete proof of Theorem A.4 (or at least a fully detailed derivation of the W3-based adjustment) in the paper; a citation to an in-preparation update cannot substitute for a proof in a submitted manuscript.","section":"§2.3 and Appendix A.2 (Theorem A.4)"},{"comment":"The inheritance lemma (Lemma A.7) is the mechanism that produces strong-proper-pseudorandomness in the sampled graph D[X', C', Y']. The proof of property D7* is asserted to follow 'almost verbatim' from [42, Proposition 3.12], but the manuscript does not exhibit the adaptation to the boundary case |Y'| = |X'|−1, which is exactly where C1* becomes relevant. Since the strengthened absorption property W3 is the only reason [42, Theorem 3.1] can be pushed to n−1 colours, this is not a purely presentational point. The authors should either prove D7* directly or give a precise statement of the modification to [42, Claim 8] and Section 9.4.","section":"Appendix A.4, properties D7* and PrP.1"}],"minor_comments":[{"comment":"The phrase 'with endpoints in A×B' is ambiguous; it should say 'with one endpoint in A and the other in B'.","section":"Section 3.1, Definition 3.1"},{"comment":"The figure showing the comparator is not captioned in the text; please add a caption and refer to it explicitly when describing the paths Q_{1,3}, Q_{2,4}, Q_{1,4}, and Q_{2,3}.","section":"Section 3.1, Lemma 3.5"},{"comment":"In the definition of 'p-random', the set A is said to be a subset of V with each element included independently with probability p; this is standard, but the notation 'A⊂V' should be 'A⊆V' for clarity when p=0 or 1.","section":"Section 2.1, Notation"},{"comment":"The reference [44] is given as 'Personal communication, 2026'; this is not a stable citation for a load-bearing theorem. Please replace it with a published or arXiv source, or include the proof in the paper.","section":"Appendix A.2"},{"comment":"After deleting f and f', the path is stated to have n−1 vertices; because both dummy edges are incident to v2, the vertex v2 is isolated and the remaining vertices form a path. Please state this explicitly, since the Hamilton cycle has n vertices and the deletion step might otherwise appear to leave n vertices.","section":"Section 4, proof of Theorem 4.1, case (1)"}],"recommendation":"major_revision","confidential_remarks":"The paper is clearly written and the main ideas are strong, but the unresolved reliance on a personal communication is a serious obstacle. I would urge the editor to require the authors to supply the missing proof of Theorem A.4 (or to obtain a written version of the updated [42] proof) before further consideration. The strengthening to n−1 colours in the BPW case is exactly the step that makes Andersen's conjecture accessible, so it should be treated as a theorem to be proved in this paper, not as an external folklore fact. There is also a fine line between 'minor modification' and 'new theorem' here: the boundary case |Y'| = |X'|−1 in D7* is precisely where the strong-pseudorandomness property is needed, and the current text does not make the adaptation verifiable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The genuinely new thing is the Hamilton router—an O(n)-comparison relaxation of sorting networks that still routes any bijection into a single cycle. That is clever and real, and it is what lets the authors convert rainbow matching results into a rainbow path missing one vertex. Theorems 1.2–1.4 are the long-standing Andersen and Gyárfás–Sárközy conjectures for large n, so the stakes are high. On spot checks the proof is coherent: the cycle-to-path step lands on n−1 vertices, the case split m=n−1 versus m≥n is correct, and the stability reduction to Theorem 5.1 is plausible.\n\nThe soft spot is the one the stress-test flags, and I think it is genuine. Theorem 2.1 is load-bearing, and the BPW case needs a strengthening of Montgomery's theorem—C1* plus C7*—that is not proved here. The manuscript says it follows with 'very minor adjustments' and will be updated in the published version of [42], citing a personal communication. Appendix A proves the pseudorandomness inheritance but not the strengthened absorption step. So the main theorem currently rests on an unverified external result. This is a verifiability gap, not an internal contradiction I could find. If [42] as it will be published contains that step, the proof likely goes through; if not, the foundation collapses. A referee needs to check this specifically.\n\nThe rest of the paper is unusually careful: hierarchies are explicit, the nibble-type lemma is proved in the appendix, and the spot checks pass. The Hamilton router construction is a contribution that stands on its own as a technique.\n\nI'd send this to a serious referee and tell them to spend most of their time on Theorem 2.1 and Appendix A.2. I'd bring it to reading group and would cite the router construction regardless of how the gap resolves.","headline":"A serious, detailed proof of Andersen's conjecture for large n built on a genuinely new Hamilton router technique, with one load-bearing unverified strengthening of a co-author's theorem.","tokens_in":45541,"tokens_out":3194,"would_cite":true,"duration_ms":32007,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C38","05C70","05B15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that, once n is sufficiently large, every properly edge-coloured complete graph on n vertices contains a rainbow path on n−1 vertices, and, when at least n colours are used, a rainbow Hamilton path.","keywords":["rainbow paths","proper edge-colouring","complete graphs","Hamilton router","sorting networks","Latin square transversals","rainbow matchings","typical digraphs"],"falsifier":"Exhibit, for infinitely many large n, a properly edge-coloured complete graph on n vertices with no rainbow path on n−1 vertices; even one such graph would refute the central claim. For the proof's dependency, check whether the companion paper's published text actually implies the strengthened pseudorandomness properties C1* and C7* invoked in Appendix A: if not, Theorem 2.1, and with it Theorems 1.2–1.4, would not be established.","tokens_in":44366,"feed_emoji":"🌈","tokens_out":10305,"duration_ms":110806,"temperature":0.7,"pith_summary":"For every sufficiently large n, the paper proves that a properly edge-coloured complete graph on n vertices always contains a rainbow path — one whose edges all have distinct colours — on n−1 of the vertices. This settles a 1989 conjecture and strengthens it in the case where at least n colours are used, where a rainbow Hamilton path exists, so every large odd-order proper colouring has a Hamilton path. The same methods prove a directed version for optimally coloured complete digraphs, which says that every large Latin square has a cycle-free transversal of size n−2. The new object that carries the proof is a Hamilton router, a sparse routing structure that converts large rainbow matchings into long rainbow cycles and is built from just O(n) auxiliary vertices.","feed_headline":"Every large properly coloured complete graph has a rainbow path on n-1","feed_subtitle":"The 1989 rainbow path conjecture now holds for all sufficiently large n, and Latin squares get cycle-free transversals of size n-2.","key_machinery":"The load-bearing object is the Hamilton router. For disjoint sets A and B of equal size, an A,B-Hamilton router is a sparse subgraph such that, for every bijection $\\phi:A\\to B$, the vertex set can be partitioned into A-to-B paths whose union with the matching $\\{(\\phi(a),a)\\}$ is a single Hamilton cycle. This is a deliberate relaxation of a sorting network: a sorting network must realize arbitrary permutations, while a router only needs one cycle type, so a router can be built with $O(n)$ comparisons instead of $\\Omega(n\\log n)$. The construction first produces order-2 routers (comparators) of depth 9 inside typical properly coloured digraphs, using a theorem that finds long even cycles avoiding forbidden pairs and a short rainbow connecting lemma, then glues $qn$ of these comparators together. The router allows the host graph to be partitioned into O(1) random parts, so that a rainbow-matching black box can be applied in each part; the resulting rainbow path forest is then merged by the router into a single long rainbow cycle.","core_discovery":"The central claim is that, in a proper edge-colouring of a complete graph, the rainbow picture is complete up to one vertex. For all n ≥ n0, every such colouring of Kn contains a rainbow path on n−1 vertices; if it uses at least n colours it contains a rainbow Hamilton path; and every such colouring contains a rainbow cycle on at least n−C vertices for an absolute constant C. The proof also establishes the Latin-square version: every optimally coloured complete digraph on n vertices contains a rainbow directed path on n−1 vertices, equivalently a cycle-free transversal of order n−2 in the associated Latin square. These conclusions replace the earlier approximate bounds of order n−O($n^{{1/2}}$\\log n) with the optimal n−1 and resolve two longstanding conjectures for all large n.","pith_inferences":["The Hamilton router construction is a transferable template: any future strengthening of the underlying rainbow-matching theorem should lift, via the same router, to longer rainbow paths and cycles in complete digraphs.","The proof gives no explicit bound on n0, and the hierarchy of constants suggests the threshold is astronomically large; making it concrete would require a separate quantitative analysis.","One testable by-product: if the router can be built inside arbitrary properly coloured graphs without the typicality hypothesis used in the stability step, the conjectures would follow in full, not just for large n.","The directed Latin-square result hints that near-perfect rainbow matchings in pseudorandom bipartite graphs are equivalent, up to the Hamilton-router conversion, to near-perfect rainbow Hamilton paths in pseudorandom complete digraphs."],"forward_implications":["Every large properly coloured complete graph has a rainbow path missing at most one vertex, which is the best possible obstruction because even n can need n−1 colours.","Every large odd-order proper colouring has a rainbow Hamilton path, since any such colouring uses at least n colours; this is stronger than the usual Hamilton path statement.","Every large properly coloured complete graph has a rainbow cycle of length n−C, and a Hamilton cycle with at least n−2 distinct colours.","Every large Latin square contains a cycle-free transversal of order n−2, confirming the Latin-square conjecture for large n.","For sufficiently large sets of points with no three collinear, the points can be ordered so that consecutive connecting lines have distinct directions, giving a new proof of the direction-tree conjecture."],"supporting_citations":[{"why":"Supplies Theorem 2.1, the randomized rainbow-matching black box on which all the matching steps in the proof depend.","marker":"[42]"},{"why":"Provides the rainbow even-cycle theorem used to build order-2 Hamilton routers (comparators) inside typical coloured digraphs.","marker":"[32]"},{"why":"Gives the stability ingredient (a rainbow Hamilton cycle for colourings with few colours) needed to reduce the general case to the typical case.","marker":"[45]"},{"why":"Establishes the previous best approximate bound n−O(n^{3/4}\\log n) for long rainbow paths, which the new n−1 result improves.","marker":"[4]"},{"why":"Pushes the approximate bound to n−O(n^{1/2}\\log n), the comparison baseline quoted in the abstract and introduction.","marker":"[8]"}],"fun_headline_variants":["Andersen's rainbow path conjecture proven for large n","Every large proper complete graph colouring has a rainbow path on n-1","Rainbow path of n-1 vertices in all large properly coloured complete graphs","Optimal rainbow paths resolve Andersen's 1989 conjecture for large n","For large n, proper edge-colourings of complete graphs contain rainbow paths on n-1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on a randomized rainbow-matching theorem imported from a companion paper, and the exact form needed here is not stated in that paper; it is justified by a strengthening that the companion's published version is said to include. If that strengthening is not already implicit, the main theorems lack their foundation.","fun_headline_variants_meta":{"raw":{"variants":["Andersen's rainbow path conjecture proven for large n","Every large proper complete graph colouring has a rainbow path on n-1","Rainbow path of n-1 vertices in all large properly coloured complete graphs","Optimal rainbow paths resolve Andersen's 1989 conjecture for large n","For large n, proper edge-colourings of complete graphs contain rainbow paths on n-1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000404,"raw_usage":{"total_tokens":2063,"prompt_tokens":861,"completion_tokens":1202,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":477,"completion_tokens_details":{"reasoning_tokens":1103}},"tokens_in":477,"tokens_out":1202,"duration_ms":12694,"temperature":1.0,"reasoning_tokens":1103,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:14:03.274377+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit, for infinitely many large n, a properly edge-coloured complete graph on n vertices with no rainbow path on n−1 vertices; even one such graph would refute the central claim. For the proof's dependency, check whether the companion paper's published text actually implies the strengthened pseudorandomness properties C1* and C7* invoked in Appendix A: if not, Theorem 2.1, and with it Theorems 1.2–1.4, would not be established.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the rainbow even-cycle theorem used to build order-2 Hamilton routers (comparators) inside typical coloured digraphs."},{"cited_title":"Montgomery, A","cited_arxiv_id":null,"evidence_quote":"Gives the stability ingredient (a rainbow Hamilton cycle for colourings with few colours) needed to reduce the general case to the typical case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the previous best approximate bound n−O(n^{3/4}\\log n) for long rainbow paths, which the new n−1 result improves."},{"cited_title":"Balogh and T","cited_arxiv_id":null,"evidence_quote":"Pushes the approximate bound to n−O(n^{1/2}\\log n), the comparison baseline quoted in the abstract and introduction."}],"review_version":1}