Talk:Ramsey's theorem

From Wikipedia, the free encyclopedia

About the intro - referring to Ramsey theory as studying homogeneous sets seems to me more helpful than 'various regularity properties'. Of course RT isn't limited to that.

Charles Matthews 11:12, 1 Mar 2004 (UTC)

No, "homogeneous" is too specific. Ramsey theory can be applied for much more general circumstances. For example it might be looking for arithmetic progressions that appear as subsequences of a sequence of integers -- I don't know that anyone used the word "homogeneous" for to mean that a sequence is an arithmetic progression. I wrote "regularity property" because it is poorly defined and seems to cover the examples I can think of. --Zero 11:40, 1 Mar 2004 (UTC)

Well, as you say, it's poorly defined. So, is the introduction to help you, or others?

By the way, I think a page called homogeneous set would help. For example the logicians use the idea. Since Ramsey was interested in that case, doesn't it make some sense to explain the theory starting from there? It is often asked that there should be more motivational explanation.

Charles Matthews 12:17, 1 Mar 2004 (UTC)

I considered changing this myself, but I'm not well-versed in Ramsey Theory so my assumption that it's an error might be incorrect. In the proof of the finite case of Ramsey's Theorem, when doing induction on r and s, this page states that the base cases are R(n,1) = R(1,n) = n. However, if I understand the meaning of R(r,s), it doesn't make sense to have either r or s equal to 1 - you can't color the 2-edges of a graph with only one vertex. Am I wrong in thinking that it should say R(n,2) = R(2,n) = n?

Daniel Lepage 5:03, 6 May 2004 (UTC)

I don't understand your reason, but you are correct that there is a mistake. R(n,2) = R(2,n) = n can be used to start the induction, or R(n,1) = R(1,n) = 1 can be. I edited the article to use the latter. The statement "R(n,1)=1" means: if the edges of the complete graph with 1 vertex are colored using two colors (there are no edges but that just makes the coloring task easier), then there is a complete subgraph of one vertex whose edges all (i.e. all zero of them) have the second color; and this is not true for smaller complete graphs (of which there aren't any anyway). This inclusion of trivial boundary cases is pretty normal, but if it bothers anyone it would be acceptable to use R(n,2) = R(2,n) = n as the starting point. --Zero 09:17, 7 May 2004 (UTC)

Both, please. It would be helpful to some readers. Charles Matthews 09:28, 7 May 2004 (UTC)

Contents 1 Example: R(3,3;2) is 6 2 No Lower Bound in Matrix 3 Erdős citation? 4 ;(number of colours) or ;(size of hyperedges) 5 Ramsey's original theorems 6 A Multicolor Example R(3,3,3)=17 7 Colour, not color

[edit] Example: R(3,3;2) is 6

http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Example:_R.283.2C3.3B2.29_is_6

Isn't the illustration that goes along with the example wrong? Maybe I misunderstand, but shouldn't there be six vertices, not 5?

No, the diagram is showing that R(3,3;2) is greater than 5. "it is possible to 2-colour a K5 without creating any monochromatic K3, showing that R(3,3;2) > 5. The unique coloring is shown to the right" We have already shown that R(3,3;2) is less than or equal to 6 so it must equal 6. Greg321 23:28, 16 January 2006 (UTC)

The Ramsey Theorem is not limited to complete graphs; it applies to any graph. "A number N has the (p, q) Ramsey property if and only if for every graph G of N vertices, either G has a complete p-gon (complet subgraph of p vertices) or the complement of G has a complete q-gon" Roberts, Fred. Applied combinatorics. New Jersey, Prentice-Hall. 1984. Pg 327

Each graph G on N vertices embeds in the complete graph K_N and induces a unique 2-coloring on the complete graph. Namely, color an edge blue if it appears in G, and color it red if it doesn't — that is, if it appears in the complement of G. The statement in Roberts's book is equivalent to saying that N has the (p, q) Ramsey property if and only if for every 2-coloring of K_N, there is either a blue p-clique or a red q-clique in the graph. Michael Slone (talk) 19:46, 19 April 2006 (UTC)

[edit] No Lower Bound in Matrix

Extremely minor quibble, or maybe I'm not understanding. Why are only upper bounds given for some ramsey numbers, such as R(7,10)? Surely there is some known lower bound, say, at least 7? 198.99.123.63 02:27, 28 March 2006 (UTC)

Absolutely there is a lower bound: 7 is trivial, but also it's fairly easy to see that the ramsey numbers must all be increasing (in each row and in each column) and thus R(7,10) = R(10,7) > 232, and R(8,10) = R(10,8) > 317. We could include them in the table. However, the table came from a table in the Radziszowski paper, which made an effort to explain where each bound came from, and thus only included those results with definiate papers that went with them. (I think anyway)

[edit] Erdős citation?

The quote from Paul Erdős strikes me as quite similar to the quote Hoffman gives in "The Man Who Loved Only Numbers". I've seen it cited[1] from the first edition:

Imagine that an evil spirit can ask of you anything it wants and if you answer incorrectly, it will destroy humanity. "Suppose it decides to ask you the Ramsey party problem for the case of a fivesome. Your best tactic, I think, is to get all the mathematicians in the world to drop what they're doing and work on the problem, the brute–force approach of trying all the specific cases... But if the spirit asks about a sixsome, your best survival strategy would be to attack the spirit before it attacks you."

And I've read it in my own 2nd edition (1st edition paperback, pp. 53-54:

