The maximum number of once-crossed edges in a rectilinear drawing of Kₙ
Abstract
For a drawing D of a graph, eₖ(D) is the number of edges involved in exactly k crossings, and the sequence (e₀(D),e₁(D),…) is the crossing profile of D. Chen and Solé-Pi, who introduced the profile, determined overline(max) e₀(Kₙ)=2n-2 and asked, as their Problem 1, for the value of overline(max) e₁(Kₙ), the maximum of e₁ over rectilinear drawings of Kₙ; for n ≥ 8 they could only place it between ⌈ 3n/2⌉-7 and 2n+⌊ (n-1)/2⌋+7. We determine overline(max) e₁(Kₙ) exactly for 4 ≤ n ≤ 11, where its values are 2,2,6,7,10,12,14,14, and we prove 16 ≤ overline(max) e₁(K₁₂) ≤ 17. In particular the pattern overline(max) e₁(Kₙ)=2n-6, which holds at n=8,9,10, fails at n=11, so this route yields no candidate answer to the limit half of Problem 1. We also exhibit drawings giving overline(max) e₁(Kₙ) ≥ 17,19,19,21 for n=13,…,16, each above the published lower bound. The upper bounds come from an exhaustion over uniform rank-3 chirotopes rather than over order types — dropping realizability enlarges the search space and so preserves an upper bound — made finite by a deletion bound that lets an n-element search be driven by the (n-1)- or (n-2)-element objects with large e₁. The supporting statements are machine-checked in Lean 4.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
ed0fabb0b16a5ae04b8e8116ab3b479a1bec4c4992dc9c24e21d76012cc63932
Claim ledger
Stated results
CP1routine2026-08-22
The model: a rectilinear drawing of Kₙ, its crossing profile eₖ, and Sₖ, transcribed from the source
CP2candidate2026-08-22
Headline: exact values of max-bar e₁(Kₙ) for n = 4..10, the source's Problem 1 at small n
CP3candidate2026-08-22
Lower bounds for max-bar e₁(Kₙ) at n = 11..15, each above the source's own bound
CP4known data2026-08-22
Validation: two published e₀ columns and Aichholzer's order-type census reproduced from the same enumeration
CP5known data2026-08-22
max-bar e₀(Kₙ) = 2n-2 attained at n = 4..16 by a wheel construction recovered from the search's own optima
CP6measurement2026-08-22
The method: exhaustion over uniform rank-3 chirotopes instead of over order types, and Bridge (B), the family's only assumption
CP7routine2026-08-22
Negative controls: degenerate input rejected, both 'too weak' directions refuted, the exhaustion shown capable of excluding, and the witnesses shown fragile
CP9candidate2026-08-23
max̄ e₁(K₁6) ≥ 21, a row the family did not have
CP10routine2026-08-23
e₁ as the source defines it — edges through exactly one crossing POINT — and every witness certified under it
CP11routine2026-08-23
The control the 2026-08-22 review asked for: IsGeneric is load-bearing on the e₁ side
CP12routine2026-08-23
n = 11 stays at 14 under a move no coordinate search can make: the exhaustive one-point extension
CP13candidate2026-08-23
max̄ e₁(K₁1) = 14 — the source's Problem 1 answered at a new n, and 2n-6 breaks
CP14routine2026-08-23
The deletion bound, verified at every chirotope on ≤ 8 elements and shown sharp
CP15routine2026-08-23
Single-element extension as a complete enumeration route: the leaf-count identity, and the two validation gates
CP16routine2026-08-23
The controls: W11, a realizable eleven-element chirotope with e₁ = 14, and what breaks around it
CP17candidate2026-08-23
max̄ e₁(K₁2) ≤ 20 — the first bound at n = 12 below the source's own 36, by a two-level deletion chain
CP18routine2026-08-23
The two-level licence, the n = 12 price list, and that chaining beats the one-shot double count
CP19routine2026-08-23
The two-level pass: the leaf-count identity at four sizes, and four two-sided gates
CP20routine2026-08-23
W12, and the controls around the two-level pass
CPQ1routine2026-08-23
(journal id CP17, renumbered: CP17 was taken by the n = 12 landing) The control on bumpQuad: no quadruple of a normalized chirotope is ambiguous, so the else if crossing chain is exact
CP21candidate2026-08-23
max̄ e₁(K₁2) ≤ 17 — the n = 12 cell narrowed to a bracket of width one
CP22routine2026-08-23
The t0 = 8 licence, its sharpness, and the measured cost of chunking a two-level filtered search
CP23routine2026-08-23
The rung shape validated at every size where the answer is known, and the controls
CP24routine2026-08-23
Z12 — a second twelve-element chirotope with e₁ = 16, found by the exhaustion
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- max̄ e₁(Kₙ) — the largest number of edges crossed *exactly once* in a straight-line drawing of the complete graph.
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7