Recommendations

Discussion

[1] David Roberts on topics: #combinatorics #RamseyTheory (Oct. 22, 2013)

Show discussion.

The title of this paper is misleading. The number most often referred to as 'Graham's number', sometimes denoted by g_64, was originally mentioned in a 1977 article by Martin Gardner in Scientific American. It arose as an upper bound on a particular problem from Ramsey theory, a subfield of combinatorics [1]. +John Baez has some history of this [2], most notably the fact that g_64 doesn't appear in the joint paper Graham eventually published with Rothschild, but the smaller bound F^7(12), where F(n) = 2↑...n...↑3 (see [3] for Knuth's up-arrow notation). The paper by Lavrov, Lee and Mackey establishes a much smaller upper bound on the Ramsey-theoretic problem, and it is the exact solution to this problem that they are calling 'Graham's number'. In fact the bound given in the title, 2↑↑↑6, is a simplification, and not the smallest bound arrived at in the paper, which is 2↑↑2↑↑2↑↑9 (despite the apparent increase in complexity, this number is much smaller than 2↑↑↑6). In terms of the function F of Graham and Rothschild, the LLM bound is between F(4) and F(5).

[1] http://en.wikipedia.org/wiki/Ramsey_theory
[2] https://plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ
[3] http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

#spnetwork arXiv:1304.6910 #RamseyTheory #combinatorics  

http://arxiv.org/abs/1304.6910