Large numbers, Knuth's arrow notation, and Ramsey theory (Q1868161)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Large numbers, Knuth's arrow notation, and Ramsey theory |
scientific article |
Statements
Large numbers, Knuth's arrow notation, and Ramsey theory (English)
0 references
27 April 2003
0 references
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.
0 references
Ramsey constants
0 references
Graham's number
0 references