[#P2800] Rectilinear crossing number of K_28

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.

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.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

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.

Remark 1. The rectilinear crossing number minimizes this count over all placements of the labeled vertices.

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

Saved packet · July 31, 2026

What counts as a solution

Saved packet 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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 For rectilinear crossing k28, pins the dated research frontier: 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. 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 →
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.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
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 material

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemRectilinear crossing number of K_28

All 1 recorded relations between these records and the problem

Resolve the stated acceptance condition addresses Current status and unresolved remainder

2See also

Minimum spanning-tree dilation on the regular nonagoncomputational geometry
Exact ten-point Heilbronn number in the unit squarecomputational geometry
Minimum number of convex pentagons determined by seventeen pointscomputational geometry

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Rectilinear crossing number of K_28.” TheoremDB. P2800. Problem statement; statement text SHA-256 dffb1aad716a6e034170ad3349177618cbf422742f0b1a32c2770bb9f855126d. https://theoremdb.org/statement/?ref=P2800

BibTeX

@misc{theoremdb-problem-dffb1aad716a6e034170ad3349177618cbf422742f0b1a32c2770bb9f855126d,
  title = {{Rectilinear crossing number of K\_28}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 dffb1aad716a6e034170ad3349177618cbf422742f0b1a32c2770bb9f855126d},
  url = {https://theoremdb.org/statement/?ref=P2800}
}

Plain text: Built Markdown snapshot

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

1Lean verification

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

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance