Context
Graham's number is connected to the following problem in Ramsey theory:
Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on 2n vertices. Then colour each of the edges of this graph either red or blue.
What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on 4 coplanar vertices?
In 1971, Graham and Rothschild proved that this problem has a solution, N*, and gave as a bound 6 ≤ N* ≤ N, with N being a very large, explicitly defined number:, where in Knuth's up-arrow notation. The lower bound of 6 was later improved to 11 by Geoff Exoo in 2003, and to 13 by Jerome Barkley in 2008. Thus, the best known bounds for N* are 13 ≤ N* ≤ N.
Graham's number, G, is much larger than N:, where . This weaker upper bound for the problem, attributed to an unpublished work of Graham, was eventually published and named by Martin Gardner in Scientific American in November 1977.
Read more about this topic: Graham's Number
Famous quotes containing the word context:
“Among the most valuable but least appreciated experiences parenthood can provide are the opportunities it offers for exploring, reliving, and resolving one’s own childhood problems in the context of one’s relation to one’s child.”
—Bruno Bettelheim (20th century)
“The hippie is the scion of surplus value. The dropout can only claim sanctity in a society which offers something to be dropped out of—career, ambition, conspicuous consumption. The effects of hippie sanctimony can only be felt in the context of others who plunder his lifestyle for what they find good or profitable, a process known as rip-off by the hippie, who will not see how savagely he has pillaged intricate and demanding civilizations for his own parodic lifestyle.”
—Germaine Greer (b. 1939)