# P2800: Rectilinear crossing number of K_28

- ID: `P2800`
- Reference: `rectilinear-crossing-k28`
- Page: https://theoremdb.org/statements/P2800
- Record maturity: Reviewed problem with recorded work

## 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.

### Problem setup

- **Definition.** General position means that no three vertices are collinear.
- **Remark.** A crossing is counted for a pair of edges with four distinct endpoints whose relative interiors intersect.
- **Remark.** The rectilinear crossing number minimizes this count over all placements of the labeled vertices.

### What 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.

## Status

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](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

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.

- Original intake status: UNKNOWN: Current tables checked 2026-07-27 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: Twenty-eight points in convex position give \(\binom{28}{4}=20475\) crossings, since every four points contribute one crossing pair.

### Open directions

- **Route 1** (reported): 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](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `rectilinear-crossing-k28`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.1016/j.endm.2008.01.045
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>Eric W. Weisstein, with a contribution by Uli Wagner, “Rectilinear Crossing Number,” MathWorld, Wolfram Research, checked 2026-08-01. complete-graph table and paragraph identifying K_28 as the smallest unsettled case https://mathworld.wolfram.com/RectilinearCrossingNumber.html
   - website; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.
3. <a id="reference-3"></a>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. sequence definition, values through n=27, and the comment giving the two-value interval for n=28 https://oeis.org/A014540
   - reference_database; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.
   - 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.