Luchita

Ezra -ez- Nugroho’s blog

The Search Space of Ramsey (5, 5)

Posted on | October 29, 2011 | 1 Comment

I think any theoretical computer scientists (or students) who have heard of Paul Erdos and Ramsey Numbers are tickled by the well known problem of Ramsey (5, 5).

Ramsey numbers intrigues computer scientists because of the concept seems very simple to understand, but the complexity of the problem is super-exponential. While we know that Ramsey (3, 3) is  6; the search space is quite small that it can be exhausted in one sitting; it may take us a while to find the value of Ramsey (5, 5). That ‘us’ is not just you and me, but our descendants too. And it’s probable that humanity may never know the exact value of Ramsey (6, 6).

Our dear Paul Erdos famously quoted by a friend, Joel Spencer:

“Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.”

For the casual reader who are still reading, here is the obligatory, standard, and surprisingly simple introduction of Ramsey number. Imagine a group of any 6 people in a room, it is guaranteed that there are 3 mutual acquaintances, or 3 mutual strangers. Just run a few iterations in your head on how you’d set up random 6 people and theirs who-knows-who relationships; the property above holds true.  For a formal proof of this, follow the following link.

The casual definition of Ramsey Number R (k, l) is simply the smallest number of people where it is guaranteed that k people are mutual acquaintances or l mutual strangers. The formal definition is defined as the smallest complete graph (clique) where any 2-colloring of the edges, pink and yellow, will guarantee the existence of a complete pink sub-graph of size k, or a yellow sub-graph of size l; but who really cares for formality? Ramsey believes that for any k and l, such number exist.

Ramsey (5, 5) is the smallest number of people where we can guarantee 5 mutual friends or 5 mutual strangers. It doesn’t seem to be above our imaginations; we surely have been in many gatherings where we’d find 5 mutual friends, or 5 mutual strangers. But what is the exact smallest number such requirement is guaranteed ? As of now, we know that the value lies between 43 and 49 people, again seems to be innocent enough, so what’s the big deal, really? There lies the trap to the naivete like me.

To prove that Ramsey (k, l) = m, we need to show that:

  1. For any possible acquaintance configurations of m number of people, we can find k mutual friends or l strangers. This is to show that m is sufficiently big for R (k, l ); mathematically R (k, l) <= m.
  2. There exist some (just 1 is enough) acquaintance configuration of n = m – 1 number of people where we cannot find k friends and l strangers. This is to show that m – 1 is too small for R (k, l); mathematically R (k, l) > n = m – 1.
  3. Once you can show both, we find that m – 1 is too small, but m is big enough, so R (k, l) must be m!

So I really want to know how much effort is needed to really crack this problem, I did some basic number crunching.

Let say we conjectured that R (5, 5) is 43. We know from previous works by experts that 42 is too small, so simply need to show that 43 is big enough. Formally, we need to show that all possible 2-colloring of the edges of complete graph of size 43 that we’d find complete sub-graph of size 5 of one color or the other. All good!

But how many possible 2-colorings are there? First, I computed that a complete graph of size 43 has 903 edges, good. Now how many ways can we 2-color 903 edges? It is basically 2 to the power of 903; again, I computed and I got:

6762169998536515153309949246931412563441245773262355483237
8970755414259527260782012725408753620120050518322559136912
4708969404876163437487680689892432562658442734955518726507
7359763426258258445478710181225103211573094762147219990257
1314803042180668990660938354910463787008

Bam! That is a 272-digit number! Let’s pretend that we’d use our computer, and we can validate 1 configuration per 1 millisecond. That means that we can validate 1000 (per second) * 60 (per min) * 60 (per hour) * 24 (per day) * 365 = 31536000000 configurations per year. We would need 2.144 * 10^262 years! Warning, that’s not in the vicinity of 262 hundred years, it’s in the vicinity of 2 or 3 googol years! So even if all computers owned by Google is used to for this, we are still far far faaaaaarrrrr away from it.

I think Erdos was being optimistic with his alien story. I’d say if such aliens do come and demand R (5, 5), we should just send Russel Peters, Anjelah Johnson, and Colbert to negotiate the terms. Maybe they’ll laugh and mellow out.

Epilogue. Stanisław Radziszowski is a mathematician who has been a diligent curator of all things Ramsey. He publishes  his findings in here. He should probably accompany our pack of comedians to meet the aliens.

Comments

One Response to “The Search Space of Ramsey (5, 5)”

  1. David
    March 15th, 2012 @ 5:05 am

    However, with Moore’s Law, we can double that every 1.5 years, meaning that our formula will be the sum of 2^(2n/3)*31536000000 from n=1 to n=x, or (31536000000 2^(2/3) (-1+2^(2 x/3)))/(-1+2^(2/3)). Setting that expression equal to 2^903 gives x≃1295 years.

    Ok, that’s a bit better than 10^262 years. However, let’s hope those aliens are patient.

Leave a Reply





*