An exponential improvement for diagonal Ramsey
arxiv.org
arxiv.org
How many people must you have at a party such that either some three have mutually shaken hands, or some three have mutually not shaken hands?
Ramsey theory looks at the generalisation of this.
One result is that in any (countably) infinite network (graph) there is either an infinite complete graph (all edges exist) or an infinite independent set.
Consider any proposition P which, when given two individuals, P(x,y) returns either True or False. Ramsey theory says that no matter what lower limit you put, call it K, there will be a number R(K) such that given R(K) people you can either find K people such that among them P(x,y) is always True, or you can find K people such that among them P(x,y) is always False.
Then we can ask: How fast does R grow?
Paul Erdős said[1]:
"Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack."
So this paper presents a major advance in understanding how these numbers behave in the long term.