{"id":"bc57f144-e15a-48ca-b82a-b8c65acd8152","arxiv_id":"1908.06461","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For large n, the minimum number of monochromatic crossings in any 2-colored straight-line drawing of K_n is Θ(n^4), between 1/33 and 0.11798016 times C(n,4).","lead":"The paper proves the first asymptotic lower and upper bounds for the rectilinear 2-colored crossing number of complete graphs, roughly between 0.0303 and 0.11798 times C(n,4). It also shows that for any fixed straight-line drawing of K_n, two-colorings beat the trivial half-crossing bound by a constant margin.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's constant rests on unstated hypotheses for the 135-vertex seed: Theorem 1's closed form assumes m even and no Case 5, but the seed is odd and Case 5 is not ruled out.","rationale":"The reader's identification of the missing no-Case-5 hypothesis is accurate, and I regard it as the main threat to the paper's central numerical upper bound. I additionally note a closely related hypothesis mismatch: the 135-vertex seed is odd, while the proof of Theorem 1 explicitly assumes m is even and relies on odd degree to guarantee a strict larger color class at every vertex. The paper's remark that odd cardinalities can be handled does not certify the seed, nor its first duplication, against the relevant failure modes, namely balanced color classes or a resulting non-halving matching. These are not accusations of error; the data are published and the gap is checkable, but they are exactly the places where the proof as written stops short of Theorem 2. I do not see a comparable flaw in the Theorem 4 ratio argument beyond minor indexing typos, and the small-set lower-bound values are deferred to a thesis, which is a reproducibility gap rather than a mathematical contradiction. If the concrete test confirms no Case 5 and strict color classes, the paper's conditional acceptance stands; if it fails, the stated constant would need recomputation. Hence no verdict change from the reader's conditional verdict is warranted.","tokens_in":18582,"tokens_out":15293,"duration_ms":156305,"concrete_test":"Download the published n=135 data (coordinates, edge colors, and χ-halving matching) from crossingnumbers.org. For each vertex, compute Ll, Lr, Sl, Sr for its matched edge and verify that a strict larger color class exists and that the vertex falls in one of Cases 1, 2, 3, 4, or 6 (i.e., no Case 5). Then recompute the constant 24A/m^4 using the formula in Claim 2 and compare it to 182873519/1550036250. If any vertex is in Case 5 or has equal color-class sizes, repeat the computation on the 270-vertex set obtained after one duplication and check whether the resulting constant still satisfies ≤ 0.11798016; if it does not, Theorem 2's numerical bound is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2's numerical upper bound cr2 ≤ 182873519/1550036250 is obtained by plugging a specific 135-vertex drawing D with coloring χ into the duplication machinery of Theorem 1. The proof of Theorem 1, however, only derives the closed form cr2(Q_k,χ_k) = A·24^k + B·23^k + C·22^k + D·2^k under conditions that are not stated in the theorem and are not verified for D. First, Section 2 fixes m to be even, and the proof uses 'as |P| is even, the degree of p is odd and hence L(p) contains at least one more edge than S(p)' to guarantee that every vertex has a strict larger color class. The seed has 135 vertices, so m is odd and a vertex can have equally many red and blue incident edges, making L(p)/S(p) undefined; the remark that odd cardinalities can be handled only warns that the resulting matching might not be χ′-halving, and it does not prove that the 135-point set, or its first duplication to 270 points, satisfies the hypotheses needed to iterate Claim 2. Second, after defining Cases 1–6, the proof states 'we assume that P is such that no point of P falls in Case 5 either', and the sums in Appendix A.3 for the closed form simply omit Case 5. The 135-vertex seed is not shown to avoid Case 5. If the seed has a Case 5 point or a balanced color class at some vertex, the specific constant in Theorem 2 is not justified by the proof as written; a different calculation would be needed, for example after one duplication to a 270-point set. This is the load-bearing step for the paper's main upper bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper investigates the rectilinear 2-colored crossing number cr_2(K_n), defined as the minimum number of monochromatic crossings over all straight-line drawings of K_n and all 2-edge-colorings. The main results are: an upper bound cr_2(K_n) ≤ 182873519/1550036250 * C(n,4) + Θ(n^3), obtained from a duplication process seeded with a 135-vertex 2-colored drawing; a lower bound cr_2(K_n) ≥ 1/33 * C(n,4) + Θ(n^3), derived from exact values cr_2(K_10)=5 and cr_2(K_11)=10 computed via ILP over all order types; and a proof that for every sufficiently large straight-line drawing D of K_n, cr_2(D)/cr(D) < 1/2 - c for a positive absolute constant c, via the positive fraction Erdős–Szekeres theorem. The paper also shows that the biplanar crossing number of K_9 is 1 while cr_2(K_9)=2, and analyzes the ratio for convex and double-chain drawings.","tokens_in":18989,"tokens_out":17221,"duration_ms":155221,"significance":"The duplication framework for the 2-colored setting is a natural and potentially influential extension of the classical method for the rectilinear crossing number; the explicit closed-form duplication formula and the use of small seeds to obtain asymptotic constants are valuable ideas. The lower-bound methodology (reducing asymptotics to exact small cases via ILP) and the improvement over the trivial 1/2 ratio for fixed drawings are also of interest. The authors have made their best seed data available online, which supports reproducibility. If the gaps identified below are repaired, the paper would be a solid contribution to crossing-number theory.","major_comments":[{"comment":"The statement of Theorem 1 assumes only that the starting set P has a χ-halving matching, but the proof uses two additional assumptions that are not stated: |P| is even, and no point of P falls in Case 5. The proof explicitly says 'we assume that P is such that no point of P falls in Case 5 either', and the closed form in Claim 2 (Appendix A.3) sums only over P2, P1∪P3, and P4∪P6, with no Case 5 term. A Case 5 edge (e ∈ L(p) with Ll(p)=Lr(p)) is a valid χ-halving edge, so the stated hypothesis does not exclude this case. As a consequence, Theorem 1 is not proved for all sets satisfying its stated hypotheses.","section":"Section 2, Theorem 1 and its proof"},{"comment":"The seed used for Theorem 2 has n=135 vertices, which is odd. The proof of Theorem 1 relies on |P| even to ensure that L(p) is strictly larger than S(p) at every vertex; the remark after the proof admits that for odd cardinality the resulting matching may not be χ′-halving. The paper does not verify that the 135-point seed, or the set obtained after one duplication to 270 points, satisfies the hypotheses needed to iterate Claim 2 (even parity, no Case 5, existence of a χ′-halving matching at each step). Therefore the numerical upper bound cr2 ≤ 182873519/1550036250 is not justified by the proof as written.","section":"Section 2, Theorem 2 and the 135-vertex seed"},{"comment":"In the final paragraph of the proof, the paper asserts '|C2| = ∑_{i=1}^m |E_i|', but E_i was previously introduced as the edge set of the drawing D_i, not as a set of crossings; the equality is unexplained and appears false. The subsequent bound '|E_i| ≥ c_4^4(1−4c_4)^{4i} n^4' is also dimensionally inconsistent, since |E_i| counts edges and the lower bound is of order n^4. The lower bound on |C2| is load-bearing for the conclusion cr2(D)/cr(D) < 1/2 − c. This counting step needs a corrected argument.","section":"Section 4, proof of Theorem 4"},{"comment":"The exact values cr2(K10)=5 and cr2(K11)=10, which yield the lower bound cr2 ≥ 1/33, are asserted with only a reference to a Master's thesis and an order-type database. Since these values are used as a central result, the paper should provide sufficient detail to make the computation reproducible, for example by including the ILP certificates or a precise description of the ILP and the exhaustive order-type verification for n=10 and n=11.","section":"Section 3, lower bound and exact small cases"}],"minor_comments":[{"comment":"In the sentence 'We color the edges of Fi with the same color and the edges of F′i−1 with the other color', the subscript 'i−1' appears to be a typo and should likely read 'F′i'.","section":"Section 4"},{"comment":"In the induction hypothesis for Case 2, the displayed tuple contains the expression '2jSr(p) + 2j−i', which mixes subscripts inconsistently; it should be a single consistent formula such as '2iSr(p) + 2i−1'.","section":"Appendix A.3, Case 2"},{"comment":"The theorem title contains a typo: 'F raction' should be 'Fraction' in 'Positive Fraction Erdős–Szekeres theorem'.","section":"Theorem 3"},{"comment":"The expression 'c4^4⌊|Xi|⌋^4/2' is typeset ambiguously; please ensure that the exponent on c4 and the floor brackets are clear.","section":"Theorem 4"},{"comment":"The data URL is helpful, but a versioned repository or DOI would make the computational results more durable and easier to cite.","section":"Footnote 5"}],"recommendation":"major_revision","confidential_remarks":"The paper's core results are likely correct and the duplication technique is genuinely novel for the 2-colored crossing number. The main issues are missing hypotheses in Theorem 1, the unverified applicability of the seed to those hypotheses, and a flawed-looking counting step in Theorem 4. These should be fixable in revision; I recommend major revision rather than rejection. The authors should also be asked to supply verifiable certificates for the exact values cr2(K10) and cr2(K11)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the core machinery is genuinely new: a duplication process that preserves a colored halving-matching structure and yields an asymptotic constant for the 2-colored rectilinear crossing number. The ratio result, using the positive-fraction Erdős–Szekeres theorem to show cr2(D)/cr(D) < 1/2 - c for every large drawing, is also a real advance over the generic 1/2 bound. Second, the main numerical upper bound is not fully justified as written. Theorem 1 is stated for any P with a χ-halving matching, but the proof explicitly assumes m is even and that no point of P falls in Case 5. The 135-vertex seed used for Theorem 2 is odd, and the paper does not check the no-Case-5 condition. The remark that odd cardinalities can be handled actually warns that the resulting matching might not be χ'-halving, so it does not bridge the gap. The constant 182873519/1550036250 is obtained by plugging that seed into the Theorem 1 machinery, but the machinery has not been proved to apply to it. This is a load-bearing gap for the upper bound, though it looks repairable: either verify the missing hypotheses for the 135-point set, or first duplicate to 270 vertices, re-check the hypotheses, and then run the process from an even seed.\n\nThe counting in Appendix A.3 is careful and mostly persuasive; the case analysis is extensive, and the closed forms for the four recurrence terms check out. The lower bound via Lemma 1 is fine, but it relies on exact ILP values for K10 and K11 that are cited to a Master's thesis rather than being fully documented in the paper. That is a reproducibility concern, not a mathematical flaw.\n\nWho should read this: people working on crossing numbers, geometric graph theory, and graph drawing algorithms. The duplication mechanism will be useful to them even with the present gap. I would send the paper to a serious referee, but with a request for major revision: state the hypotheses of Theorem 1 exactly, prove or verify them for the seed (or adjust the seed), and supply the ILP certificates or enough detail to make the lower bound reproducible.\n\nIn short: good ideas, skilled proof effort, but the main theorem as stated is bigger than the proof; a revision that tightens the statement and verifies the seed would make this a solid contribution.","headline":"The paper's new duplication mechanism and ratio theorem are genuinely useful, but Theorem 2's upper bound rests on unstated hypotheses about the 135-vertex seed; the gap looks repairable, so the paper deserves a serious referee but with a major-revision request.","tokens_in":19461,"tokens_out":3749,"would_cite":true,"duration_ms":34594,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62"],"pacs":[],"model":"deepseek-v4-flash","headline":"The rectilinear 2-colored crossing number of $K_n$ grows like a constant times $\\binom{n}{4}$, and that constant is at least $1/33$ and at most $0.11798016$.","keywords":["2-colored crossing number","rectilinear crossing number","complete graph","straight-line drawing","halving matching","edge coloring","order types","positive-fraction Erdős–Szekeres theorem"],"falsifier":"Inspect the published 135-vertex seed configuration, its 2-coloring, and its halving matching, and check whether any vertex has its matched edge in the larger color class with equal numbers of larger-color edges on both sides (the paper's Case 5). If such a vertex exists, the recurrence used for Theorem 2 is not the one proved, and the stated upper-bound constant is not justified by the supplied proof; if no such vertex exists, the gap is closed and the claimed constant stands.","tokens_in":18416,"feed_emoji":"📐","tokens_out":17808,"duration_ms":156004,"temperature":0.7,"pith_summary":"The paper studies the best way to color the edges of a straight-line drawing of the complete graph $K_n$ with two colors so that few crossings occur between edges of the same color. It establishes that the asymptotic rate of the unavoidable number of monochromatic crossings is a constant $\\mathrm{cr}_2$, and confines that constant to the interval $[1/33,\\ 0.11798016]$. The upper bound is reached by a duplication process: starting from a carefully computed 135-vertex drawing, each vertex is replaced by a nearby pair of clones, and the monochromatic-crossing count is tracked through the recursion. The paper also shows that in every sufficiently large straight-line drawing of $K_n$, an optimal 2-coloring leaves strictly less than half of the crossings monochromatic, improving the trivial random-coloring bound of $1/2$. These results pin down the asymptotic cost of using two colors to separate crossings in complete geometric graphs, and they separate the rectilinear 2-colored crossing number from the biplanar crossing number at $K_9$.","feed_headline":"The 2-colored crossing constant of K_n is between 1/33 and 0.118","feed_subtitle":"A duplication process turns a 135-vertex seed into bounds for all n; two colors also beat the trivial 1/2 ratio.","key_machinery":"The central object is the $\\chi$-halving matching. For a 2-coloring $\\chi$ of the edges of a straight-line drawing on a point set $P$, a $\\chi$-halving edge at $p$ is an incident edge whose line splits the larger color class at $p$ evenly, meaning the numbers of larger-color edges on the two sides differ by at most one; a $\\chi$-halving matching pairs every point with such an edge. The duplication process replaces each point $p$ by two nearby clones $p_1,p_2$ on the line of its matching edge. A six-case color assignment for the new clone–clone edge preserves the halving property in every case except Case 5, where the two clones fall into Cases 2 and 4. Iterating $k$ times gives a drawing of $K_{2^k m}$ whose monochromatic crossing count satisfies the exact recurrence $\\mathrm{cr}_2(Q_k,\\chi_k) = A 2^{4k} + B 2^{3k} + C 2^{2k} + D 2^k$; the leading coefficient $A$, divided by $m^4$ and scaled by $24$, is the asymptotic upper-bound constant. For the ratio theorem, the key ingredient is the positive-fraction Erdős–Szekeres theorem, which guarantees large subsets $Y_1,Y_2,Y_3,Y_4$ of vertices such that every transversal is a convex quadrilateral; crossing pairs from opposite parts can be colored oppositely so that at most a third of their crossings are monochromatic.","core_discovery":"For the rectilinear 2-colored crossing number of $K_n$, the paper's central claim is the existence of a limiting constant $\\mathrm{cr}_2 = \\lim_{n\\to\\infty} \\mathrm{cr}_2(K_n)/\\binom{n}{4}$ with $\\mathrm{cr}_2(K_n) = \\mathrm{cr}_2\\binom{n}{4} + \\Theta(n^3)$, together with the bounds $\\frac{1}{33} \\le \\mathrm{cr}_2 \\le \\frac{182873519}{1550036250} < 0.11798016$. The lower bound comes from exhaustive computation over all order types up to size 11, yielding $\\mathrm{cr}_2(K_9)=2$, $\\mathrm{cr}_2(K_{10})=5$, and $\\mathrm{cr}_2(K_{11})=10$, combined with a subset-counting lemma that amplifies a fixed-size bound to all $n$. The upper bound comes from a 135-vertex 2-edge-colored straight-line drawing with 1,470,756 monochromatic crossings and an associated $\\chi$-halving matching, fed into a doubling process that yields the closed form $A\\cdot 2^{4k} + B\\cdot 2^{3k} + C\\cdot 2^{2k} + D\\cdot 2^k$ for the $k$-th iterate. In addition, for every straight-line drawing $D$ of $K_n$ with $n$ sufficiently large, the paper proves $\\mathrm{cr}_2(D)/\\mathrm{cr}(D) < 1/2 - c$ for a positive absolute constant $c$, using the positive-fraction Erdős–Szekeres theorem to find large subsets whose crossing structure can be colored with a constant fraction of savings.","pith_inferences":["If the Case 5 condition fails for the published seed, the fix is likely a finite search: because Case 5 is not hereditary only at the initial step, any nearby locally optimized seed that avoids Case 5 would restore the upper-bound proof; the paper does not report such a check.","The closed-form duplication constants depend on the full left/right color-class counts at every vertex, so a good upper-bound seed should be selected for balanced color-class splits and small $\\mathrm{cr}_2$ simultaneously; the paper indicates this dependence but does not turn it into an optimization criterion.","The convex-position ratio $3/8$ plus the numerical observation that convex sets are worst among order types of size 10 suggests that convex position may maximize $\\mathrm{cr}_2(D)/\\mathrm{cr}(D)$ among all order types; checking all order types up to size 11 or 12 would test this conjecture directly.","The proof of Theorem 4 probably extends to $k \\ge 3$ colors by replacing four-part transversals with $k$-part convex subsets and coloring the parts cyclically; the paper does not state such an extension."],"forward_implications":["Because $\\mathrm{cr}_2(K_n)$ is asymptotic to $\\mathrm{cr}_2 \\binom{n}{4}$, the 2-colored crossing number has the same quartic order of growth as the uncolored crossing number; the paper's bounds put the constant between $0.03030$ and $0.11798$.","Combined with the known lower bound $277/729$ for the uncolored rectilinear crossing constant, the upper bound gives $\\mathrm{cr}_2/\\mathrm{cr} \\le 0.3105$, so an optimal 2-coloring of a well-drawn $K_n$ wastes less than a third of its crossings on same-color pairs.","For any fixed straight-line drawing of $K_n$ with $n$ large, the optimal 2-coloring keeps fewer than $1/2 - c$ of all crossings monochromatic for an absolute $c>0$; the trivial $1/2$ bound from random coloring is uniformly improved.","The exact value $\\mathrm{cr}_2(K_9)=2$ and the biplanar crossing number of $K_9$ being $1$ separate the rectilinear 2-colored crossing number from the biplanar crossing number.","The lower-bound amplification lemma converts any future improvement on a small fixed set into an improved lower bound for all $n$, so the asymptotic lower-bound problem reduces to finitely many small searches."],"supporting_citations":[{"why":"provides the halving-matching duplication process on which Theorem 1 is built","marker":"[3]"},{"why":"supplies the heuristic search and improved uncolored constants that motivate the seed-based upper-bound approach","marker":"[7]"},{"why":"gives the positive-fraction Erdős–Szekeres theorem used in the proof of Theorem 4","marker":"[11]"},{"why":"shows the limit defining the rectilinear crossing constant exists, which is cited to justify the existence of the 2-colored constant","marker":"[24]"},{"why":"supplies the improved crossing lemma that yields the first lower bound 3/116 for $\\mathrm{cr}_2$","marker":"[5]"},{"why":"introduces the parameter and the random-coloring bound 1/2 that Section 4 improves","marker":"[23]"},{"why":"supplies the lower bound 277/729 for the uncolored rectilinear crossing constant used to compute the ratio $\\mathrm{cr}_2/\\mathrm{cr} \\le 0.3105$","marker":"[4]"},{"why":"provides the order-type database over which the exhaustive $K_9$ computation runs","marker":"[6]"},{"why":"provides the enumeration of order types up to size 11 used for $\\mathrm{cr}_2(K_{10})$ and $\\mathrm{cr}_2(K_{11})$","marker":"[8]"},{"why":"details the integer-programming method that certifies the optimal colorings of all $K_9$ order types","marker":"[17]"}],"fun_headline_variants":["2-colored crossing constant of K_n: between 1/33 and 0.118","New bounds for 2-colored crossing number in K_n","Two-color edge crossings: K_n bounds 1/33 to 0.118","Constant for 2-colored crossing of K_n: 1/33 to 0.118","2-colored crossing in K_n: improved constants, 1/33–0.118"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the starting 135-vertex colored drawing has no vertex whose matched halving edge lies in the larger color class while that larger class is split exactly evenly to the left and right of the edge (the paper's Case 5); Theorem 1 is proved only under that assumption, the assumption is not part of the theorem statement, and the paper does not verify it for the seed configuration it uses in Theorem 2.","fun_headline_variants_meta":{"raw":{"variants":["2-colored crossing constant of K_n: between 1/33 and 0.118","New bounds for 2-colored crossing number in K_n","Two-color edge crossings: K_n bounds 1/33 to 0.118","Constant for 2-colored crossing of K_n: 1/33 to 0.118","2-colored crossing in K_n: improved constants, 1/33–0.118"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000928,"raw_usage":{"total_tokens":4024,"prompt_tokens":1044,"completion_tokens":2980,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":2871}},"tokens_in":660,"tokens_out":2980,"duration_ms":23281,"temperature":1.0,"reasoning_tokens":2871,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:44:33.739056+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect the published 135-vertex seed configuration, its 2-coloring, and its halving matching, and check whether any vertex has its matched edge in the larger color class with equal numbers of larger-color edges on both sides (the paper's Case 5). If such a vertex exists, the recurrence used for Theorem 2 is not the one proved, and the stated upper-bound constant is not justified by the supplied proof; if no such vertex exists, the gap is closed and the claimed constant stands.","supporting_citations":[{"cited_title":"Journal of Combinatorial Theory, Series A 114(2), 373–379 (2007)","cited_arxiv_id":null,"evidence_quote":"provides the halving-matching duplication process on which Theorem 1 is built"},{"cited_title":"Discrete & Com- putational Geometry 19(3), 335–342 (1998)","cited_arxiv_id":null,"evidence_quote":"gives the positive-fraction Erdős–Szekeres theorem used in the proof of Theorem 4"},{"cited_title":"Electronic Notes in Discrete Mathematics 30, 273–278 (2008)","cited_arxiv_id":null,"evidence_quote":"supplies the lower bound 277/729 for the uncolored rectilinear crossing constant used to compute the ratio $\\mathrm{cr}_2/\\mathrm{cr} \\le 0.3105$"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the order-type database over which the exhaustive $K_9$ computation runs"},{"cited_title":"Computational Geometry: Theory and Applications 36(1), 2–15 (2006)","cited_arxiv_id":null,"evidence_quote":"provides the enumeration of order types up to size 11 used for $\\mathrm{cr}_2(K_{10})$ and $\\mathrm{cr}_2(K_{11})$"},{"cited_title":"Master’s thesis, University of Technology Graz, Austria (2019)","cited_arxiv_id":null,"evidence_quote":"details the integer-programming method that certifies the optimal colorings of all $K_9$ order types"}],"review_version":1}