Zufälliges Dreieck-Entfernen
Über diese App
Aus dem vollständigen Graphen verschwindet ein zufälliges Dreieck nach dem anderen, bis keins mehr da ist. Die gelöschten Dreiecke blitzen auf, der dreiecksfreie Rest leuchtet. Eine Messreihe bis n = 2000 zeigt: Der Rest geteilt durch n^1,5 strebt gegen 1/(2√2) ≈ 0,354. openai/math Familie 188 (Lean-formalisiert).
Worum es geht
Man startet mit dem vollständigen Graphen auf n Knoten, in dem jeder mit jedem verbunden ist, und löscht immer wieder die drei Kanten eines gleichverteilt zufälligen noch vorhandenen Dreiecks, bis keins mehr übrig ist. Wie viele Kanten bleiben am Ende? Bollobás und Erdős vermuteten 1990 etwa n^(3/2). Bohman, Frieze und Lubetzky bewiesen 2015 den Exponenten n^(3/2+o(1)); die genaue Konstante sagten Joos und Kühn vorher. Ein KI-erzeugtes Preprint aus github.com/openai/math (Familie 188) beweist nach eigener Darstellung: Der Rest geteilt durch n^(3/2) strebt gegen 1/(2√2) ≈ 0,354. Laut Katalog ist der Hauptsatz in Lean formalisiert, begutachtet ist das Preprint nicht.
Was die App zeigt
Der Prozess läuft sichtbar ab: Gelöschte Dreiecke blitzen auf, der dreiecksfreie Rest leuchtet am Ende. Du kannst ein einzelnes Dreieck entfernen, bis zum Ende laufen lassen oder neu würfeln; ein Panel zählt Kanten, entfernte und noch mögliche Dreiecke und den Quotienten Rest / n^1,5. Die Messreihe rechnet im Hintergrund ganze Läufe bis n = 2000 und trägt sie über n auf, mit Mittelwerten und der Linie 1/(2√2). Die Läufe sind exakt gleichverteilte Simulationen; sie illustrieren die Konstante, beweisen sie aber nicht.
Worauf achten
Bei kleinem n schwankt der Rest stark von Lauf zu Lauf; erst die Messreihe zeigt die Konstante. Mit wachsendem n schrumpft die Streuung, und die Mittel steigen langsam auf 0,354 zu. Bei n = 2000 liegt das Mittel noch knapp darunter, etwa bei 0,35, denn der Satz handelt vom Grenzwert und die Annäherung ist langsam. Der Beweis verfolgt das Überleben einzelner Kanten mit einem rekursiven Prioritätstest; davon zeigt die App nichts.
Häufige Fragen
- Was ist der Prozess des zufälligen Dreieck-Entfernens?
- Beim zufälligen Dreieck-Entfernen beginnt man mit dem vollständigen Graphen und löscht wiederholt die drei Kanten eines zufällig gewählten Dreiecks. Jedes noch vorhandene Dreieck hat dabei dieselbe Chance. Der Prozess endet, wenn der Graph dreiecksfrei ist.
- Wie viele Kanten bleiben beim Dreieck-Entfernen übrig?
- Bollobás und Erdős vermuteten etwa n^(3/2) Kanten, also einen verschwindend kleinen Anteil aller n(n−1)/2 Kanten. Bohman, Frieze und Lubetzky bewiesen 2015 diese Größenordnung bis auf Faktoren n^(o(1)). Die genaue Konstante 1/(2√2) stammt aus der Vorhersage von Joos und Kühn.
- Ist die Konstante 1/(2√2) beim Dreieck-Entfernen bewiesen?
- Ein KI-erzeugtes Preprint aus dem Katalog github.com/openai/math (Familie 188) beweist nach eigener Darstellung, dass der Rest geteilt durch n^(3/2) gegen 1/(2√2) ≈ 0,354 strebt, im quadratischen Mittel und damit in Wahrscheinlichkeit. Laut Katalog ist der Hauptsatz in Lean formalisiert. Das Preprint ist noch nicht begutachtet.
- Was kann ich in dieser App ausprobieren?
- Du stellst die Knotenzahl n ein und siehst, wie Dreiecke einzeln oder in einem Lauf verschwinden. Ein Zähler zeigt verbliebene Kanten und den Quotienten Rest / n^1,5. Eine Messreihe bis n = 2000 zeigt, wie sich die Werte der Konstante 0,354 nähern.
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