Symbolic Moment Calculus II. Why is Ramsey Theory Sooooo …

Short Description
Symbolic Moment Calculus II.: Why is Ramsey Theory Sooooo Eeeenormously Hard? Doron ZEILBERGER. 1. Dedicated to Ron Graham, on his (106) …

Website: www.math.rutgers.edu | Filesize: 135kb

Content
Symbolic Moment Calculus II.: Why is Ramsey Theory Sooooo Eeeenormously Hard?
Doron ZEILBERGER 1
Dedicated to Ron Graham, on his (106)8-th Birthday
Abstract. The short answer to the question in the title is that Ron Graham, one of the leaders of
Ramsey theory, co-author of the denitive book (with Rothschild and Spencer) on the subject and
co-prover of one of its Super-Six theorems (with Leeb and Rothschild), would not choose to work
on an easy subject. A longer answer, from my enumerator’s perspective, is that Ramsey theory,
that according to Motzkin, proves that complete disorder is impossible, is equivalent to proving
that for suciently large universes we are guaranteed islands of order. More precisely, if X is the
random variable,
umber of orderly islands”, we have to nd (or bound) the number of universes
with X=0. If we knew all the moments of X, we would be done. Already the rst moment, the
expectation E[X], gives us some information (as was rst observed by Erd}os). The second moment
is harder, but still tractable, even for humans. But for the…