Log in


Ramsey Theory And Graham's Number trivia

I have been reading Martin Gardner's The Colossal Book Of Mathematics.  It is, as the title strongly suggests,  a colossal collection of Gardner's recreational mathematics columns in  Scientific American, with addenda written specially for the book.

I recently finished reading the piece on Ramsey Theory, a branch of  graph theory. A typical Ramsey Theory problem is "what's the minimum number of people you can invite to a party so that there's a group of three that all know each other". The number of people is said to be the Ramsey number for this problem. You can also have more categories than just "know" and "don't know" each other. For instance, you might specify related,not related but friends, and don't know each other at all.

Of course, Ramsey theory is not just about inviting people to parties. The party examples given are just real world illustrations of the more abstract actual problems in Ramsey theory.

RT made it into the news several years back when someone wrote a letter to Ann Landers about it. Apparently someone had just used a lot of resources solving a particularly tricky problem, and the writer picked up on the "party invitation" aspect of it and dismissed it as completely trivial. (I'll bet she would have really blown a gasket over the dining philosopher's problem).

I remember the letter when it was published, especially the writers remark that "the time and money spent on this project could have better used....toward finding ways to get food to ....starving children". This remark planted a seed which eventually bloomed into what I call babydoc3's Starving Children Principle: that people who dismiss anything and everything by saying "you could have fed starving children instead" should themselves be fed to starving children.

Landers, to her credit, asked any knowledgeable parties to provide a better explanation of the problem. Martin Gardner sent her a letter explaining the graph theory behind it, which was not printed. Gardener says "perhaps Miss Landers remained baffled as to what earthly use this result could possibly have." I think that Gardner didn't understand that Landers didn't share the enthusiasm for graph theory Gardner's regular readers have. :)

There was interesting information about Graham's number in this chapter. Graham's number is an upper bound to the Ramsey number of an as yet unsolved problem. It is a great big number. As far as I know, it is the biggest number that has a name (there are several larger numbers that don't.)  I won't go into the details about how it is computed, but suffice it to say that it is 3 raised to a power that has more digits than I can put into a livejournal entry (and that understates it.) 

I knew about Graham's number , but I did not know where it came from. I also didn't know that it's discoverer, Ronald  Graham, is a past president of the International Juggler's Association. Wow. Juggling and graph theory are only two skill sets, but they are such disjoint skill sets I think Graham qualifies as a renaissance man.
Tags: ,


I remember the Discussion for the wikipedia page for Graham's number around when I first heard about it. There were all these people like, 'Well, if we can't print out the number, can't we print out an approximation? Like in scientific notation?'

When told no, they'd be like, well, what about if instead of squaring we use tetration, etc... None work. The people wanting to know 'what number it is' just seemed to get more and more frustrated at these answers.

Knuth's up arrow notation is the only decent way of representing it and it's really just a set of directions for creating it.

It is so big that if you were to paint a digit of it on every atom in the universe into some method of displaying a digit, you still wouldn't even get close. The same applies for the # of digits in the scientific notation you'd need to represent it. More digits than you can put in a livejournal entry is more like more digits than can fit in a universe! : )