Chi sa rispondere a questa domanda???
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 using only the colours red and black. What is the smallest value of n for which every possible such colouring must necessarily contain a single-coloured complete sub-graph with 4 vertices which lie in a plane? Graham & Rothschild [1971] proved that this problem has a solution, N*, and gave as a bounding estimate 6 ≤ N* ≤ N, with N a particular, explicitly defined, very large number; however, Graham (in unpublished work) revised this upper bound to be a much larger number. Graham’s revised upper bound was later published — and dubbed “Graham’s number” — by Martin Gardner in [Scientific American, "Mathematical Games", November 1977].
The lower bound was later improved by Exoo[2003], who showed the solution to be at least 11, and provided experimental evidence suggesting that it is at least 12. Thus, the best known bounding estimate for the solution N* is 11 ≤ N* ≤ G, where G is Graham’s number.
