gpt 6 astra ultra attempt on Math-609

The Harary--Hill--Guy Crossing Formula

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For a complete graph on $n$ vertices, the proposed topological crossing number is \[H(n)=\frac14\lfloor n/2\rfloor\lfloor(n-1)/2\rfloor\lfloor(n-2)/2\rfloor\lfloor(n-3)/2\rfloor.\] The equality concerns the minimum over all plane drawings, not just straight-line or circular drawings. It is asserted for every integer $n\geq1$. [S1] [S2]

Statement recorded in the supplied source.

Is the crossing number of the complete graph $K_n$ equal to the value given by Guy's formula? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Close the asymptotic 1.5% gap and determine the first unresolved exact case n=13 and all subsequent cases. [S1]

Short English statement

Does the classical four-factor formula give the exact minimum crossing number of every complete graph?

Research attempt

Status: UNRESOLVED. We prove a subdrawing lower bound of quartic order, establish the small cases through five vertices, and compare the resulting coefficient with the proposed formula. The key gap is compatibility among many overlapping complete subdrawings.

Literature and scope check.

The inherited publisher links [S2,S3] were inaccessible in the tool used on 1 October 2026. The accessible primary paper [E1] distinguishes ordinary crossing number from the two-page version and records drawings attaining the proposed value. Its two-page lower bounds do not prove the unrestricted lower bound. We do not assert a new current-best bound or independently reproduce a Hill drawing. Instead we derive a weaker unrestricted estimate from first principles.

Small complete graphs.

For $n\le4$, $K_n$ is planar: draw a triangle and, for $K_4$, put the fourth vertex inside and join it to the three corners. Thus its crossing number is zero, agreeing with $H(n)$.

The graph $K_5$ is nonplanar because its ten edges exceed the planar bound $3\cdot5-6=9$. It has a one-crossing drawing. Start with a triangle, one vertex inside joined to all three corners, and one vertex outside joined to all three corners in the outer face. This draws $K_5$ minus the edge between the two extra vertices without crossings. Add that missing edge across a suitable triangle side through the two adjacent faces; it crosses that side once and avoids the other edges. Hence $\operatorname{cr}(K_5)=1=H(5)$.

Counting five-vertex subdrawings.

Take a drawing of $K_n$ with $C$ crossings, simplified so that adjacent edges do not cross and each interior crossing involves exactly two edges. Every five-set of vertices induces a drawing of $K_5$, and hence contributes at least one crossing. A particular crossing involves four distinct endpoints. It appears in exactly $n-4$ induced five-vertex subdrawings, according to the fifth vertex selected. Therefore, for $n\ge5$, \[ C(n-4)\ge\binom n5,\qquad \operatorname{cr}(K_n)\ge\frac{n(n-1)(n-2)(n-3)}{120} =\frac15\binom n4. \] The right side is rounded up if nonintegral. The four-endpoint property is necessary for the multiplicity; it follows from local simplification of a crossing-minimal drawing, not from an assumption that all edges are straight.

A universal comparison from larger complete graphs.

More generally fix $5\le t\le n$ and a lower bound $L_t\le\operatorname{cr}(K_t)$. Summing over all $t$-sets, each crossing is counted $\binom{n-4}{t-4}$ times, giving \[ \operatorname{cr}(K_n)\ge L_t\frac{\binom nt}{\binom{n-4}{t-4}} =L_t\frac{\binom n4}{\binom t4}. \] In particular the normalized quantity $\operatorname{cr}(K_n)/\binom n4$ is nondecreasing as $n$ grows, in the sense supplied by this inequality between any two orders. It is at most one: putting all vertices in convex position with straight edges yields exactly one crossing per four-set, because each four-set has exactly one pair of diagonals.

This provides a bounded monotone sequence and hence a limiting normalized crossing density. Existence of that limit is not its evaluation, and does not imply an exact finite formula. The proposed expression satisfies $H(n)/\binom n4\to3/8$, whereas the five-vertex argument only gives $1/5$. Thus even at the asymptotic level it leaves a nonzero gap.

Why naive local equality does not propagate.

The case $K_5$ shows that each five-set needs a crossing, but a single crossing serves many five-sets. The lower bound optimizes this reuse only at the level of total incidences. There may be no drawing realizing a proposed uniform distribution of these incidences, because subdrawings share edges and their cyclic orders around vertices must agree. Treating each five-set as independently drawable omits those compatibility constraints.

Conversely the convex-position construction gives an explicit upper bound but need not be optimal among curved-edge drawings. Proving optimality within straight-line or two-page drawings establishes only a restricted problem. Since the catalogue allows arbitrary arcs, restricting the competitor class would invalidate a claimed universal lower bound.

Verification and remaining gap.

At $n=5$ the bound is exactly one, so the endpoint and multiplicity are consistent. All formulas count unordered four-sets and crossings of unordered pairs of independent edges. No exhaustive drawing enumeration, new crossing certificate, or formal proof assistant check was performed.

The unresolved step is raising the unrestricted lower bound to $H(n)$ at every order, or producing a drawing below it. A next approach would encode compatible rotation systems and crossing incidences for overlapping complete subgraphs; any finite enumeration would need a completeness theorem for its drawing representation. The present work proves baseline bounds and monotonicity of normalized density, but does not settle Guy's formula.

Sources

• E1 E. de Klerk and D. V. Pasechnik, Improved lower bounds for the 2-page crossing numbers of $K_{m,n}$ and $K_n$ via semidefinite programming. Primary abstract checked 1 October 2026. https://arxiv.org/abs/1110.4824.

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1408 (GRAPH-021), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 S. Pan and R. B. Richter, The crossing number of K11 is 100, Journal of Graph Theory 56 $2007$, 128–134. https://doi.org/10.1002/jgt.20249. Bibliographic information from the supplied record.

• S3 J. Balogh, B. Lidický, and G. Salazar, Closing in on Hill's Conjecture, SIAM Journal on Discrete Mathematics 33 $2019$, 1261–1276. https://doi.org/10.1137/17M1158859. Bibliographic information from the supplied record.