GPT 6 Astra Ultra attempt on Math-1144

Crossing numbers and coloring

Definitions and mathematical statement

Let $G$ be a finite simple undirected graph. Its chromatic number $\chi(G)$ is the least number of colours in a vertex colouring where adjacent vertices have different colours. A plane drawing represents vertices by distinct points and edges by simple arcs between their ends, with no edge through another vertex, finitely many transverse crossings of edge interiors, and no triple crossing. The crossing number $\operatorname{cr}(G)$ is the least total number of crossing points over all such drawings; endpoints are not counted. Edges need not be straight.

For an integer $t\ge1$, write $K_t$ for the complete graph on $t$ vertices. Albertson's conjecture is the universal implication \[ \chi(G)\ge t \quad\Longrightarrow\quad \operatorname{cr}(G)\ge\operatorname{cr}(K_t). \] The right-hand side is the actual crossing number of $K_t$, not a conjectured formula for that number. Thus defining this question does not require solving the separate complete-graph crossing problem.

Equivalently, among graphs with chromatic number exactly $t$, the complete graph should minimize crossing number. To pass to the "at least" formulation, delete vertices until a subgraph of chromatic number $t$ remains, and use monotonicity of crossing number under taking subgraphs. The conjecture does not assert that $G$ contains a complete subgraph, a complete subdivision, or a complete minor. It compares two numerical invariants and permits arbitrarily many vertices and arbitrary graph structure beyond the chromatic hypothesis.

Short English statement

Does every graph requiring at least t colours have crossing number at least that of the complete graph on t vertices?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 2 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope. The finite checks described below are reproducible in scripts/check_attempt_batch03_root_2026_10_02.py.

A route through critical graphs.

The target compares a chromatic obstruction with the crossing number of a clique, rather than with an arbitrary polynomial in the chromatic number. We derive a sufficient condition based on the order of a critical subgraph. It proves the desired inequality for graphs whose critical obstruction is sufficiently large, but leaves a concrete range of smaller obstructions untreated. This is an elementary reduction, not a claim to improve the literature surveyed in [S2].

An elementary crossing estimate.

Let $H$ be simple with $n$ vertices, $m$ edges and crossing number $c$. Deleting at most one edge for each crossing in an optimal drawing leaves a planar graph. The planar edge bound, including the cases with fewer than three vertices, therefore gives the convenient weak inequality $c\ge m-3n$. We may choose an optimal drawing without crossings between incident edges: exchanging the initial portions of two such edges removes their crossing without increasing the total. Keep each vertex independently with probability $p$, and use the induced drawing. Each edge survives with probability $p^2$, and each original crossing with probability $p^4$, since its four endpoints are distinct. Applying the weak inequality to each outcome and taking expectations gives \[ p^4c\ge p^2m-3pn. \] If $m\ge4n>0$, choose $p=4n/m\le1$ and rearrange to obtain \[ c\ge\frac{m^3}{64n^2}. \] The drawing inherited by a vertex subset need not be optimal; its crossing count still exceeds the minimum and hence obeys the same lower estimate. This avoids an unjustified exchange of minimization and expectation.

A proved range of the conjectured comparison.

Suppose $\chi(G)\ge t$. Delete vertices until an induced subgraph $H$ is minimal with chromatic number at least $t$. Removing one vertex decreases chromatic number by at most one, so $\chi(H)=t$ and every proper vertex deletion is $(t-1)$-colourable. A vertex of degree at most $t-2$ could be added back using an available colour; therefore $\delta(H)\ge t-1$ and $m\ge(t-1)n/2$. For $t\ge9$ the preceding estimate applies and yields \[ \operatorname{cr}(G)\ge\operatorname{cr}(H) \ge\frac{(t-1)^3n}{512}. \] Place $t$ points in convex position and draw the complete graph with straight segments. Each four-point subset contributes exactly one crossing pair. A generic perturbation avoids triple crossings, giving $\operatorname{cr}(K_t)\le\binom t4$. Consequently the required comparison is proved whenever \[ n\ge\frac{512\binom t4}{(t-1)^3},\qquad t\ge9. \] The condition concerns the critical subgraph's order. Adding isolated vertices to $G$ cannot make it true, because they do not enlarge that obstruction.

What remains after this reduction.

Any counterexample with $t\ge9$ would have a $t$-critical subgraph with order strictly below this threshold. The threshold is asymptotic to $(64/3)t$, so the reduction is a linear bound on the order of a possible critical counterexample for each fixed chromatic number. It is not a uniform finite verification of the conjecture as $t$ varies. For $1\le t\le4$ the desired inequality is immediate because $K_t$ is planar. The present density calculation by itself does not settle $5\le t\le8$, nor the remaining small critical graphs at larger $t$. An attempt to remove the order condition would need substantially more structural information than minimum degree: at $n=t$ the displayed lower coefficient is far below the convex-drawing upper coefficient.

Verification and final status.

The root script checks the threshold comparisons with exact rational arithmetic for $9\le t\le100$, including the first integer order that satisfies each threshold. The probability and criticality arguments supply the parameter proofs; these arithmetic checks are not a search over critical graphs. The sufficient-order theorem is established, but Albertson's full inequality remains unresolved by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3323 (OPG-37068), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Crossing numbers and coloring. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/crossing_numbers_and_coloring.