Skip to content
All apps

Crossing numbers — Turán's brickyard

About this app

How few crossings does a drawing need in which every point is joined to every other? Drag vertices, flip arcs, let it search: at best the counter lands on the Harary–Hill or Zarankiewicz formula. With straight edges a gap remains from K₈ on; the two-page drawing hits the formula exactly. Result from github.com/openai/math (family 165, Lean-formalised).

Turán’s brick factory problem

Connect n points pairwise (the complete graph Kn), or two groups everyone-to-everyone (Km,n), and draw it in the plane. How few crossings are possible? Paul Turán posed the question in 1944 in a brick factory where carts ran on tracks from every kiln to every store. The conjectured values are cr(Km,n) = ⌊m/2⌋⌊(m−1)/2⌋⌊n/2⌋⌊(n−1)/2⌋ (Zarankiewicz) and cr(Kn) = ¼⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋ (Harary–Hill). A good drawing only shows that this many suffice; that no drawing does better was open. An AI-generated preprint in github.com/openai/math (family 165) claims proofs of both formulas, listed as formalised in Lean and not peer-reviewed.

What the app shows

You build drawings of Kn or Km,n, every crossing lights up as a dot, and a counter compares your drawing with the formula. There are two drawing styles: straight edges with freely draggable vertices, or the two-page drawing, where all vertices sit on a line and edges run as arcs above or below it. A search tries thousands of changes and at best lands on the formula. With straight edges a gap remains for K8 and from K10 on, for example 19 instead of 18.

Try it yourself

Start from the circular layout and drag vertices until the count drops. Then run the search and compare your best value with the best possible using straight edges. Switch to the two-page drawing and click arcs to flip them to the other side: two arcs on the same side cross exactly when their endpoints alternate. In this style the formula can be reached exactly.

Frequently asked questions

What is the crossing number of a graph?
The crossing number cr(G) is the smallest number of edge crossings with which a graph can be drawn in the plane. Edges may be curved in any way. Planar graphs have crossing number 0; for complete graphs it grows roughly like n⁴.
What is the Harary–Hill conjecture?
The Harary–Hill conjecture (1962) gives the crossing number of the complete graph Kn as ¼⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋. Zarankiewicz’s formula plays the same role for Km,n. Drawings that reach these values have long been known; computer verification covered only small cases up to K14.
Has the crossing number of Kn been proved?
An AI-generated preprint in the catalogue github.com/openai/math (family 165) claims proofs of the Harary–Hill and Zarankiewicz formulas. The catalogue lists the main theorems as formalised in Lean. The preprint has not yet been peer-reviewed.
What can I try out in this app?
You draw Kn or Km,n with straight edges or as a two-page drawing, drag vertices, flip arcs and let a search run. A counter compares the crossings in your drawing with the formula and with the best value achievable with straight edges.

Subject: Open problems, solved by AI

More from Open problems, solved by AI

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps