Short··0:21·Combinatorics
Hadwiger's Conjecture: OpenAI Claims a Counterexample
Watch on YouTubeAbout the problem →
About this video
Hadwiger's conjecture (1943) says that any graph needing k colours must contain the complete graph K_k as a minor, obtained by squeezing connected groups of dots into single dots. OpenAI claims arbitrarily large counterexamples: graphs with no three mutually unlinked dots, so they need at least m/2 colours for m dots, whose largest clique minor is below 26m/75 + 2/3. The same preprints claim a counterexample to the Colin de Verdière chromatic conjecture and prove a linear list-colouring bound in terms of the Hadwiger number; these are OpenAI's preprints, not yet peer reviewed.
Papers (OpenAI, catalogue result 157):
- A counterexample to Hadwiger's conjecture: github.com/openai/math/blob/main/preprints/A-counterexample-t…
- A counterexample to the Colin de Verdière chromatic conjecture: github.com/openai/math/blob/main/preprints/A-counterexample-t…
- A linear list-coloring bound in terms of the Hadwiger number: github.com/openai/math/blob/main/preprints/A-linear-list-colo…
The animation illustrates the result; it is not a proof. The 12-dot graph is a small example where the conjecture holds; the towers show the paper's bounds for its large graphs.
Gradient Damage: mathematics you can see, equations you can hear.
youtube.com/@gradientdamage
Every result explained: gradientdamage.com/p/157
About the problem
Combinatorics·OpenAI Math·Result 157
Graph coloring, clique minors, and Colin de Verdière invariants
Disproves Hadwiger's conjecture even for fractional coloring: arbitrarily large finite simple graphs with independence number at most two satisfy χf(G) > h(G), where h(G) is the largest clique-minor order. Also disproves the fractional Colin de Verdière chromatic bound χf(G) ≤ μ(G)+1. In the positive direction, every finite nonempty graph satisfies χlist(G) ≤ C h(G) for a universal constant C. (Lean)
Topics
Hadwiger's conjectureHadwiger conjecture counterexampleHadwiger numberclique minorgraph minorgraph colouringgraph coloringchromatic numberfractional chromatic numberColin de Verdière invariantColin de Verdière conjecturelist coloringconnected matchingindependence numbergraph theorycombinatoricsOpenAIOpenAI mathAI mathematicsAI proofmathsmathematicsmath shorts3D animationColin de Verdiere invariantColin de Verdiere conjecture
