Kreuzungszahlen — Turáns Ziegelei
Über diese App
Wie wenige Kreuzungen braucht eine Zeichnung, in der jeder Punkt mit jedem verbunden ist? Knoten ziehen, Bögen umklappen, suchen lassen: Der Zähler landet bestenfalls auf der Formel von Harary–Hill bzw. Zarankiewicz. Mit geraden Kanten bleibt ab K₈ eine Lücke; die Zwei-Seiten-Zeichnung trifft die Formel genau. Ergebnis aus github.com/openai/math (Familie 165, Lean-formalisiert).
Turáns Ziegelei-Problem
Man verbindet n Punkte jeweils paarweise (vollständiger Graph Kn) oder zwei Gruppen jeder mit jedem (Km,n) und zeichnet das in der Ebene. Wie wenige Kreuzungen sind möglich? Paul Turán stellte die Frage 1944 in einer Ziegelei, in der Wagen auf Gleisen von jedem Ofen zu jedem Lager fuhren. Vermutet sind cr(Km,n) = ⌊m/2⌋⌊(m−1)/2⌋⌊n/2⌋⌊(n−1)/2⌋ (Zarankiewicz) und cr(Kn) = ¼⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋ (Harary–Hill). Eine gute Zeichnung zeigt nur, dass so wenige reichen; dass keine weniger schafft, war offen. Ein KI-erzeugtes Preprint aus github.com/openai/math (Familie 165) beweist beide Formeln nach eigener Darstellung, laut Katalog in Lean formalisiert, nicht begutachtet.
Was die App zeigt
Du baust Zeichnungen von Kn oder Km,n, jede Kreuzung leuchtet als Punkt, und ein Zähler vergleicht deine Zeichnung mit der Formel. Zwei Zeichenweisen stehen zur Wahl: gerade Kanten mit frei ziehbaren Knoten oder die Zwei-Seiten-Zeichnung, bei der alle Knoten auf einer Linie liegen und Kanten als Bögen oberhalb oder unterhalb verlaufen. Eine Suche probiert Tausende Änderungen und landet bestenfalls auf der Formel. Mit geraden Kanten bleibt bei K8 und ab K10 eine Lücke, etwa 19 statt 18.
Selbst ausprobieren
Starte mit der Kreisanordnung und ziehe Knoten, bis die Zahl sinkt. Lass dann die Suche laufen und vergleiche deinen Bestwert mit dem Bestwert für gerade Kanten. Wechsle in die Zwei-Seiten-Zeichnung und klicke Bögen an, um sie auf die andere Seite zu klappen: Zwei Bögen auf derselben Seite kreuzen sich genau dann, wenn ihre Endpunkte abwechseln. Mit dieser Zeichenweise lässt sich die Formel genau erreichen.
Häufige Fragen
- Was ist die Kreuzungszahl eines Graphen?
- Die Kreuzungszahl cr(G) ist die kleinste Anzahl von Kantenkreuzungen, mit der sich ein Graph in der Ebene zeichnen lässt. Kanten dürfen dabei beliebig gebogen sein. Planare Graphen haben Kreuzungszahl 0; für vollständige Graphen wächst sie etwa mit n⁴.
- Was ist die Harary-Hill-Vermutung?
- Die Harary-Hill-Vermutung (1962) gibt die Kreuzungszahl des vollständigen Graphen Kn an: ¼⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋. Für Km,n gibt es die entsprechende Formel von Zarankiewicz. Zeichnungen, die diese Werte erreichen, waren lange bekannt; computergestützt bestätigt waren nur kleine Fälle bis K14.
- Ist die Kreuzungszahl von Kn bewiesen?
- Ein KI-erzeugtes Preprint aus dem Katalog github.com/openai/math (Familie 165) beweist nach eigener Darstellung die Formeln von Harary–Hill und Zarankiewicz. Laut Katalog sind die Hauptsätze in Lean formalisiert. Das Preprint ist noch nicht begutachtet.
- Was kann ich in dieser App ausprobieren?
- Du zeichnest Kn oder Km,n mit geraden Kanten oder als Zwei-Seiten-Zeichnung, ziehst Knoten, klappst Bögen um und lässt eine Suche laufen. Ein Zähler vergleicht die Kreuzungen deiner Zeichnung mit der Formel und mit dem Bestwert für gerade Kanten.
Fach: Offene Probleme, gelöst von KI
Mehr aus Offene Probleme, gelöst von KI
- Anderson-Lokalisierung: 2D gegen 3D (3D)
- Barker-Folgen und zirkulante Hadamard-Matrizen
- Barnettes Vermutung: Rundreise über jedes Polyeder (3D)
- Birkhoff-Billard: nur die Ellipse ist lückenlos
- Cardys Formel — Perkolation im Zufallsmosaik
- Die Ebene ist nicht fünffärbbar (Hadwiger–Nelson)
- Doppel-Dimer-Schleifen und CLE₄
- Dreiecksbillard — irrationale Winkel mischen (3D)
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps