Large numbers, Knuth's arrow notation, and Ramsey theory
type: Item
instance of: scholarly article
title: Large numbers, Knuth's arrow notation, and Ramsey theory
zbMATH Open document ID: 1021.05097
DOI: 10.1023/A:1020879709125
author: Hans Jürgen Prömel
published in: Synthese
publication date: 2003-04-27T00:00:00Z
review text: This amusing paper deals with several topics from combinatorics. In the introductory part 1 the author starts with the number systems which were used by the Romans and the Greeks, in particular how they denoted great numbers. The second part compiles a lot of the fundamental theorems of Ramsey theory, mainly with respect to the Ramsey constants \(R(t,t)\) and their growth. (Recall: \(R(t,t)\) is the least integer \(n\), for which there holds: If we have a symmetric relation in an \(n\)-element set \(S\), then there are \(t\) elements of \(S\) which are pairwise related or \(t\) elements of \(S\) which are pairwise unrelated.) A special subsection refers to the state of knowledge concerning the Ramsey constants \(R(3,t)\) and their asymptotic behaviour, and another one treats Ramsey theory for graphs. (Here one considers two-colorings of the edge set \(E\) of a graph \(G= (V,E)\) and looks what can be said about the size of monochromatic induced subgraphs.) A further section describes the development which was started by Rota's conjecture, who proposed a geometric analogue to Ramsey's theorem. Among others results of \textit{R. L. Graham}, \textit{R. Leeb} and \textit{B. L. Rothschild} [Adv. Math. 8, 417-433 (1972; Zbl 0243.18011)] and \textit{R. L. Graham} and \textit{B. L. Rothschild} [Trans. Am. Math. Soc. 159, 257-292 (1971; Zbl 0233.05003)] are mentioned. The last section treats Knuth's arrow notation (which is related to the Ackermann function) and Graham's number, which seems to be the largest number ever used in a serious mathematical proof. Some shorter proofs are worked out in detail, for some others an outlook is given.
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 03-03
Mathematics Subject Classification ID: 05-03
Mathematics Subject Classification ID: 00A35
zbMATH DE Number: 1901263
zbMATH Keywords: Ramsey constants
zbMATH Keywords: Graham's number
reviewed by: Egbert Harzheim
MaRDI profile type: Publication
full work available at URL: a:1020879709125
OpenAlex ID: W2091413853
Recommended article: Q4871773
Recommended article: Q4317536
Recommended article: What can we hope to accomplish in generalized Ramsey theory ?
Recommended article: Q4121920
Recommended article: Q5202224
Recommended article: Q5754491
Recommended article: Q5688994
Recommended article: Q4040468
Recommended article: Ramsey Theory
Recommended article: An Introduction to Ramsey Theory
description: scientific article; zbMATH DE number 1901263