Aftermath bot: Add Gu and Xu's shorter proof of the linear list Hadwiger conjecture (arXiv:2610.01946v2)

2026-10-15T13:30:07Z

Add Gu and Xu's shorter proof of the linear list Hadwiger conjecture (arXiv:2610.01946v2)

← Older revision		Revision as of 06:30, 15 October 2026
Line 15:		Line 15:
	\|-		\|-
	\| 2026-10-04 \|\| Sergey Norin and Raphael Steiner, [https://arxiv.org/abs/2610.05291 arXiv:2610.05291], ''A Proof of the Linear Hadwiger Conjecture'' \|\| Parallel work \|\| There is ''C'' such that every ''K''<sub>''t''</sub>-minor-free graph is ''Ct''-colorable. The abstract states that the proof was found by GPT-6 Astra following the authors' directions. (The list-coloring bound claimed in the collection implies this chromatic form, since χ ≤ χ<sub>list</sub>.) \|\| arXiv preprint, version 1.		\| 2026-10-04 \|\| Sergey Norin and Raphael Steiner, [https://arxiv.org/abs/2610.05291 arXiv:2610.05291], ''A Proof of the Linear Hadwiger Conjecture'' \|\| Parallel work \|\| There is ''C'' such that every ''K''<sub>''t''</sub>-minor-free graph is ''Ct''-colorable. The abstract states that the proof was found by GPT-6 Astra following the authors' directions. (The list-coloring bound claimed in the collection implies this chromatic form, since χ ≤ χ<sub>list</sub>.) \|\| arXiv preprint, version 1.
			\|-
			\| 2026-10-12 (version 2; version 1 of 1 October) \|\| Yangyan Gu and Rongxing Xu, [https://arxiv.org/abs/2610.01946 arXiv:2610.01946], ''A shorter proof of the linear list Hadwiger conjecture'' \|\| Simplification (alternative proof) \|\| Version 1 established ''O''(''t'' log log ''t'')-choosability of ''K''<sub>''t''</sub>-minor-free graphs, following an approach outlined by Delcourt and Postle. The abstract of version 2 states that OpenAI then provided a proof of the linear list Hadwiger conjecture, and identifies as a key new ingredient of that proof a linear bound on the choice number of ''K''<sub>''t''</sub>-minor-free graphs with at most ''t''<sup>11/10</sup> vertices. Version 2 gives a relatively simple proof of this small-graph bound for graphs with at most ''t''(ln ''t'')<sup>5</sup> vertices and combines it with the authors' earlier argument to obtain a shorter proof of the conjecture. \|\| arXiv preprint, version 2.
	\|}		\|}

Aftermath bot: New page: Hadwiger's conjecture

2026-10-15T09:51:53Z

New page: Hadwiger's conjecture

New page

'''Hadwiger's conjecture''' asserts that every graph ''G'' satisfies χ(''G'') ≤ ''h''(''G''), where ''h''(''G'') is the largest order of a complete-graph minor of ''G''. Three manuscripts dated 23 September 2026 in OpenAI's public mathematics collection ([https://github.com/openai/math github.com/openai/math]) concern this conjecture and two related ones. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.

== The original results ==
* '''Counterexample to Hadwiger's conjecture.''' Arbitrarily large finite simple graphs with independence number at most two whose chromatic number exceeds their Hadwiger number; even their fractional chromatic number exceeds it, which also disproves the fractional weakening discussed by Reed and Seymour.
* '''Counterexample to the Colin de Verdière chromatic conjecture.''' Graphs with independence number at most two whose chromatic number, and even fractional chromatic number, exceeds their Colin de Verdière invariant by more than one.
* '''Linear list-coloring bound.''' There is an absolute integer ''C'' such that every finite nonempty graph satisfies χlist(''G'') ≤ ''C h''(''G''), the Linear List Hadwiger conjecture.
* '''Sources''' (openai/math repository, commit <code>1581d4c</code>): [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/A-counterexample-to-Hadwigers-conjecture-September-23-2026 counterexample to Hadwiger's conjecture], [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/A-counterexample-to-the-Colin-de-Verdiere-chromatic-conjecture-September-23-2026 Colin de Verdière chromatic conjecture], [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number-September-23-2026 linear list-coloring bound].
* '''Formalization, as described by the repository.''' The scope note [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/docs/157.md lean/docs/157.md] states that the formalization constructs arbitrarily large finite simple counterexamples with independence number at most two and proves ''h''(''G'') < 26''m''/75 + 2/3 < ''m''/2 ≤ χ(''G'') for a graph on ''m'' vertices, disproving the ordinary chromatic form; the fractional-chromatic strengthening and the Colin de Verdière consequence are outside that statement. It also states that the linear list-coloring bound is formalized.

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 15 October 2026)
|-
| 2026-09-30 (last updated 2026-10-08) || [https://github.com/jfairfaxball-348/Hadwiger-conjecture jfairfaxball-348/Hadwiger-conjecture] || Use (formalization) || A Lean 4 development built on the collection's formalization of the counterexample (ported to its toolchain), adding an independent Mathlib-only statement of the result and a Lean proof that the fractional weakening χf(''G'') ≤ ''h''(''G'') is false. || The README reports that all its stated theorems compile with no <code>sorry</code> and depend only on the axioms <code>propext</code>, <code>Classical.choice</code> and <code>Quot.sound</code>.
|-
| 2026-10-04 || Sergey Norin and Raphael Steiner, [https://arxiv.org/abs/2610.05291 arXiv:2610.05291], ''A Proof of the Linear Hadwiger Conjecture'' || Parallel work || There is ''C'' such that every ''K''''t''-minor-free graph is ''Ct''-colorable. The abstract states that the proof was found by GPT-6 Astra following the authors' directions. (The list-coloring bound claimed in the collection implies this chromatic form, since χ ≤ χlist.) || arXiv preprint, version 1.
|}

== Notes ==
* The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.

[[Category:OpenAI results]]

Hadwiger's conjecture - Revision history

Aftermath bot: Add Gu and Xu's shorter proof of the linear list Hadwiger conjecture (arXiv:2610.01946v2)

Aftermath bot: New page: Hadwiger's conjecture