Verbindung hergestellt.connected.<br>num: 30283<br>
<pre>
-------------------------
GRUPPE: de.sci.mathematik
FROM  : Stefan Ram <ram@zedat.fu-berlin.de>
DATE  : 22 Apr 2026 19:10:21 GMT
TEMA  : Grosse Zahlen und schwierige Beweise
---------------------------------------------
  (Ich folge hier einem englischsprachigen populärwissenschaftlichem
  Artikel, aber bin selber auf diesem Gebiet nicht ausgebildet! 
  Ich habe die chaotischer Reihenfolge des Originals umorganisiert,
  und den Text stark gekürzt, diesmal wieder ohne AI.)

  Ein /Graph/ besteht aus Punkten, die paarweise mit Verbindungen
  (Kanten) verbunden sein können. Ein /subkubischer Graph/ ist ein
  Graph, dessen Punkte nie mehr als drei Kanten verlassen.

  Ein Graph G heißt /Minor/ eines Graphen Z, wenn Z einen Teilgraphen
  enthält, aus dem G durch Kantenkontraktion hervorgeht. 
  (Bei einer Kantenkontraktion wird eine Kante entfernt und die beiden
  anliegenden Knoten werden zu einem neuen Knoten vereinigt.)

  Wenn man Graphen generiert, kommt es früher oder später dazu,
  daß ein generierter Graph Minor eines anderen generierten Graphen
  ist. Man kann keine unendliche Sammlung endlicher Graphen erzeugen,
  bei der dies nicht der Fall ist. Aber der Beweis dieser Aussage
  verlangt exotische Axiome außerhalb der üblichen Mathematik!

  (Aussage mit den korrekten Fachbegriffen: "The graph minor theorem
  has a surprisingly high proof-theoretic strength.". Aus einer
  Arbeit: "It has a very complicated and long proof that features
  intricate transfinite inductions." Es sind wohl über 500 Seiten.)

  Nun kann man eine Liste von Graphen betrachten, die folgenden
  Regeln genügt: Der erste Graph darf maximal einen Punkt
  habe, der zweite zwei und so weiter. Außerdem darf kein
  Graph Minor eines späteren sein.

  Es ist wohl nicht so schwierig, das auszuprobieren und dann zu sehen,
  daß man so nicht mehr als 6 Graphen finden kann. SCG(0) = 6.

  Nun dasselbe, mit der folgenden Variation: Der erste Graph darf
  diesmal /zwei/ Punkte enthalten, der zweite drei und so weiter.
  Die Länge der so maximal erzeugbaren Graphenliste nennen wir jetzt
  SCG(1). Es stellt sich heraus, daß diese Folge die in meinem vorigen
  Thread beschriebene Goodstein-Metafolge weit in den Schatten stellt!

  Mehr dazu findet man auf der deutschsprachigen Wikipädie-Seite
  "Minorentheorem" und auf den englischsprachigen Wikipedia-Seiten
  "Friedman's SSCG function", "Robertson–Seymour theorem"
  und "Ordinal analysis".

  Für ein gutes Verständnis des Gebietes wird wohl auch das folgende
  Buch empfohlen:

"Graph Theory" (5th Edition, 2017) von Reinhard Diestel.


head: