Section 14.11 Joel Spencer
Joel Spencer is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his Ph.D. from Harvard University in 1970, under the supervision of Andrew Gleason. Professor Spencer is a coauthor, with Ronald Graham and Bruce Rothschild, of the book Ramsey Theory that established Ramsey theory as a mathematical field. [14.11.3.3] Professor Spencer's work was strongly influenced by Paul Erdős, with whom he coauthored 17 papers. Professor Spencer is a Fellow of the American Mathematical Society and a Fellow of the Society for Industrial and Applied Mathematics.
He is a recipient of the Leroy P. Steele Prize for Mathematical Exposition. [14.11.3.1]
Subsection 14.11.1 Joel Spencer's Favourite Proof
Professor Spencer sent us the following reply:
I particularly like the following argument for the diagonal Red/Blue Ramsey:
Pick vertex \(v_1\text{.}\) At least half of remaining vertices are the same colour to \(v_1\text{.}\) Discard others.
Do this \(2n-1\) times.
The selected \(v_1,\ldots,v_{2n-1}\) each have the same colour edge to all vertices to the right. That may be Red or Blue but for half of them it will be the same — say Red.
Those \(n\) points give a Red \(K_n\text{.}\)
No, this doesn't give the best bound for Ramsey \(R(k,k)\text{.}\) But I find it a beautiful argument. [14.11.3.2]
Subsection 14.11.2 Reflection
All what we can say is that we agree with Professor Spencer: This is a beautiful argument that \(R(n,n)\leq 2^{2(n-1)}\text{.}\)
References 14.11.3 References
Joel Spencer. Wikipedia. Retrieved April 7, 2024, from Wikipedia
Joel Spencer Personal Communication. February 5, 2024.
Graham, R. L.; Rothschild, B. L.; Spencer, J. H.; (1991), Ramsey Theory (2nd ed.), New York: John Wiley and Sons