Erdős liked to tell the story of an evil spirit that can ask of you anything it wants. If you answer incorrectly, it will destroy humanity. "Suppose," Erdős said, "it decides to ask you the Ramsey party problem for the case of a fivesome. Your best tactic, I think, is to get all the mathematicians in the world to drop what they're doing and work on the problem, the brute–force approach of trying all the specific cases"--of which there are more than 10 to the 200th power (the number 1 followed by 200 zeroes). "But if the spirit asks about a sixsome, your best survival strategy would be to attack the spirit before it attacks you. There are too many cases even for computers."

Now I can easily imagine Erdős telling both the version above and the verson in the article, but I'd like a citation if possible. I'd hate to think we have a misquote here. I noticed that the only Google hits on the article's quote come from Wikipedia and its mirrors/spinoffs. CRGreathouse 02:25, 18 July 2006 (UTC)

He told this story dozens (maybe hundreds) of times and it's unlikely that every time he said it exactly the same way. I heard it from him quite a few times myself. However, I bet he never said "the brute–force approach of trying all the specific cases" because that is impossible and he was perfectly clever enough to know it is impossible. What he said in my hearing was that all the mathematicians and all the computers in the world should be devoted to the problem and probably they would find a way to solve it. I don't remember him ever calling it the "Ramsey party problem" either. I think these versions are just Hoffman's poor retelling. Of course my personal recollection doesn't meet Wikipedia requirements so we still need a citation. McKay 14:11, 12 October 2006 (UTC)

Having just finished typing that, I found a cited version that matches my own memory much better (but sometimes it was an "evil demon" rather than "aliens"):

Erdos related the following anecdote: "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 [that is, R(5,5)]. 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. (Graham, Ronald L. and Joel H. Spencer. Ramsey Theory. Scientific American July 1990: 112-117). [2] McKay 14:15, 12 October 2006 (UTC)

[edit]  ;(number of colours) or ;(size of hyperedges)

As far as I can see, in modern usage there are a couple of different ways to denote classical Ramsey numbers; essentially based on laziness (as so much mathematical notation is). The necessary size of a 4-coloured complete graph in order to guarantee an (i+2) clique in the i'th colour, for at least one i, is usually ; but if you want to guarantee a triangle in any of the triangles, you may write as an alternative to . This is the terminology used by both Landman-Robertson and Radziszowski. I do not at the moment have access to Graham & al.; but I remember having seen things like or even for , a long time ago. However, I don't recall having seen an irredundancy like ; if anyone may tell me where this might be found, I'd appreciate it.

Actually, I didn't note that this slightly unusual and irredundant notation is used here, until I noticed that this was removed on the page Ramsey theory, by an anonymous user; but then immediately put back. The latter seemed a bit too fast.

Actually, there is a good reason to follow Landman-Robertson and Radziszowski here; namely, to avoid confusion. In fact, in his dynamic survey Radziszowski uses in a quite different meaning; letting this s stand for the size of the 'edges' in a hypergraph. Thus, you may find a statement like this:

(from section 5 Multicolor graph numbers, of the latest edition of the dynamic survey). To repeat: here does not mean

Colouring with two colours forces at least a triangle in one of the three colours,

which is the contradictory meaning resulting from trying to apply the present notation in Ramsey's theorem, but rather

Three-colouring all two-sets forces at least one 3-set, all of whose 2-subsets have the same colour.

A reader of Ramsey's theorem will have easier access to modern literature, and in particular to the dynamic survey, if we change the notation in both articles. I'll do that, if no one protests. JoergenB 17:00, 6 October 2006 (UTC)

[edit] Ramsey's original theorems

I found Ramsey's original article in our library. Indeed, it concerns a logical problem; and the combinatorial results which have an independent interest (an understatement!!!) actually start with the infinitive version, and (in modern terminology) concern hypergraph variants. In other words, Ramsey considers colourings of all subsets of a fixed size r (where r = 2 corresponds to the common case of ordinary graphs. I think I'll add a few references to the original, and also a brief mention of the hypergraph cases; but I do not think proofs for the latter need to be added. Perhaps we also could have a brief section on the original setting? JoergenB 16:00, 10 October 2006 (UTC)

[edit] A Multicolor Example R(3,3,3)=17

OK, I give up. I just got a new monitor, and see that my section is ugly in the new resolution. How can I get the 2 figures to the right to not overlap with the next section, and not have a big gap in the middle of the section, indepenmdent of the resolution that the user might be using? (I also realize that I have quite a few unsourced statements, and intend to add references to the literature for those assertations in the future when I get the chance.)--Ramsey2006 04:01, 29 November 2006 (UTC)

BTW, I didn't even know that the monochromatic subgraph in a specified color of the good K16's actually had a name until I ran across the picture of the Clebsch graph in the gallery of graphs with names page. (I always thought that it was beautiful enough to deserve a name.) Good work, guys!--Ramsey2006 04:01, 29 November 2006 (UTC)

[edit] Colour, not color

I notice that the latest edit was a change of the spelling 'colour' to 'color' at one instance; and further inspection showed that the spelling is inconsistent. This is a rather minor matter; and there exists a consensus on a very simple rule to decide the matter: follow the original contributor's preference. This article was started with the British spelling, whence 'colour', not 'color' should be used everywhere. (I wish all edit questions had as simple answers!))

A closer check revealed 59 'colour' and 34 'color' in the article. I now have changed all 34 'color' to 'colour'.--JoergenB 15:55, 1 December 2006 (UTC)

Thanks! -- Dominus 16:15, 1 December 2006 (UTC)

Thanks! I didn't even think to check when I added my section (which accounted for 31 of the 34 "colors"). The "colour" version is definately the cooler of the two!  ;o} --Ramsey2006 17:40, 1 December 2006 (UTC)