Liczba Grahama

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ronald Graham

Liczba Grahama – wielka liczba będąca górnym oszacowaniem rozwiązania problemu Twierdzenia Ramseya. Wpisana do Księgi rekordów Guinnessa jako największa liczba użyta w twierdzeniu matematycznym[1]. Nazwana od jej twórcy, matematyka Ronalda Grahama.

Definicja[edytuj | edytuj kod]

Oznaczmy G_{1}=3\uparrow^4 3. Wtedy G_{2}=3\uparrow^{G_1} 3, G_{3}=3\uparrow^{G_2} 3, itd. Liczbę G_{64} nazywamy liczbą Grahama[2].

Problem Grahama-Rothschilda[edytuj | edytuj kod]

Graham i Rothschild zajmowali się uogólnionym Twierdzeniem Ramseya. W 1971 opublikowali pracę, w której udowodnili istnienie takiej liczby naturalnej n, że w dowolnym dwukolorowaniu krawędzi grafu pełnego powiązanego z n-wymiarową kostką jednostkową zawsze pojawi się płaska jednokolorowa klika K_{4}. Najmniejsze n o tej własności oznaczono przez RG(1,2,2) gdzie:

1 - kolorowane są obiekty jednowymiarowe (krawędzie)

2 - obiekt, który musi się pojawić jest dwuwymiarowy (płaska klika K_{4})

2 - użyto dwóch kolorów

Dokładna wartość tej liczby nie jest znana, zawiera się w przedziale:13 \leqslant n \leqslant G_{64}[3]

Przypisy

  1. Graham's Number (ang.). math.ucsd.edu. [dostęp 2014-03-09].
  2. Graham's Number (ang.). mathworld.wolfram.com. [dostęp 2014-03-09].
  3. Jerome Barkley: Improved lower bound on an Euclidean Ramsey problem (ang.). arxiv.org, 2008-11-06. [dostęp 2014-04-26].

Bibliografia[edytuj | edytuj kod]

  • Tomasz Bartnicki. Czy 11 jest największą liczbą na świecie?. „Matematyka Społeczeństwo Nauczanie”. 39, s. 36, styczeń 2007. 

Zobacz też[edytuj | edytuj kod]