we-solve (beta)

Math-1142 · mathematics · Graph theory

The Crossing Number of the Complete Graph

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $K_n$ be the finite simple complete graph on $n\ge1$ vertices. A topological drawing in the plane represents vertices by distinct points and edges by simple arcs between their endpoints. No edge passes through another vertex. Edge interiors meet, if at all, in finitely many transverse crossings, with no three edges crossing at one point. Common endpoints are not crossings. The crossing number $\operatorname{cr}(G)$ is the minimum total number of such crossings among all drawings of a graph $G$.

The conjecture asks whether, for every integer $n\ge1$, \[ \operatorname{cr}(K_n)= \frac14\left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}2\right\rfloor \left\lfloor\frac{n-2}2\right\rfloor \left\lfloor\frac{n-3}2\right\rfloor. \] The floor symbols mean rounding down. This expression is zero for $n\le4$, consistent with planar drawings, and gives one for $n=5$. The source records constructions attaining the displayed expression; the asserted equality requires that no drawing do better.

Edges may bend freely: no requirement of straight-line segments, convex vertex placement, or a fixed cyclic ordering of vertices is imposed. Thus the problem concerns topological crossing number, which differs from the rectilinear parameter. Crossings are counted as points, so if a drawing lets the same two edges cross more than once, every crossing contributes. A proof of equality must cover all finite orders, rather than only showing that the ratio to the displayed expression tends to one.

Short English statement

Is the crossing number of the complete graph exactly the displayed four-factor floor formula for every number of vertices?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1142-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1142

Complete graph crossing numbers: For every complete graph K_n the claimed crossing number is exactly the Hill four-floor-factor expression, proving both the exact-value records and the matching lower-bound formulation.

With the hypotheses and conventions above, the claimed result addresses the whole mathematical assertion on this page.

The Crossing Number of the Complete Graph

OpenAI's claim

Complete graph crossing numbers: The paper claims that the ordinary crossing number of $K_n$ equals one quarter of the product of the four consecutive half-integer floor factors. The statement holds at every positive integer order.

Mathematical statement of the claimed result

Mathematical claim 1.
For every integer $n\ge3$, the manuscript asserts \[\operatorname{cr}(K_n)=\frac14\left\lfloor\frac n2\right\rfloor\left\lfloor\frac{n-1}2\right\rfloor\left\lfloor\frac{n-2}2\right\rfloor\left\lfloor\frac{n-3}2\right\rfloor.\] Here $\operatorname{cr}$ minimizes the number of proper edge-crossing points over ordinary plane drawings, allowing curved edges.

Outline of the argument

Complete graph crossing numbers: The drawing is reduced to a controlled simple-arc form, then signed cycle intersections and endpoint orders are encoded algebraically. An even-node order detector supplies the rank obstruction giving the lower bound. A two-page drawing attains the proposed value, with the normalization argument ensuring that unrestricted continuous-arc drawings are covered.

Formal verification

Family 165 describes Lean coverage for the two exact ordinary crossing formulas and drawings attaining them.

Complete graph crossing numbers: The manuscript links BipartiteCrossing.lean (declaration OAI.Zarankiewicz.mainTarget_proof), CompleteCrossing.lean (declaration OAI.Paper170.complete_graph_crossing_number).

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →