MathematikPreprintTheorie3 Min. Lesezeit

DER BEWEIS EINER KI, FÜR MENSCHEN NEU GEZEICHNET

Zeichnen Sie ein paar Punkte und verbinden Sie einige davon mit Linien. Mathematiker nennen das einen Graphen; die Punkte sind Knoten, die Linien Kanten, und die Zahl der Linien, die einen Punkt berühren, ist sein Grad. Ein Baum ist ein Graph ohne Kreise, der in einem Stück zusammenhängt, wie ein verzweigter Zweig; ein Baum mit t Punkten hat immer t − 1 Linien.

Anfang der 1960er-Jahre stellten Paul Erdős und Vera T. Sós eine einfache Frage: Wie viele Linien zwingen einen Graphen, jeden Baum einer gegebenen Größe zu enthalten? Ihre Antwort, die Erdős-Sós-Vermutung, lautet:

Hat ein Graph einen Durchschnittsgrad größer als t − 2, so enthält er jeden Baum mit t Knoten.

Die Schwelle ist scharf. Man nehme getrennte Kopien eines vollständigen Graphen mit t − 1 Punkten, in dem jedes Paar verbunden ist: Jeder Punkt hat genau t − 2 Nachbarn, doch kein Teil ist groß genug, um einen Baum mit t Punkten aufzunehmen. Die Schwierigkeit liegt im Wort Durchschnitt. Hätte jeder einzelne Punkt mindestens t − 1 Nachbarn, könnte man einen Baum problemlos Ast für Ast platzieren. Doch ein Durchschnitt sagt nichts über einen einzelnen Punkt: Manche haben vielleicht Hunderte Nachbarn, andere fast keine.

Sechzig Jahre Teilantworten

Laut der im Artikel geschilderten Geschichte stammt das Problem aus den Jahren 1962–1964 und wurde zentral für den Zweig der Mathematik, der untersucht, wie viele Kanten ein bestimmtes Muster erzwingen. Sonderfälle fielen nach und nach: Sterne, Pfade, Doppelsterne, Bäume mit wenigen Ästen. Anfang der 1990er-Jahre kündigten vier Mathematiker — Ajtai, Komlós, Simonovits und Szemerédi — einen Beweis für sehr große Bäume an, doch neuere Arbeiten merken an, dass nie ein vollständiges Manuskript veröffentlicht wurde. Weitere Teilergebnisse folgten 2021, 2024 und 2026. Am 4. September 2026 stellten Reed und Stein einen Beweis für große, dichte Graphen online, der nach ihren Angaben ohne KI entwickelt wurde.

Dann kam ein Bericht. Im September 2026 schrieben Tom Adamczewski und Thomas Bloom in einem Dokument namens FrontierMath Erdős einen Beweis der vollständigen Vermutung einer Vorabversion des KI-Modells GPT-6 Astra zu. Das ursprüngliche Zählargument ist öffentlich, und ein begleitendes Repository dokumentiert die autonome Beweissuche der KI sowie eine formale Verifikation in der Beweisprüfsprache Lean. Die Autoren des Berichts riefen zudem menschliche Experten auf, ausführlichere, traditionelle Darstellungen zu verfassen.

Einen Graphen Punkt für Punkt aufdecken

Jay Cummings von der California State University, Sacramento, folgt diesem Aufruf. Sein 27-seitiger Artikel behält das zentrale Zählargument der KI bei, erzählt es aber anders:

  1. Den Graphen schrittweise aufdecken. Die Knoten in irgendeiner Reihenfolge auflisten und einzeln aufdecken, zusammen mit den Kanten zwischen den bereits gezeigten.
  2. Mehr verlangen. Statt irgendeiner Kopie des Baums eine suchen, deren gewählte „Wurzel“ genau auf dem ersten Knoten sitzt. Mehr zu verlangen macht den Beweis leichter.
  3. Die frühen Nachbarn zählen. Das sind die Nachbarn des ersten Knotens, die auftauchen, bevor eine solche Kopie erscheint. Man summiert sie über alle möglichen Reihenfolgen.
  4. Die Summe beschränken. Durch Vertauschen von Knoten oder ganzen Blöcken der Reihenfolge — Züge, die sich stets rückgängig machen lassen — zeigt Cummings, dass es im Mittel über alle Reihenfolgen höchstens t − 2 frühe Nachbarn gibt.

Der letzte Schritt ist kurz. Enthielte der Graph keine Kopie des Baums, wäre jeder Nachbar des ersten Knotens in jeder Reihenfolge früh. Gemittelt über alle Reihenfolgen ist das genau der Durchschnittsgrad — der nach Voraussetzung t − 2 übersteigt. Widerspruch: Der Baum muss vorhanden sein.

Der Beweis nutzt nur die Summe der Grade, nicht deren Verteilung. Cummings liefert auch eine probabilistische Version und rechnet Bäume mit vier und fünf Knoten an konkreten Graphen durch.

Ein Beweis als Bilderbuch

Der Artikel enthält 32 Abbildungen. Er schließt mit einer klassischen Folgerung: Färbt man alle Linien eines vollständigen Graphen mit q Farben, enthält eine Farbe stets einen gegebenen Baum, sobald der Graph q(t − 2) + 2 Knoten hat. In einer abschließenden Erklärung schreibt Cummings, er habe den Text in einem langen Dialog mit ChatGPT entwickelt, die neuen Darstellungsideen — frühe Nachbarn, die expliziten Zerlegungen, die Zeichnungen — stammten von ihm, und er habe alles geprüft und übernehme die volle Verantwortung.

Er vergleicht seine Darstellung mit anderen neueren von Riordan und Scott, Wood sowie Frederickson und merkt an, dass die Methode bereits auf Netze mit Richtungen und auf „Hypergraphen“ erweitert wurde, wobei einige dieser Erweiterungen ebenfalls GPT-6 Astra zugeschrieben werden. Sein Beitrag, schreibt er, sei „eine leserzentrierte, visuelle Darstellung des Arguments, keine neue Lösung der Vermutung“.