Dedicated to A. Nilli, on her R(4,4)-th birthday
Abstract: Using some general vague principles of rough classification of W. T. Gowers, we prove the asymptotic bound of the title for the celebrated diagonal Ramsey Numbers.
Combinatorics is not unlike a competitive sport, and sometimes a breaking of a record has mostly psychological rather than conceptual significance. Hence when, on May 6, 1954, Sir Dr. Roger Bannister ran one mile in less than four minutes, the whole world was excited, even though both mile and minute are arbitrary human-made units.
Four is also a very significant number in both the mathematical and physical universes. Until recently we believed that we live in 4 dimensions, and even if string theory turns out to be the theory of everything, the remaining 6 dimensions are negligible. Hara and Slade proved that above four dimensions, self-avoiding walks behave basically like random walks. In four dimensions they seem to almost do so, but for dimensions less than four they are probably very different. Smale proved that the Poincare conjecture is true for dimension greater than four, while Freedman and Donaldson proved the existence of kinky spaces in dimension four. It is trivial that three colors do not suffice, while five colors suffice to color a planar map, yet it is relatively hard to prove that four colors suffice.
Here we announce the breaking of the notorious 4 barrier for the asymptotic upper bound for the n-th root of R(n,n). The details are all contained in the source code and output of 300 hours of CPU of the Maple package FRANK written by the second author, and executed by the first author. Here we will only describe, in very vague terms the rough ideas behind the proof.
Most of the credit is due to W. T. Gowers, the second-youngest member of the top-16 most influential living mathematicians, according to Cliff Pickover's list (`Wonders of Numbers', Oxford Univ. Press, 2001, p. 88). This must be Gowers's favorite problem, since he listed it first in his list of 19 open problems for the 21st century ([1], p. 17).
The very general, rather rough, extremely vague, but nevertheless seminal, principle behind our proof is described succinctly on p. 74 of [2]. Partition the family of graphs into a union of disjoint families, each of them with additional structure, and prove the upper bound separately for each of them, using different methods, if necessary.
But this is easier said than done. What if the number of cases exceeds, say, 10000, and each case requires solving a recursive inequality involving a system of 100 equations for 100 unknown discrete functions, each of which depend on up to 50 variables? Luckily, the first author, assisted by its sibling, Shalom B. Ekhad (with some help from Shalom's kind editor and agent, Jeff Lagarias), and all the computer servants of the enigmatic, elite, and secret society called the Bitchen Mathematicians. (consisting of the world's 12 greatest mathematicians), made the proof possible.
Recall that the classical proof that R(n,n) is less than (2n-2)!/(n-1)!)**2 consists in introducing a more general quantity, R(n,m) and, claiming, by an extremely naive and simple-minded pigeon-principle argument, that R(m,n) is less than R(m-1,n)+R(m,n-1), which implies by induction that R(m,n) is less than (m+n-2)!/((m-1)!(n-1)!).
This simple argument takes no advantage of any extra structure that a graph might have, that would force an n-clique or m-independent set. We introduce ten attributes: the number of edges, and certain parameters derived from the spectrum of the graph, using Alon and Milman's celebrated result about the second-largest eigenvalue. Then each family is treated separately, getting a system of recursive inequalities, that is solved using the famous WZ method, and then analyzed asymptotically by the Birkhoff-Trijinski method.
Much more important than the result itself, is the method of proof, that, unlike previous `computer-proofs', like the Four Color Theorem or Kepler's Conjecture that were merely computer-assisted, the present proof is purely computer-generated. The only human parts were the very vague idea of Gowers mentioned above, and of course some routine programming by the second author.
2. W. T. Gowers. The two cultures of mathematics, in: `Mathematics: Frontiers and Perspectives', edited by V. Arnold et. al, AMS, 2000. Available from W. T. Gowers's on-line papers.