{"id":"69035b6d-bae2-467e-b21f-bf8b8c7eac73","arxiv_id":"1908.07851","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The simple quasi crossing number of K11 is exactly 4.","lead":"This paper finds the exact value of a graph-drawing invariant for the complete graph on 11 vertices. It shows that any drawing of K11 must contain at least four triples of pairwise crossing edges, and gives a drawing with exactly four such triples.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower bound cr3(K11) ≥ 4 is sound, but the equality cr3(K11) = 4 rests entirely on the missing Figure d; no coordinates or routing rules are given, so the upper bound is unverified from the text.","rationale":"I read the argument in good faith. The lower bound is a standard and valid application of the quasi-planar edge bound; no issue there. The probabilistic bound is not needed for the headline result, although as written it is not fully rigorous. The single place where the theorem could be wrong is the upper-bound construction. The reader's verdict identified exactly this ('correctness of Figure d'), and I agree. Because the construction is entirely visual and the figure is absent from the reviewed text, the claim cr3(K11) = 4 cannot be independently confirmed. The appropriate disposition is the same as the reader's: conditional acceptance on verification of the drawing. If the figure turns out to contain exactly four triples and is simple, the paper's central claim is correct; if not, the upper bound fails. One concrete check—independent counting of triples in the supplied drawing—settles the matter, so the concern is not speculative.","tokens_in":1857,"tokens_out":8082,"duration_ms":81713,"concrete_test":"Obtain Figure d from the authors or the published version and encode it as an explicit topological drawing of K11 (vertex coordinates plus edge curves, or an equivalent planar embedding). Write an independent checker that, for every one of the C(55,3) triples of edges, tests pairwise interior intersections and counts those in which the three edges pairwise cross exactly once, and that also verifies the drawing is simple (no two edges meet more than once and no edge passes through a non-incident vertex). Accept cr3(K11) = 4 only if the count is exactly 4. If the count is >4, the equality fails; if the figure cannot be supplied in a checkable form, the upper bound remains unverified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorem has two directions. The lower bound is solid: applying the Ackerman–Tardos bound (at most 6.5n − 20 = 51.5 edges for n = 11) to the quasi-planar subgraph obtained by deleting a hitting set for the crossing triples gives 55 − t ≤ 51, hence t ≥ 4. The upper bound, however, is asserted only by 'In the following, we present a drawing (Figure d) that shows that cr3(K11) = 4.' The figure is not present in the provided manuscript, and the text gives no vertex coordinates, no edge-routing prescription, and no combinatorial data from which the drawing can be reconstructed. Thus the existence of a simple drawing of K11 with exactly four pairwise-crossing triples is not checkable from the paper as written. This is not an internal contradiction, but the central equality is only as reliable as that unavailable figure. The later probabilistic improvement (Eq. 2) has a separate gap—inequality (1) is applied to random subgraphs with fewer than four vertices, where the '+20' term can make the right-hand side positive while cr3(H)=0—but Eq. (2) is not used for the K11 result, so it does not undermine the main claim. The main claim is unsupported only insofar as Figure d is unverified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines the simple quasi crossing number cr3(G) as the minimum number of triples of pairwise crossing edges over all simple drawings of G. It combines the Ackerman-Tardos bound of 6.5n−20 edges for simple quasi-planar graphs with a hitting-set argument to derive the lower bound cr3(G) ≥ e−6.5n+20. For K11 this gives cr3(K11) ≥ 3.5, hence at least 4. The paper then asserts, with reference to a figure, that there is a simple drawing of K11 with exactly four such triples, concluding cr3(K11)=4. A probabilistic improvement of the lower bound is also derived and applied to graphs with e≥8.125n, and two open problems are stated.","tokens_in":2170,"tokens_out":5536,"duration_ms":54605,"significance":"If the upper-bound drawing is supplied, the equality cr3(K11)=4 would be a clean, nontrivial exact value that goes beyond the known quasi-planarity of K_n for n≤10, and the lower-bound proof via the Ackerman-Tardos bound is mathematically sound. The lower-bound technique (inequality (1)) is simple and correct. However, as the manuscript stands, no verifiable drawing is provided, so the central equality is not established. The probabilistic improvement (2) is derived incorrectly; although it does not affect the K11 lower bound, it is a substantive error in the paper's general claim.","major_comments":[{"comment":"The assertion cr3(K11) ≤ 4 is supported only by 'Figure d', which is not present in the manuscript. No vertex coordinates, edge-routing prescription, rotation system, or other data are given from which the drawing can be reconstructed or verified. Since this upper bound is the second half of the equality cr3(K11)=4, the central claim is uncheckable as written. The manuscript must include the drawing (or an explicit combinatorial description) and a verification that it is a simple drawing of K11 containing exactly four triples of pairwise crossing edges.","section":"Upper-bound paragraph ('In the following, we present a drawing...')"},{"comment":"Inequality (1) is valid only for graphs with at least four vertices, but the derivation of (2) applies it to the random subgraph H without any restriction. For a subgraph with n_H=3 and e_H=1, inequality (1) would give cr3(H) ≥ 1.5, while cr3(H)=0, so the inequality is false for such H. Hence the expectation E[cr3(H)] ≥ E[e_H] − 6.5E[n_H] + 20 is not justified. This does not affect the K11 lower bound, but it invalidates the claimed probabilistic improvement (2) as stated and must be repaired, e.g., by conditioning on n_H≥4 or proving a version valid for all n_H.","section":"Equation (2), paragraph beginning 'We improve this bound by the probabilistic method'"}],"minor_comments":[{"comment":"The phrase 'Consider a random subgraph of H obtained by including each vertex of G independently' should read 'random subgraph of G'; as written, H is introduced both as the random subgraph and as the graph being sampled, which is confusing.","section":"Probabilistic method paragraph"},{"comment":"The text and captions repeatedly refer to Figures a-d, but none of these figures appears in the manuscript; even apart from the missing verification of Figure d, the paper should either include all figures or describe the incremental construction in words.","section":"Figure references"},{"comment":"The references [3,5] are cited for the claim that K_n is simple quasi-planar for n≤10; reference [3] is a point-set order-type database, so it would be helpful to cite a direct source for the graph-drawing claim or to describe the construction.","section":"First paragraph of the introduction"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The lower bound in this note is correct, and the exact value for K11 is a nice data point, but the paper as submitted does not give you the drawing that proves the upper bound. The main claim cr3(K11)=4 therefore rests on a figure I cannot see.\n\nWhat is new: as far as I can tell, this is the first exact simple quasi crossing number for a complete graph beyond the quasi-planar range (n ≤ 10). The lower bound argument is clean: in any simple drawing of K11, every triple of pairwise crossing edges can be destroyed by removing one edge, so deleting t edges from a drawing with t triples yields a simple quasi-planar graph on 11 vertices. Ackerman-Tardos caps such graphs at 6.5·11 − 20 = 51.5 edges, so 55 − t ≤ 51, giving t ≥ 4. That part is airtight.\n\nThe soft spot is the upper bound. The sentence 'In the following, we present a drawing (Figure d) that shows that cr3(K11) = 4' is all we get. The figure is not in the text I received, and there are no coordinates, routing rules, or edge-order data to reconstruct the drawing. So the existence of a simple drawing of K11 with exactly four crossing triples is not checkable from the manuscript. This is not a contradiction inside the math; it's just that the central equality is as good as that missing figure. If the figure is provided in the actual arXiv version, this concern goes away.\n\nThere is also a separate gap in the probabilistic bound (2). The derivation applies inequality (1) to the random subgraph H, but (1) only holds for graphs with at least four vertices, and when H has fewer vertices the '+20' term can make the right-hand side positive while cr3(H)=0. The paper does not use (2) for the K11 result, so this does not hurt the main theorem, but the section should be fixed or clearly scoped to n_H ≥ 4.\n\nOverall this is a short, honest note. The lower bound is solid, the upper bound is plausible but unverified in the text. If the drawing is real and supplied in a checkable form, the result is a legitimate small contribution to graph drawing. I'd send it to review only once the figure is available; the probabilistic section needs a correction or a caveat.","headline":"The lower bound cr3(K11) ≥ 4 is sound, but the claimed equality rests entirely on a missing figure; the probabilistic add-on also has a fixable gap.","tokens_in":2576,"tokens_out":2449,"would_cite":false,"duration_ms":23237,"reading_group":"maybe","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 simple quasi crossing number of $K_{11}$ is exactly 4, making $K_{11}$ the smallest complete graph that is not simple quasi-planar.","keywords":["simple quasi crossing number","quasi-planar graphs","complete graph K11","pairwise crossing edges","probabilistic method","graph drawing","crossing number"],"falsifier":"Make the drawing labeled Figure d explicit by listing the positions of the 11 vertices, compute all pairwise edge crossings, and count the triples of edges whose three pairwise pairs all cross; any count other than exactly four would refute the asserted value.","tokens_in":1690,"feed_emoji":"📐","tokens_out":10941,"duration_ms":103256,"temperature":0.7,"pith_summary":"The paper establishes that the simple quasi crossing number of $K_{11}$ is exactly $4$: every simple drawing of the complete graph on eleven vertices must contain at least four triples of pairwise crossing edges, and some simple drawing has exactly four such triples. The lower bound is derived from the known $6.5n-20$ edge bound for simple quasi-planar graphs, amplified by a random-subgraph argument; the upper bound is a single explicit drawing. Since every smaller complete graph is already known to be simple quasi-planar, this makes $K_{11}$ the first complete graph that is not.","feed_headline":"Every drawing of K11 has at least four crossing triples","feed_subtitle":"K11 is the first complete graph that cannot be drawn with fewer than four crossing triples.","key_machinery":"The carrier of the proof is the quantity $\\operatorname{cr}_3(G)$, the minimum number of triples of pairwise crossing edges over all simple drawings of $G$. For the lower bound, the paper combines the extremal fact that any simple quasi-planar graph on $n$ vertices has at most $6.5n-20$ edges with a probabilistic argument: sample vertices independently with probability $p = \\alpha n/e$, take expectations, and optimize $\\alpha$. This yields $\\operatorname{cr}_3(G) \\ge \\frac{\\alpha-6.5}{\\alpha^5}\\frac{e^5}{n^4} + \\frac{20}{\\alpha^6}\\frac{e^6}{n^6}$ for graphs with $e\\ge \\alpha n$, and the maximizing choice $\\alpha=8.125$ gives $\\operatorname{cr}_3(K_{11})\\ge 3.5$, hence at least $4$. The upper bound is a single drawing in which the marked triples are claimed to be the only ones.","core_discovery":"The central claim is that $\\operatorname{cr}_3(K_{11}) = 4$. A triple of pairwise crossing edges is a set of three edges in which every two meet at an interior point, and a simple drawing lets each pair of edges meet at most once. The paper proves that every simple drawing of $K_{11}$ contains at least four such triples, and it presents a drawing of $K_{11}$ in which the number of such triples is exactly four. Together these settle the value and place the threshold for simple quasi-planarity of complete graphs at $n=11$.","pith_inferences":["Extending the paper's inequality (1) to $n=12$ gives $\\operatorname{cr}_3(K_{12})\\ge 8$; the paper does not state this number.","If the Figure d drawing is made explicit, inspecting whether its four triples share a structural pattern could suggest the first non-trivial upper-bound constructions for $n\\ge 12$; this is a line of inquiry the paper leaves open.","A natural higher-order analogue would apply the same probabilistic amplification to drawings free of $k+1$ pairwise crossing edges, once the corresponding extremal edge bound is known; the paper does not pursue this."],"forward_implications":["For every $n\\le 10$, $\\operatorname{cr}_3(K_n)=0$, so $K_{11}$ is the smallest complete graph that is not simple quasi-planar.","Any simple drawing of $K_{11}$, no matter how crossings are arranged, contains at least four triples of pairwise crossing edges.","The lower-bound inequality applies to every graph with $e\\ge 8.125n$, giving an explicit polynomial lower bound on $\\operatorname{cr}_3(G)$ in terms of $e$ and $n$.","The value of $\\operatorname{cr}_3(K_{11})$ is now known exactly, so the remaining open case for complete graphs starts at $n=12$."],"supporting_citations":[{"why":"Supplies the $6.5n - 20$ edge bound for simple quasi-planar graphs that anchors the lower-bound argument.","marker":"[1]"},{"why":"Provides order-type data showing complete graphs on at most 10 vertices are simple quasi-planar, so their quasi crossing number is 0.","marker":"[3]"},{"why":"Exhibits a simple quasi-planar drawing of $K_{10}$, the largest case before the new bound.","marker":"[5]"},{"why":"The crossing-free subgraphs route whose probabilistic amplification is imitated to improve the lower bound.","marker":"[4]"},{"why":"The other source of the crossing-number-inequality method used to derive the stronger lower bound.","marker":"[6]"}],"fun_headline_variants":["K11: every drawing forces four crossing triples","Four crossing triples are unavoidable in K11","K11's quasi crossing number is exactly four","K11 is first graph needing four crossing triples","No drawing of K11 has fewer than four crossing triples"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that Figure d, which is mentioned but not described in the text, really is a simple drawing of $K_{11}$ with exactly four triples of pairwise crossing edges; if that figure contains any additional crossing triple, the proposed upper bound fails.","fun_headline_variants_meta":{"raw":{"variants":["K11: every drawing forces four crossing triples","Four crossing triples are unavoidable in K11","K11's quasi crossing number is exactly four","K11 is first graph needing four crossing triples","No drawing of K11 has fewer than four crossing triples"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000645,"raw_usage":{"total_tokens":2814,"prompt_tokens":647,"completion_tokens":2167,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":263,"completion_tokens_details":{"reasoning_tokens":2091}},"tokens_in":263,"tokens_out":2167,"duration_ms":16686,"temperature":1.0,"reasoning_tokens":2091,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:27:08.382420+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Make the drawing labeled Figure d explicit by listing the positions of the 11 vertices, compute all pairwise edge crossings, and count the triples of edges whose three pairwise pairs all cross; any count other than exactly four would refute the asserted value.","supporting_citations":[{"cited_title":"Ackerman and G","cited_arxiv_id":null,"evidence_quote":"Supplies the $6.5n - 20$ edge bound for simple quasi-planar graphs that anchors the lower-bound argument."},{"cited_title":"Aichholzer and H","cited_arxiv_id":null,"evidence_quote":"Provides order-type data showing complete graphs on at most 10 vertices are simple quasi-planar, so their quasi crossing number is 0."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Exhibits a simple quasi-planar drawing of $K_{10}$, the largest case before the new bound."},{"cited_title":"Ajtai, V","cited_arxiv_id":null,"evidence_quote":"The crossing-free subgraphs route whose probabilistic amplification is imitated to improve the lower bound."},{"cited_title":"Leighton","cited_arxiv_id":null,"evidence_quote":"The other source of the crossing-number-inequality method used to derive the stronger lower bound."}],"review_version":1}