{"id":"aabcb448-2334-4077-9c1f-ef5048debfa8","arxiv_id":"2505.18014","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Improved asymptotic upper bounds on the geometric k-colored crossing constant for k=2,...,10, such as cr_2 <= 0.11731412 and cr_3 <= 0.06062466.","lead":"This paper finds new upper bounds on how few same-colored crossings are necessary when the complete graph K_n is drawn with straight edges colored in k colors. The bounds for k=2 through 10 improve on earlier constructions, for k=3 through 10 by a factor of about 3.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The asymptotic bound rests on an unproved five-entry classification of offset pairs (o1,o2); if a legal detail choice yields (2,0) or o2=2, the closed forms in Appendix C and every Table 1 bound collapse.","rationale":"The reader's weakest assumption identifies the completeness of the offset-pair table as the pivotal trust point, and my reading agrees: the entire asymptotic machinery in Section 3 and the numerical bounds in Table 1 reduce to this finite combinatorial classification. The paper's own text admits the proof is a short case distinction, and the details are not provided. I did not find a more fundamental flaw: the crossing count in Theorem 1 is a standard recursive count, the matching construction is locally consistent, and the t=0 check α+β+γ+δ=cr_k(P0;χ0) is consistent with the closed forms. The external data artifact [15] affects reproducibility, not the validity of the method, and is secondary. An independent exhaustive check of the offset classification, or an independent derivation of Appendix C, would settle the concern. Since the reader already issued a conditional verdict, my stress-test does not change that assessment.","tokens_in":10711,"tokens_out":14755,"duration_ms":122607,"concrete_test":"Enumerate all legal detail choices at a vertex p, i.e., all allowed choices for m1(p1) ∈ {p2, q1, q2} and m1(p2) ∈ {q1, q2} (with m1(p2)≠p1 disallowed), and all sibling-edge colors χ1(p1p2) ∈ {1,...,k}. For each color c and each side d ∈ {ℓ,r}, compute the offset pair (o1,o2) by counting the remaining edges among {p1p2,p1q1,p1q2} and {p2p1,p2q1,p2q2} that lie on side d of the respective matching edge, using a symbolic infinitesimal perturbation of the collinear split to resolve degeneracies. If any legal choice yields a pair outside the five-entry set, the theorem fails; if all choices stay within the set, the case distinction is confirmed. Additionally, recompute the Appendix C closed forms symbolically from the recurrence to catch algebra errors in α.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 and the resulting bound cr_k ≤ 24α/|P0|^4 depend on the claim that for every legal choice of details, the offset pairs (o1,o2) in the recurrence for S^d_c are restricted to the five entries {(0,0),(0,1),(1,0),(1,1),(2,1)}. This is asserted in Section 3 with a 'short case distinction' but is not proved there or in Appendix B; Appendix B only solves the recurrence conditional on given offsets. In particular, the claims o2≤1 and (o1,o2)≠(2,0) are load-bearing: if a legal detail choice produced (2,0), the corresponding closed forms B(2,0) and C(2,0) would be needed, and the closed forms in Appendix C (and hence the formula for α) would be incomplete. Because the numerical bounds in Table 1 are computed from α using these closed forms, an unverified gap in this case distinction would invalidate all claimed improvements, not just the constants. The rest of the construction (Theorem 1 counting, the bipartite matching optimization for details) is internally plausible and the dependence on the initial heuristic seeds is a separate, secondary verification concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a general doubling construction for bounding the geometric k-colored crossing number of complete graphs. Starting from a small k-edge-colored straight-line drawing (a point set with a coloring, a matching, and local \"details\"), the authors define an iterated subdivision of vertices that yields drawings of K_n for exponentially growing n. Theorem 1 gives an exact recurrence for the number of monochromatic crossings, and Theorem 2 states that after t iterations the crossing count has the form α16^t + β8^t + γ4^t + δ2^t. The asymptotic constant is then bounded by 24α/|P0|^4. The authors compute optimal matchings via a bipartite matching formulation and use heuristic seeds for k=2..10, obtaining improved upper bounds, e.g., cr_2 ≤ 0.11731412 and cr_3 ≤ 0.06062466.","tokens_in":10987,"tokens_out":14849,"duration_ms":104757,"significance":"If the proof is completed, this is a substantial contribution. The construction generalizes the halving-matching technique of [5] to arbitrary k and yields the first improvements over the book-crossing-number upper bounds for k≥3, by a factor of about 3; it also slightly improves the k=2 bound. The theoretical framework is elegant: the crossing counting in Theorem 1 is a careful case analysis, the matching optimization is polynomial-time and provably optimal for a fixed seed, and the method gives explicit formulas for the asymptotic coefficient α. The companion artifact [15] supports reproducibility. The main weakness is a missing proof of the offset classification that the closed-form formulas and all numerical bounds depend on.","major_comments":[{"comment":"The classification of offset pairs (o1,o2) into the five entries of the table is asserted but not proved. The text claims \"o2 ≤ 1\" and \"if o1 = 2, then o2 ≠ 0 as is apparent from a short case distinction,\" but no case distinction is provided. Appendix B proves Lemma 1, which only derives closed forms for given o1,o2; it does not establish the restriction of the offsets to the five allowed pairs. Since the closed forms for B(o1,o2) and C(o1,o2) in Appendix C are given only for those five pairs, and the formula for α in Theorem 2 depends on summing over exactly these pairs, any missing pair (e.g., (2,0) or o2=2) would invalidate the asymptotic coefficient and all numerical bounds in Table 1. This is load-bearing and must be fixed by a rigorous proof of the offset classification.","section":"Section 3 (paragraph after Eq. (5))"},{"comment":"The closed forms for A, B, and C are stated without derivation. The proof of Theorem 2 relies on these formulas, including the sign claims α>0 and β<0. While long computations are often omitted, these formulas directly determine the numerical bounds; the authors should either include the derivation or at least provide a verifiable method (e.g., a computer algebra script) so that the formulas can be checked independently.","section":"Appendix C"}],"minor_comments":[{"comment":"In the displayed formula after Eq. (5), the exponent \"16^{t-i-i}\" appears; this should be \"16^{t-i-1}\".","section":"Section 3, Eq. (6)"},{"comment":"The abstract uses the notation \\overline{\\overline{\\text{cr}}}_k(K_n), while the body consistently uses cr_k(K_n); please align the notation.","section":"Abstract and Section 1"},{"comment":"The last term in the displayed formula has an unclosed bracket: \"[S^ℓ_{c(p)}(p_i^j) + S^r_{c(p)}(p_i^j)\" should have a closing bracket.","section":"Theorem 1, Eq. (5)"},{"comment":"The proof states \"α>0 and β<0 follow from the signs of the relevant coefficients in the closed formulas when |P0|≥3\" without specifying which coefficients; please expand this argument.","section":"Section 3, proof of Theorem 2"},{"comment":"The numerical results depend on the external artifact [15]; the paper should describe the verification steps (e.g., how the Python script computes cr_k(P_k;χ_k) and the bound) and provide a version identifier or checksum, so that Table 1 can be independently reproduced.","section":"Section 4"},{"comment":"The heuristic search is described only at a high level; please give concrete parameter settings (e.g., number of iterations, perturbation size, MAX-k-CUT heuristic used) for reproducibility.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the unproved offset classification in Section 3. If it is correct, the paper is likely acceptable; if any legal detail choice violates the five-entry table, the claimed bounds collapse. The artifact [15] should be vetted by the editorial office, for instance by running the provided script to confirm the values in Table 1. The heuristic nature of the seeds is acceptable for upper bounds, but the authors should make explicit that the constants are conditional on the correctness of the seed data."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know about this one: the paper is a genuine advance on the geometric k-colored crossing constant, and the numerical table is trustworthy in the sense that nothing is fitted. The authors generalize the 2-color halving-matching doubling construction to arbitrary k, make the per-vertex detail selection an independent optimization, and prove the optimal matching can be found in polynomial time via a min-weight bipartite matching. For k=3..10 this yields upper bounds about a factor of three below the old book-crossing bounds; for k=2 the gain over [5] is only about 0.6%, so the k≥3 results are the real news.\n\nWhat is good: the crossing count in Theorem 1 is a credible four-case analysis and the asymptotic reduction to cr_k ≤ 24α/|P0|^4 is correct. I spot-checked B(0,0) against a direct summation and it matches, so the closed forms in Appendix C are probably right even if 'straightforward but long' is doing heavy lifting. The matching-optimality argument is clean and goes beyond [5], whose matchings were not known optimal. Shipping the seeds and a verification script in a data artifact is good practice for an upper-bound construction.\n\nWhere it is soft: the five-entry offset-pair table in Section 3 is load-bearing and asserted, not proved. All the Appendix C formulas and every Table 1 bound assume that no legal detail choice produces (o1,o2)=(2,0) or o2=2. The case distinction is finite and the claims look plausible, but 'a short case distinction' is not a proof, and the referee should require it to be written out. The derivations behind Appendix C should also be included or at least sketched far more thoroughly. The external seed data is a secondary reproducibility concern: any valid seed gives a valid upper bound, so this is not circularity, just something to check.\n\nBottom line: the central construction holds up and the improvements are real. This is a paper for crossing-number people and computational geometry readers who want the current best constants. With the offset case analysis filled in it is publication-ready; even as it stands it deserves a serious referee, not a desk rejection.","headline":"A solid generalization of the 2-color halving-matching construction that gives real factor-three improvements for k≥3; everything rests on an asserted offset-pair table the referee should make the authors prove.","tokens_in":11525,"tokens_out":7046,"would_cite":true,"duration_ms":70157,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every seed drawing with at least three points doubles into an exact four-term crossing formula, yielding record upper bounds on the geometric k-colored crossing constant for k=2,...,10.","keywords":["geometric k-colored crossing number","crossing number","complete graph","rectilinear crossing","doubling construction","halving matching","MAX-k-CUT","asymptotic upper bounds"],"falsifier":"Take the published seed instances [15], enumerate all legal detail choices at every vertex, and compute the resulting offset pairs (o1, o2); finding any legal choice with o2 = 2 or with (o1, o2) = (2, 0) would refute the Appendix B table and break the closed-form coefficient formulas. Independently, re-running the supplied Python script should reproduce the seed crossing counts used in Table 1, such as cr_2(P_2; chi_2) = 1468394 and the reported bound 0.11731412; a mismatch would invalidate the numerical constants.","tokens_in":10477,"feed_emoji":"📐","tokens_out":5567,"duration_ms":42707,"temperature":0.7,"pith_summary":"The paper gives a way to build straight-line drawings of arbitrarily large complete graphs with few monochromatic crossings, starting from a small seed drawing. It proves that iterating a vertex-doubling construction for t steps produces an exact crossing count of the form $\\alpha$*2^(4t) + $\\beta$*2^(3t) + gamma*2^(2t) + delta*2^t, so the asymptotic density of monochromatic crossings depends only on quantities computed from the seed. For k=2 through 10, the authors carry this out on heuristic seed drawings, obtaining the best known upper bounds for the geometric k-colored crossing constant, including cr_2 <= 0.11731412 and cr_3 <= 0.06062466. If correct, these bounds replace the previous book-crossing-based bounds for k>=3 by a factor of about three.","feed_headline":"Doubling seeds yields best k-colored crossing bounds for k=2..10","feed_subtitle":"An exact four-term formula turns small seed drawings into record upper bounds on the k-colored crossing constant.","key_machinery":"The machinery is an iterated doubling construction: each vertex is replaced by two nearby children along the line spanned by its matching edge, edges between different parents inherit their parent's color, and each parent makes local choices for the sibling edge color and for the matching edges of its two children. The argument is carried by a recurrence for the numbers S_d^c(p) of incident edges of each color on each side of a matching edge, whose offsets (o1, o2) are restricted to five cases by the table in Appendix B. Closed forms for the sums A, B, and C in Appendix C turn the recurrence into the exact four-term formula of Theorem 2, and the leading coefficient $\\alpha$ is computed by summing per-vertex local contributions.","core_discovery":"The central claim is that for any seed point set P0 with |P0| >= 3, any k-edge-coloring, any matching, and any legal choice of local details, the doubling construction yields cr_k(P_t; chi_t) = $\\alpha$ * 2^(4t) + $\\beta$ * 2^(3t) + gamma * 2^(2t) + delta * 2^t, with $\\alpha$ > 0, $\\beta$ < 0, and $\\alpha$ + $\\beta$ + gamma + delta equal to the seed's monochromatic crossing count. The asymptotic k-colored crossing constant therefore satisfies cr_k <= 24 $\\alpha$ / |P0|^4. Table 1 lists the resulting numerical bounds: cr_2 <= 0.11731412, cr_3 <= 0.06062466, cr_4 <= 0.03572151, and so on down to cr_10 <= 0.00692671, improving on all previous upper bounds for k >= 2.","pith_inferences":["The exact four-term form suggests the doubling construction behaves like a linear dynamical system with growth factor 16 = 2^4, so the leading coefficient alpha might be expressible directly from per-vertex local data, opening the door to optimizing over colorings as well as matchings.","Because matching optimization is polynomial once the coloring is fixed, alternating between MAX-k-CUT coloring heuristics and exact matching optimization is a natural way to search for even stronger seeds beyond the heuristic search reported.","The five-case offset table effectively classifies the local behavior of the recurrence, so exhaustively enumerating all legal detail choices on a seed is a cheap computation that would either certify the table for that seed or expose a counterexample.","A similar doubling recurrence might improve the uncolored rectilinear crossing constant cr_1 if a one-color analogue of the offset analysis can be made to work."],"forward_implications":["Any seed with at least three points yields a provable asymptotic upper bound on the k-colored crossing constant, so progress reduces to finding better seeds.","For a fixed seed and coloring, the matching minimizing the asymptotic coefficient can be found in polynomial time as a minimum-weight saturating matching in a bipartite graph.","The improved bounds supersede the book-crossing-number bound 2/k^2 - 1/k^3 for k=3,...,10 by a factor of about three, and improve the previous best bound for k=2.","The construction works for every fixed k, so new seeds for larger k would immediately give the first improved bounds there too."],"supporting_citations":[{"why":"Supplies the original doubling construction with halving matchings that this paper generalizes from one color to k colors.","marker":"[2]"},{"why":"Provides the 2-colored crossing number instance and halving-matching approach whose bound this paper improves.","marker":"[5]"},{"why":"Contains the seed point sets, colorings, matchings, and Python script that determine the reported numerical bounds.","marker":"[15]"},{"why":"The Hungarian method is used to find the minimum-weight saturating matchings that minimize the asymptotic coefficient alpha.","marker":"[17]"},{"why":"Supplies the MAX-k-CUT heuristics used to find the low-crossing k-edge-colorings of the seed instances.","marker":"[22]"},{"why":"One of the book-crossing-number constructions that gave the previous upper bounds which Table 1 improves.","marker":"[10]"},{"why":"The other independent book-crossing-number construction providing the old upper bounds for k >= 3.","marker":"[24]"}],"fun_headline_variants":["Seed doubling improves k-colored crossing bounds","Tighter k-colored crossing bounds via seed doubling","Doubling seeds sharpen k-colored crossing bounds","New record bounds for k-colored crossings from seeds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole computation rests on the case analysis in Appendix B: every legal choice of local details must yield one of the five offset pairs, with o2 <= 1 and (o1, o2) = (2, 0) impossible; if any legal choice lies outside that table, the closed formulas and every numerical bound in Table 1 fail.","fun_headline_variants_meta":{"raw":{"variants":["Seed doubling improves k-colored crossing bounds","Tighter k-colored crossing bounds via seed doubling","Doubling seeds sharpen k-colored crossing bounds","New record bounds for k-colored crossings from seeds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000375,"raw_usage":{"total_tokens":1967,"prompt_tokens":882,"completion_tokens":1085,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":1029}},"tokens_in":498,"tokens_out":1085,"duration_ms":8705,"temperature":1.0,"reasoning_tokens":1029,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:37:40.024064+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the published seed instances [15], enumerate all legal detail choices at every vertex, and compute the resulting offset pairs (o1, o2); finding any legal choice with o2 = 2 or with (o1, o2) = (2, 0) would refute the Appendix B table and break the closed-form coefficient formulas. Independently, re-running the supplied Python script should reproduce the seed crossing counts used in Table 1, such as cr_2(P_2; chi_2) = 1468394 and the reported bound 0.11731412; a mismatch would invalidate the numerical constants.","supporting_citations":[{"cited_title":"Geometric Drawings ofKn with Few Crossings","cited_arxiv_id":null,"evidence_quote":"Supplies the original doubling construction with halving matchings that this paper generalizes from one color to k colors."},{"cited_title":"On the 2-Colored Crossing Number","cited_arxiv_id":null,"evidence_quote":"Provides the 2-colored crossing number instance and halving-matching approach whose bound this paper improves."},{"cited_title":"Instances with Low Geometric k-Colored Crossing Number","cited_arxiv_id":null,"evidence_quote":"Contains the seed point sets, colorings, matchings, and Python script that determine the reported numerical bounds."},{"cited_title":"An Upper Bound to the Crossing Number of the Complete Graph Drawn on the Pages of a Book","cited_arxiv_id":null,"evidence_quote":"One of the book-crossing-number constructions that gave the previous upper bounds which Table 1 improves."}],"review_version":1}