{"id":"2bb28f57-677a-4513-99da-14444f277c0f","arxiv_id":"2505.24490","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The maximum number of edges in an outer k-planar graph on n vertices is at most (sqrt(2)+epsilon) sqrt(k) n plus a lower-order term, with epsilon tending to 0 as k grows.","lead":"This paper shows that any drawing of n points in convex position, where each segment crosses at most k others, contains at most about 1.41 times the square root of k times n segments. That improves the previous best bound of about 2.47 and gets closer to the known lower bound, using a new counting argument and a graph-cut result.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the apparent omission of length-1 diagonals in Theorem 10 is an indexing artifact, and the counting step is sound after the intended shift.","rationale":"I read the proof of Theorem 10 in good faith. The central claim is the asymptotic bound (√2+ε)√k n on diagonals, improving the previous best constant. The proof's strategy is sound: take a vertex-minimum counterexample, choose the shortest diagonal D of length at least l0, bound diagonals in the smaller side G1 by their possible lengths, apply minimality to G2, and derive that D is crossed more than k times. The only arguably weak step is the G1 count. Examining it carefully shows that the sum over p=2..l0 of (l+2-p) is exactly the number of chords in an (l+2)-gon whose smaller side has q=p-1 vertices, i.e., actual lengths 1..l0-1. So length-1 diagonals are not omitted in substance; the notation is off by one. Even if read literally as omitting them, the correction is O(l), and the final inequality has margin ε√k l, which dominates for any fixed ε > 0 and sufficiently large k. Therefore the reader's weakest assumption does not land as a fatal flaw. The manuscript still has genuine presentation issues (abstract omitting additive n, Theorem 19 not covering k=5,6, Theorem 20 formula typo, and several indexing inconsistencies), but these do not threaten the central asymptotic result. I therefore see no reason to change the CONDITIONAL verdict: the paper needs revision, but the main theorem is likely correct.","tokens_in":11730,"tokens_out":50148,"duration_ms":617133,"concrete_test":"Re-derive the diagonal count in G1 for a small explicit instance, e.g., l=4, l0=3, with outside vertices so that the full polygon has n>l+2 vertices. Enumerate all chords inside G1, compute their actual lengths with respect to the full n-gon, and verify that the paper's expression Σ_{p=2}^{l0}(l+2-p) equals the number of diagonals of actual length at most l0-1, including length 1. If the counts match, the Theorem 10 counting step is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest assumption targets the count of diagonals in G1 in the proof of Theorem 10. Under the paper's intended indexing, G1 has l+2 boundary vertices, and the number of diagonals with actual length q (q vertices on the smaller side) is l+1-q. The proof sums p=2..l0 of (l+2-p); substituting q=p-1 gives the identical expression sum_{q=1}^{l0-1}(l+1-q), which includes all actual length-1 diagonals. The text's 'length two' is a shifted label, not a genuine omission. Even under the alternative literal reading where actual length-1 diagonals are omitted, the omitted count is only l+1, and the corrected crossing lower bound becomes k + ε√k l - O(√k), which exceeds k for fixed ε > 0 and sufficiently large k because l ≥ l0 = √2√k. Thus the flaw, if any, is a presentational off-by-one, not a load-bearing mathematical gap. The central asymptotic claim of Theorem 10 and Corollary 11 is not endangered.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the maximum number of edges of an outer k-planar graph, i.e., a straight-line drawing of a graph on n points in convex position in which every edge crosses at most k other edges. The main contribution is a direct counting argument giving an upper bound of (√2+ε)√k n diagonals for sufficiently large k with ε→0, hence (√2+ε)√k n+n edges, improving the previous best 2.465√k n. The paper also gives three other upper-bound approaches with constants 2.85, 2.34, and 2√(k+1)+2, a small-k table, and a bipartite version of the problem. The bipartite part uses a maximum-cut bound for circulant graphs C_n^{1,...,r} and derives bounds for consecutive and alternating bipartite settings.","tokens_in":11832,"tokens_out":36046,"duration_ms":360139,"significance":"The claimed asymptotic bound √2√k n + n, if correct, is a substantial improvement over the previous best 2.465√k n and matches the order of the known lower bound √k n up to the constant. The proof is self-contained modulo known crossing lemmas and the cited spectral max-cut bound, and it does not rely on the author's own prior work for its main claim. The circulant maximum-cut lemma and the bipartite bounds are of independent interest. However, the manuscript contains several algebraic and range-of-validity errors in central and auxiliary proofs, so the current version needs revision before the results can be accepted.","major_comments":[{"comment":"The proof of Theorem 19 does not support the stated range k≥5. From m>2.228√k n one obtains |E(G')|> (4.456√k −1)n, not (4.06√k + (0.45√k−1))n; the displayed equality is algebraically false. Moreover, comparing the lower bound with 5.243√k n (the constant of Lemma 2) is inappropriate because Lemma 18 gives the relevant bound 4.06√k n. With Lemma 18, the argument yields a contradiction only when 4.456√k −1 > 4.06√k, i.e., k≥7. The theorem should be restated for k≥7 or supplied with a different argument.","section":"§5.2 (Theorem 19)"},{"comment":"The derivation of the main inequality contains a false equality. After substituting l0=√2√k, the lower bound on the number of crossings is (ε√k+1)l + k+1 −2ε√k −(7√2/2)√k, not k+1+ε√k l−2(√2+ε)√k−0.5√2√k. The displayed expression can be used as a (weaker) lower bound after replacing l by l0 in the linear term, but this replacement and the resulting inequality need to be stated explicitly. The asymptotic conclusion is unaffected, but as written the central chain of inequalities is not derivable.","section":"§3.5 (Theorem 10)"},{"comment":"The numerical claim that f(176)≈−0.4997 does not follow from the displayed formula f(r)=1/r+C0−8π²/(r+1) with C0≥−0.4344; for r=176 that expression is approximately −0.875 (or, with a squared denominator, about −0.431). Since the proof of Lemma 12 relies on f(176)>−1/2, the stated Mercer bound or its evaluation must be corrected. This is relevant for the bipartite upper bounds that use Lemma 12.","section":"§4 (Lemma 12)"}],"minor_comments":[{"comment":"In Theorem 20, the statement writes −(2k+5) in the numerator, but the proof derives −(2k+6) and the subsequent list of bounds for k=0,...,4 is consistent only with −(2k+6).","section":"Theorem 20"},{"comment":"In the proof of Theorem 10, the terms 'length two' and 'length three' are shifted by one relative to the definition of length in §2; the count of diagonals in G1 is correct after the intended reindexing, but the terminology should be clarified so the reader does not infer that length-1 diagonals are omitted.","section":"§3.5 (Theorem 10)"},{"comment":"There are several typos: 'meassured' in §3.5, 'imaginery' in §4, 'sraphs' in reference [14], and in Lemma 12 the Dirichlet kernel is written as D_r(2πk/n) although k has already been used for the summation index.","section":"Throughout"},{"comment":"In Theorem 15, '\\lfloor\\sqrt{k}/2\\rfloor' should presumably be '\\lfloor\\sqrt{k/2}\\rfloor' to match the stated asymptotic 0.707√k n.","section":"Theorem 15"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the main theorem is likely correct and the flaws I found are local (a missing inequality sign, an incorrect constant in Theorem 19, and an unexplained numerical evaluation in Lemma 12). The paper would benefit from a careful pass by the authors; I would not recommend rejection, but the proofs as written are not reliable. The bibliographic entry [9] appears to duplicate [8], and the internal cross-references in Section 5.2 need attention."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is that this paper has the real thing: a new upper bound on the edge density of outer k-planar graphs, improving the best constant from about 2.465√k n to (√2+ε)√k n + n. The main idea in Theorem 10 is a direct counting argument around a shortest long diagonal, generalizing an olympiad solution, and it is genuinely new as far as I know. The paper also gives bipartite bounds and a circulant graph max-cut lemma; the latter might be independently useful, even if the bipartite results are subsumed for large k by the general bound, as the author admits.\n\nThe central proof is plausible and, after checking the stress-test note, I agree the apparent omission of length-1 diagonals is an indexing artifact, not a real gap. The counting is confusingly written, but the shift in the definition of length accounts for it. So the main theorem does not have a load-bearing flaw.\n\nThe soft spots are real but patchable. Theorem 19 is stated for k≥5, but the displayed inequality only gives a contradiction for k≥7; a corrected constant would fix the statement, and the reader is right to flag it. Theorem 20 has a small algebraic typo in the numerator (2k+5 should be 2k+6, matching the bound in the following sentence). The abstract says 'edges' for a bound that actually counts diagonals and misses the +n term; for fixed k that changes the constant from about 1.414√k to 1.414√k+1, so it should be stated precisely. None of these affect the main asymptotic claim, but they do mean the paper is not ready as-is.\n\nCitation pattern looks fine: he builds on [2], [23], [11], and the crossing lemma constants are cited to their sources. Self-citation [10] for the bipartite crossing lemma constant is appropriate there and not load-bearing for Theorem 10.\n\nWho is this for? Anyone working on edge densities of planar or k-planar graph classes. It deserves a serious referee: the main result is important enough and the technique is reusable, even though the write-up needs a careful revision round. I would recommend conditional accept after major revision; the referee should check the k thresholds in the variants and the exact statements of Corollary 11 and Theorem 20.","headline":"New best constant for outer k-planar edge density, from about 2.465√k down to (√2+ε)√k; the central proof holds, but the write-up needs corrections before publication.","tokens_in":12498,"tokens_out":3570,"would_cite":true,"duration_ms":41779,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C35","05C62","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"An outer k-planar graph has at most $(\\sqrt{2}+\\varepsilon)\\sqrt{k}\\,n + n$ edges, with $\\varepsilon\\to 0$, improving the previous best constant $2.465$ to an asymptotic constant of $\\sqrt{2}$.","keywords":["edge density","convex k-plane graphs","outerplanar","circulant graphs","crossing number","maximum cut","bipartite graphs","Turán-type problem"],"falsifier":"Take a family of outer $k$-planar graphs, split each along a shortest diagonal of length at least $\\sqrt{2}\\,\\sqrt{k}$, and count the length-one diagonals in the smaller region. If any family has more than $(l_0-1)(2l-l_0+2)/2$ such diagonals, the main inequality fails; the concatenated-$K_x$ lower-bound construction is a concrete test case.","tokens_in":11399,"feed_emoji":"📐","tokens_out":6013,"duration_ms":54909,"temperature":0.7,"pith_summary":"This paper studies how many straight-line segments can connect $n$ points in convex position if each segment crosses at most $k$ others, equivalently the maximum edge count of an outer $k$-planar graph. Its central claim is an upper bound of $(\\sqrt{2}+\\varepsilon)\\sqrt{k}\\,n$ diagonals, with $\\varepsilon$ tending to $0$ for large $k$, which translates to at most $(\\sqrt{2}+\\varepsilon)\\sqrt{k}\\,n + n$ edges. If correct, this improves the previous best constant of about $2.465$ to about $1.414$, bringing the upper bound closer to the known lower-bound constant of $1$. The paper also derives bounds for bipartite outer $k$-planar graphs, using a new maximum-cut estimate for circulant graphs that may be useful beyond this setting.","feed_headline":"Outer k-planar edge bound falls to 1.414 sqrt(k) n","feed_subtitle":"New counting argument beats the old 2.465 constant by splitting along a shortest long diagonal.","key_machinery":"The carrying object is the shortest diagonal of length at least $l_0 = \\sqrt{2}\\,\\sqrt{k}$, denoted $D$. The argument relies on the counting inequality that the smaller region $G_1$ contains at most $\\sum_{p=2}^{l_0}(l+2-p)$ diagonals of length $p$, and that the complementary region $G_2$, by minimality of the counterexample, contains at most $x(n-l+2)$ diagonals. Subtracting these from the total diagonal count yields a lower bound on the number of diagonals crossing $D$; the choice of $l_0$ and $x=(\\sqrt{2}+\\varepsilon)\\sqrt{k}$ makes this lower bound exceed $k$ for large $k$, yielding the contradiction.","core_discovery":"The main theorem, Theorem 10, states that an outer $k$-planar graph has at most $(\\sqrt{2}+\\varepsilon)\\sqrt{k}\\,n$ diagonals, where $\\lim_{k\\to\\infty}\\varepsilon = 0$. The proof takes a vertex-minimal counterexample, chooses a shortest diagonal whose length is at least $l_0 = \\sqrt{2}\\,\\sqrt{k}$, and splits the graph along it into two regions. It then counts diagonals in the smaller region by length, bounding the number of length-$p$ diagonals by $l+2-p$, and uses minimality of the counterexample to bound the larger region. Combining these bounds forces the chosen diagonal to be crossed by more than $k$ diagonals, contradicting $k$-planarity for sufficiently large $k$.","pith_inferences":["Editorial extension: if the counting of length-one diagonals in the smaller region is handled carefully, the same shortest-long-diagonal method could yield explicit finite-$k$ bounds rather than only an asymptotic statement.","Editorial extension: the circulant max-cut estimate is proved without boundary conditions; incorporating boundary terms directly into Problem 1 could push the bipartite direct approach below the general bound.","Editorial extension: the asymmetry between the lower bound constant $1$ and the upper bound constant $\\sqrt{2}$ suggests that the true maximum might lie at $\\sqrt{k}\\,n$, but the current method cannot reach that constant without a more delicate count of short diagonals.","Editorial extension: the same diagonal-counting strategy might transfer to non-convex $k$-planar graphs, where no analogue of a shortest long diagonal is currently used."],"forward_implications":["Every outer $k$-planar graph on $n$ vertices has at most $(\\sqrt{2}+\\varepsilon)\\sqrt{k}\\,n + n$ edges for sufficiently large $k$, improving the previous best of about $2.465\\sqrt{k}\\,n$ edges.","The known lower bound construction of $\\sqrt{k}\\,n + \\Theta(1)$ edges remains the best known, so the gap between lower and upper bound constants shrinks from roughly $2.465$ to $\\sqrt{2}$.","The minimum-degree bound $2\\sqrt{k+1}+2$ implies that every convex geometric $k$-plane graph can be colored with $\\lfloor 2\\sqrt{k+1}\\rfloor + 1$ colors.","For bipartite outer $k$-planar graphs, the local approach gives at most $2\\sqrt{8/11}\\,\\sqrt{k}\\,n \\approx 1.7\\sqrt{k}\\,n$ edges for sufficiently large $k$.","The bound $\\mathrm{mc}(C_n^{1,2,\\dots,r}) \\le (5r/8 + 76)n$ on the maximum cut of circulant graphs is a standalone result that could serve other extremal graph problems."],"supporting_citations":[{"why":"A community-contributed solution to an olympiad problem supplies the core idea that a shortest long diagonal must be crossed many times, which the proof generalizes.","marker":"[16]"},{"why":"Provides the lower-bound construction of $\\sqrt{k}\\,n + \\Theta(1)$ edges and the tight small-$k$ bounds that the new upper bound must improve.","marker":"[23]"},{"why":"Established the previous best upper bound of about $2.465\\sqrt{k}\\,n$ via the Crossing Lemma and supplies the small-$k$ bounds used in the common approach.","marker":"[2]"},{"why":"Supplies the eigenvalue bound $\\mathrm{mc}(G) \\le \\tfrac{1}{4}\\lambda_{\\max}(L)\\,n$, which underpins the circulant max-cut lemma.","marker":"[19]"},{"why":"Gives the lower bound on the Dirichlet kernel used to control the largest Laplacian eigenvalue of the circulant graph.","marker":"[18]"},{"why":"Provides the eigenvalue formula for circulant matrices used to compute the Laplacian eigenvalues of $C_n^{1,2,\\dots,r}$.","marker":"[15]"},{"why":"Szekely's crossing-number lemma is used in the lazy variants for both general and bipartite outer $k$-planar graphs.","marker":"[22]"},{"why":"The bipartite crossing lemma with its current best constant is used to derive the first bipartite variant bound.","marker":"[10]"}],"fun_headline_variants":["Outer k-planar edge bound improved to sqrt(2) sqrt(k) n","New bound for outer k-planar edges: sqrt(2) sqrt(k) n","Outer k-planar edge count tightened to 1.414 sqrt(k) n","Diagonal-splitting argument sharpens outer k-planar edge bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the diagonals in the smaller region can be counted by length with at most $l+2-p$ diagonals of length $p$, and implicitly that diagonals of length one either do not occur or are negligible; if a dense construction puts many length-one diagonals in that region, the forced crossing count could drop below $k$.","fun_headline_variants_meta":{"raw":{"variants":["Outer k-planar edge bound improved to sqrt(2) sqrt(k) n","New bound for outer k-planar edges: sqrt(2) sqrt(k) n","Outer k-planar edge count tightened to 1.414 sqrt(k) n","Diagonal-splitting argument sharpens outer k-planar edge bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000962,"raw_usage":{"total_tokens":4050,"prompt_tokens":852,"completion_tokens":3198,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":3111}},"tokens_in":468,"tokens_out":3198,"duration_ms":21366,"temperature":1.0,"reasoning_tokens":3111,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:22:44.026789+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a family of outer $k$-planar graphs, split each along a shortest diagonal of length at least $\\sqrt{2}\\,\\sqrt{k}$, and count the length-one diagonals in the smaller region. If any family has more than $(l_0-1)(2l-l_0+2)/2$ such diagonals, the main inequality fails; the concatenated-$K_x$ lower-bound construction is a concrete test case.","supporting_citations":[{"cited_title":"prove that one of them intersects at least 10000 others","cited_arxiv_id":null,"evidence_quote":"A community-contributed solution to an olympiad problem supplies the core idea that a shortest long diagonal must be crossed many times, which the proof generalizes."},{"cited_title":"Book crossing numbers of the complete graph and small local convex crossing numbers","cited_arxiv_id":"1607.00131","evidence_quote":"Provides the lower-bound construction of $\\sqrt{k}\\,n + \\Theta(1)$ edges and the tight small-$k$ bounds that the new upper bound must improve."},{"cited_title":"In: SoCG","cited_arxiv_id":null,"evidence_quote":"Established the previous best upper bound of about $2.465\\sqrt{k}\\,n$ via the Crossing Lemma and supplies the small-$k$ bounds used in the common approach."},{"cited_title":"Czechoslovak Mathematical Journal 40(2), 343--352 (1990), http://eudml.org/doc/13856","cited_arxiv_id":null,"evidence_quote":"Supplies the eigenvalue bound $\\mathrm{mc}(G) \\le \\tfrac{1}{4}\\lambda_{\\max}(L)\\,n$, which underpins the circulant max-cut lemma."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the lower bound on the Dirichlet kernel used to control the largest Laplacian eigenvalue of the circulant graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Szekely's crossing-number lemma is used in the lazy variants for both general and bipartite outer $k$-planar graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The bipartite crossing lemma with its current best constant is used to derive the first bipartite variant bound."}],"review_version":1}