Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 16. Juni 2019 

Grahams Zahl


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Grahams Zahl (Ronald L. Graham * 1936 amerikanischer Mathematiker) ist die größte jemals in einem Beweis verwendete Zahl laut Guinness-Buch der Rekorde .

Sie ist eine obere Grenze für folgende Problem der Ramsey Theorie.

Grahams Problemstellung

In einem n -dimensionalen Hyperwürfel seien alle Punkte (Ecken Knoten ) mit einer Kante verbunden so dass ein vollständiger Graph auf <math>2^n</math> Knoten entsteht.

Diese Kanten werden nun mit jeweils von zwei Farben eingefärbt. Es ergibt sich Frage wie groß n sein muss damit es notwendigerweise immer einen Untergraph gibt der aus 4 Knoten besteht in einer Ebene liegt. Anders ausgredrückt: Ab welcher Dimension notgedrungen die genannte Form von Ordnung auf?

Das Problem wurde noch nicht gelöst. and Rothschild ( 1971 ) haben gezeigt dass n mindestens 6 sein muss Exoo ( 2003 ) zeigte dass <math> n \ge 11</math>. Zahl liegt weit darüber.

Grahams Zahl: Definition

Grahams Zahl ist so groß dass am besten mit Knuths Pfeil-Schreibweise ausgedrückt werden kann. Diese wird besten anhand einiger Beispiele verdeutlicht (statt ^ oft auch <math>\uparrow</math> verwendet):

<math> m\hat{\ }n=\underbrace{m*m*m*\ldots *m*m}_{n-\mathrm{mal}} </math>

<math> m\hat{\ }\hat{\ }n=\underbrace{m\hat{\ } m\hat{\ m\hat{\ }\ldots\hat{\ } m\hat{\ } m}_{n-\mathrm{mal}} </math>

<math> m\hat{\ }\hat{\ }\hat{\ }n=\underbrace{m\hat{\ }\hat{\ m\hat{\ }\hat{\ } m\hat{\ }\hat{\ }\ldots\hat{\ }\hat{\ m\hat{\ }\hat{\ } m}_{n-\mathrm{mal}} </math>

<math> \vdots </math>

Damit kann man eine Reihe bilden die durch die folgenden Regeln ist:

<math> G_0=4 </math>

<math> G_{N}=3\ \underbrace{\hat{\ }\hat{\ }\hat{\ }\cdots\hat{\ 3 _{G_{(N-1)-\mathrm{mal}}} </math>

Grahams Zahl ist nun definiert als <math> G=G_{64}</math>.

Weblinks



Bücher zum Thema Grahams Zahl

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Grahams_Zahl.html">Grahams Zahl </a>