[#P2800] Rectilinear crossing number of K_28

A flat mathematical diagram showing a straight-line complete graph with marked crossings. — A schematic view of a straight-line complete graph with marked crossings.

Problem. Determine the minimum number of crossing pairs of edges in a straight-line drawing of the complete graph \(K_{28}\) with its vertices in general position in the plane. Equivalently, decide whether \(\overline{\operatorname{cr}}(K_{28})\) is 7233 or 7234.

1Context

Only one crossing separates the current bounds. A single new order type settles the lower endpoint, while excluded allowable sequences and k-edge inequalities remain useful toward the upper endpoint.

2Problem setup

Definition 1 (General position). General position means that no three vertices are collinear.

Definition 2 (A crossing). A crossing is counted for a pair of edges with four distinct endpoints whose relative interiors intersect.

Definition 3 (The rectilinear crossing number minimizes this count over all placements of the labeled vertices). The rectilinear crossing number minimizes this count over all placements of the labeled vertices.

Remark 1. Only one crossing separates the current bounds. A single new order type settles the lower endpoint, while excluded allowable sequences and k-edge inequalities remain useful toward the upper endpoint.

3What counts as a solution

Give a realizable order type or exact-coordinate drawing with 7233 crossings, or prove that every realizable 28-point order type has at least 7234 crossings. Include a replayable crossing count or lower-bound certificate.

1Status

Current status (Current status and unresolved remainder). UNKNOWN: Current tables checked 2026-07-31 give the two-value interval 7233 through 7234. Give a realizable order type or exact-coordinate drawing with 7233 crossings, or prove that every realizable 28-point order type has at least 7234 crossings. Include a replayable crossing count or lower-bound certificate.^[1]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 UNKNOWN: Current tables checked 2026-07-31 give the two-value interval 7233 through 7234. Give a realizable order type or exact-coordinate drawing with 7233 crossings, or prove that every realizable 28-point order type has at least 7234 crossings. Include a replayable crossing count or lower-bound certificate.^[1] Relevance to this problem Defines the dated frontier and the exact remainder that research on this problem must resolve. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details UNKNOWN: Current tables checked 2026-07-31 give the two-value interval 7233 through 7234. A complete resolution must satisfy this condition: Give a realizable order type or exact-coordinate drawing with 7233 crossings, or prove that every realizable 28-point order type has at least 7234 crossings. Include a replayable crossing count or lower-bound certificate. Open full record →
	Trace	Reported
attempt · Route 1 Give a realizable order type or exact-coordinate drawing with 7233 crossings, or prove that every realizable 28-point order type has at least 7234 crossings. Include a replayable crossing count or lower-bound certificate.^[1] Relevance to this problem For Rectilinear crossing number of K_28, record rectilinear-crossing-k28-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Give a realizable order type or exact-coordinate drawing with 7233 crossings, or prove that every realizable 28-point order type has at least 7234 crossings. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Give a realizable order type or exact-coordinate drawing with 7233 crossings, or prove that every realizable 28-point order type has at least 7234 crossings. Include a replayable crossing count or lower-bound certificate. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN: Current tables checked 2026-07-31 give the two-value interval 7233 through 7234.

2026-07-27: The exact values are published through n=27. Current MathWorld and OEIS entries identify n=28 as the first unsettled case and give 7233 or 7234.
2026-07-27: No equivalent K_28 target was found in earlier TheoremDB candidate corpora or live prospecting data.
Every crossing corresponds to a convex 4-subset of the point set. Order-type certificates, allowable sequences, and k-edge counts can support either endpoint.

Recorded example 1. Twenty-eight points in convex position give \(\binom{28}{4}=20475\) crossings, since every four points contribute one crossing pair.

Computational notes

Exact integer arithmetic gives \(\binom{28}{4}=20475\). The interval 7233-7234 is taken from the dated external status sources and was not independently recomputed.

How the 2 records connectTyped relations and evidence flow

ProblemRectilinear crossing number of K_28

Claim 1Current status and unresolved remainderin this packetSupported
Route 1Resolve the stated acceptance conditionaddressesReported

2See also

Dürer’s edge-unfolding problemcomputational geometry
Minimum spanning-tree dilation on the regular nonagoncomputational geometry
Flip-graph diameter for triangulations of C(10,4)computational geometry

How to cite

TheoremDB contributors, “Rectilinear crossing number of K_28,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/rectilinear-crossing-k28

This page as plain text: rectilinear-crossing-k28.md

This problem includes 2 records joined by 1 typed links, sourced from doi.org^[1], current as of July 31, 2026.

1References

Packet source. Bernardo M. Ábrego, Silvia Fernández–Merchant, Jesús Leaños, and Gelasio Salazar, “The maximum number of halving lines and the rectilinear crossing number of for”. Electronic Notes in Discrete Mathematics 30 (2008), 261-266. DOI 10.1016/j.endm.2008.01.045. Original database formulation of the first unresolved complete-graph rectilinear crossing number. ↗journal article · primary source · checked 2026-08-01Source use: original summary.UNKNOWN: Current tables checked 2026-07-27 give the two-value interval 7233 through 7234.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to assess the problem's recorded status.For Rectilinear crossing number of K_28: UNKNOWN: Current tables checked 2026-07-27 give the two-value interval 7233 through 7234.Source named by the research packet.
Eric W. Weisstein, with a contribution by Uli Wagner, “Rectilinear Crossing Number,” MathWorld, Wolfram Research, checked 2026-08-01. Status evidence identified in the source record and checked at the linked publication. ↗website · primary source · checked 2026-07-31Source use: original summary.UNKNOWN: Current tables checked 2026-07-27 give the two-value interval 7233 through 7234.Also cited at complete-graph table and paragraph identifying K_28 as the smallest unsettled case.Source used to assess the problem's recorded status.For Rectilinear crossing number of K_28, this source summarizes the maintained interval 7233 through 7234 for the rectilinear crossing number of K_28.
Eric W. Weisstein, “A014540: Rectilinear crossing number of the complete graph on n nodes,” On-Line Encyclopedia of Integer Sequences; the n=28 interval comment was contributed by Bernardo M. Ábrego on May 5, 2008; checked 2026-08-01. Status evidence identified in the source record and checked at the linked publication. ↗website · primary source · checked 2026-07-31Source use: original summary.Reused material: sequence definition, values through n=27, and the comment giving the two-value interval for n=28.Reuse basis: fair use reviewed · rights holder: The OEIS Foundation Inc. and the credited contributors · checked 2026-08-01 by Philip Weiss, TheoremDB staff.Required attribution: Eric W. Weisstein, “A014540: Rectilinear crossing number of the complete graph on n nodes,” On-Line Encyclopedia of Integer Sequences; the n=28 interval comment was contributed by Bernardo M. Ábrego on May 5, 2008; checked 2026-08-01.UNKNOWN: Current tables checked 2026-07-27 give the two-value interval 7233 through 7234.Also cited at sequence definition, values through n=27, and the comment giving the two-value interval for n=28.Source used to assess the problem's recorded status.For Rectilinear crossing number of K_28, this source records the complete-graph rectilinear crossing-number table and the exact remaining K_28 interval.

Original formulation of a one-unit gap at the current exact frontier.

[#P2800] Rectilinear crossing number of K_28

1Context

2Problem setup

3What counts as a solution

1Status

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance