Talk:Ramsey's theorem

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)

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)

Yes, Greg, what you say is correct, so there is no "error", per se, in the graph. However, it is nonetheless confusing. I kept looking at the graph & at the text, wondering why an example that starts with the statement regarding 6 vertices then gives as an accompanying graph an object with only 5 vertices. So it is not incorrect in any technical sense, but the graph does not act as a useful tool to educate the reader. this.is.mvw March 27, 2013

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)

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)

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)

for a citation: the documentary about Erdos ("N is a number" http://www.imdb.com/title/tt0125425/) has Erdos himself recounting the alien story. —Preceding unsigned comment added by 72.95.237.151 (talk) 09:09, 30 March 2009 (UTC)

;(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 $R(3,4,5,6)\,$; but if you want to guarantee a triangle in any of the triangles, you may write $R_{4}(3)\,$ as an alternative to $R(3,3,3,3)\,$. 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 $R(3;4)\,$ or even $R(3,4)\,$ for $R(3,3,3,3)\,$, a long time ago. However, I don't recall having seen an irredundancy like $R(3,3,3,3;4)\,$; 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 $R(n_{1},\ldots ,n_{r};s)$ 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:

$R_{3}(3)=R(3,3,3)=R(3,3,3;2)=17\,$

(from section 5 Multicolor graph numbers, of the latest edition of the dynamic survey). To repeat: here $R(3,3,3;2)\,$ 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)

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)

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)

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)

need picture for Friendship theorem

There is also an article on the Friendship theorem. That theorem is simply the fact that R(3,3)=6. That article should have a picture of the 2-coloring of $K_{5}$ with no monochromatic triangle (i.e. blue star inscribed in red pentagon). I am happy to draw the picture, but there is already a nice one in this article. Can I copy this picture to that article? What is the wiki policy for such a case? If it were a photo, I would be likely to find a new one because the new one would give more breadth. However, in this case, a second drawing would not offer any more information than the first one. Thoughts? Ptrillian 01:41, 6 January 2007 (UTC)

You can use the same pictures. It is under the GDFL copyleft. --Ramsey2006 15:24, 6 January 2007 (UTC)

I didn't mean, is it illegal to use the pictures. I meant, is it frowned upon by the community at wikipedia to use the same pictures in multiple articles within wikipedia? Possibly the answer is still, "no", but I want to make clear which question I'm asking.Ptrillian 05:49, 7 January 2007 (UTC)

No it is fine. If a picture would be a good addition to several different articles, by all means use it. McKay 00:45, 9 January 2007 (UTC)

R(3,10) and R(10,3)

A couple of months ago an anonymous user made a small but heavy edit. 67.174.183.183 (talk · contribs) changed the tabulated estimate of R(3,10), with the following comment in the history:

→Ramsey numbers - According to OEIS this is either 40 or 41

(See the revision 22 december 2006, 02:55:18, in the history.) I don't know what OEIS means. I would very much appreciate a reference for the improvement (it is not in Radziszowsky's dynamic survey), and I think the reference should be added to the wikipedia article, too; together with an update of the R(10,3) estimate. All this under the exciting assumption that this is correct; if not, of course the old R(3,10) estimate should be restored. (In either case, I think the probability for $R(3,10)\neq R(10,3)$ to hold is rather low :-). JoergenB 18:59, 13 February 2007 (UTC)

OEIS is OEIS. -- Dominus 22:21, 13 February 2007 (UTC)

here is the OEIS entry for R(3,n), including the comment "The next term is known to be 40 or 41." Nothing in the list of references seems promising, except perhaps for "B. D. McKay, personal communication." -- Dominus 22:26, 13 February 2007 (UTC)

Thanks, Dominus, I've furthered the question to Sloane. (Moreover, McKay, if the result is yours, please tell us! Of course this would be 'original research' in the very best sense, but would you have e.g. an arxive entry...?)--JoergenB 11:11, 14 February 2007 (UTC)

I'm slightly confused; Neil Sloane thought he got the new estimate from our article! I don't know; but the few other edits that 67.174.183.183 (talk · contribs) made seemed all to be rather sensible, so I think that OEIS was changed before the 22 December. (But, could there have been an old, undocumented and reverted edit in our article?) JoergenB 16:28, 14 February 2007 (UTC)

Well. Seemingly Sloane changes the upper limit back to 43; we do the same; whenever anyone (McKay?) finds a source for a lower limit, they change it and inform the other party. Is this OK? JoergenB 18:03, 14 February 2007 (UTC)

Infinite implies finite

The argument given proves but does not refer to König's infinity lemma. Kope 15:21, 13 May 2007 (UTC)

Non graph theory version

The article does not include any reference to the arrows version of Ramsey's theorem. It is important because it gives a simple understanding of the theorem from a non-graphical point of view. (In the arrows notation the Theorem on friends and strangers is $6\longrightarrow (3)_{2}$ ). The arrows notation also gives a trivial proof of Schur's theorem. The arrows version should be included in the article. I plan to do it soon. Cheers--Shahab 11:00, 18 May 2007 (UTC)

The arrow notation should be used in partition calculus to describe the Erdos-Dushnik-Miller theorem, the Erdos-Rado theorem, and other generalizations of Ramsey's theorem. Incidentally, I think, but I am not sure, that Ramsey proved the infinite version of his theorem, the finite version was discovered and proved by Paul Erdős and George Szekeres a few years later.Kope 14:13, 19 May 2007 (UTC)

Technicality

In the part "(that is a simple graph, where an edge connects every pair of vertices)" at the beginning of the article the quantifiers should be altered. It should read "(that is a simple graph, where every pair of vertices is connected by an edge)". The difference is logically relevant. —Preceding unsigned comment added by 129.132.189.181 (talk) 08:08, 5 September 2007 (UTC)

Intro text

What is $r$ in $R(r,s)$? s denotes the size of the complete monochromatic subgraph, and R(r,s) is the size of the whole graph. But what is r? It should be stated in the intro text. Paxinum (talk) 08:47, 17 March 2008 (UTC)

It says: "such that ... there exists either a complete subgraph on r vertices which is entirely blue, or ...". -- Dominus (talk) 13:18, 17 March 2008 (UTC)

wrong citation

According to the book : The man who only loved numbers, (page 53) Erdos quote about R(5,5) is related to a evil spirt not aliens. Stdazi (talk) 15:01, 1 August 2008 (UTC)

My mistake, heh, should have looked here before editing. Sorry. Stdazi (talk) 15:04, 1 August 2008 (UTC)

I don't get it. This is an original Erdos paper and it uses evil spirit, doesn't it? Kope (talk) 15:11, 1 August 2008 (UTC)

From the above talk, it seems like he used both Stdazi (talk) 20:08, 1 August 2008 (UTC)

I humbly disagree: from his papers it seems that he used "evil spirit" and not aliens. You can search the collection at the Renyi Institute. Kope (talk) 05:48, 2 August 2008 (UTC)

I'd like to use the word spirit too, though Wikiquote uses aliens too : http://en.wikiquote.org/wiki/Paul_Erdős Stdazi (talk) 14:39, 2 August 2008 (UTC)

This is a very personal remark. When I read the Wikiquote quotation I don't "hear" Paul. This is probably not a word-by-word quote, it is probaly formulated by Ron (Erdos's style is different). I will ask him tomorrow. But in any case, both formulations should be OK, as they are very close to each other, and the idea is the same. Kope (talk) 15:10, 4 August 2008 (UTC)

Proof for 2 colors

The section on Proof of Ramsey's Theorem for 2 colors contains the following sentence:

Now |M| ≥ R(r − 1, s) or |N| ≥ R(r, s − 1), again by the pigeonhole principle.

Can someone please explain how the inequalities follows from the pigeonhole principle. Thanks--Shahab (talk) 04:44, 6 August 2008 (UTC)

John Mackey (mathematician)

This article is now up for deletion, but it includes: His [Mackey's] main contributions to mathematics have been his discoveries of many new bounds for Ramsey numbers. In 1994 he discovered new bounds for R(6, 6) through R(10, 10), and proved that 41 ≤ R(5, 5) ≤ 55, at the time a great feat. He later reduced the upper bound to 50. To this day he believes R(5, 5) = 43. Mackey is an adjunct IIRC, at Carnegie-Mellon.

I mention this here in case he should be noted in the history of the problem. Septentrionalis PMAnderson 18:02, 18 November 2008 (UTC)

New upper bound

A new upper bound for diagonal Ramsey numbers. I'm putting this here as a reminder to myself to put it in, but if anyone else wants to add it instead, I hope they will go ahead. —Dominus (talk) 12:39, 31 October 2009 (UTC)

Unwarranted emphasis

This page has a very strong emphasis on the specifics of small Ramsey numbers. No mention is made of the many interesting asymptotic aspects of the field. The most important omitted results are Erdos' lower bound that $r(n)\geq 2^{n/2}$ and the Erdos-Szekeres upper bound, that $r(n)\leq {\binom {2n-2}{n-1}}\leq 4^{n}/{\sqrt {n}}$. The discussion on off-diagonal numbers could easily be extended beyond just $r(3,n)$. Finally, some quantitative aspects of the theory for hypergraphs could be mentioned, for example, the important work of Erdos, Hajnal and Rado on the subject. —Preceding unsigned comment added by Busy365 (talk • contribs) 18:06, 7 September 2010 (UTC)

I have a formula for Ramsey Numbers

n >2, R(n,n)= 2*(2^n -2*n +1), since 43 <=R(5,5) <=49; it can't be odd... 43, 45, 47, or 49, and neither 44 nor 48-- both equal to 2*(even); for n=3 & 4, it's R(n,n)= 2*(odd), so R(5,5)= 2*23= 46, and check to see that R(6,6)= 2*53= 106 is barely inside the next range. I have posted a *proof* for this formula on my website... www.oddperfectnumbers.com; just click on the Ramsey Theory page!

This is not a place to post your original research or advertise your web page. McKay (talk) 06:11, 10 November 2011 (UTC)

incorrect claims

I deleted this:

Using contemporary computational technology, it would take on the order of 10²⁵⁰ years to exhaust all possible 2-colourings of graphs of size 43. (However, many of these colourings are isomorphic to each other, and an intelligent algorithm that only checks unique colourings could get the task done in as little as 10²²⁰ years.) Brute-force enumeration ceases to be practical much earlier: the number of unique 2-colourings of a graph on 18 nodes is already an intractable 1.788*10³⁰.

The main reason is that it is simply not true. Nobody would try to look at all possible colourings one at a time as there are much better ways. Looking at all colourings is not possible for graphs of size greater than 13 (and very expensive for size 13), yet many larger Ramsey numbers can be found exactly via computer search. In other words, this type of calculation does not correctly indicate the difficulty of searching. A secondary reason is that blogs are not permitted as sources in Wikipedia, see WP:BLOGS. McKay (talk) 02:54, 13 March 2012 (UTC)

I replaced this:

Searching all colourings of a graph K_n becomes computationally extremely difficult as n increases; the number of colourings grows super-exponentially. The complexity for searching all possible graphs is O(2^(n-1)(n-2)/2) for an upper bound of n nodes.

for the same reason. McKay (talk) 02:57, 13 March 2012 (UTC)

Tournament Ramsey numbers (revisited)

I restored the end of the section Ramsey's theorem#Directed graph Ramsey numbers. It was removed as 'vandalism', probably in good faith; the reference to aliens is incomprehensible, if you missed the Erdős R(5,5) and R(6,6) story.

This means that the who? tag also got restored. Now, this section was mainly written here, from an IP where no uninlogged editing has been done since 2006. The IP provided no direct references, but on the other hand added an external link: Partial Answer to Puzzle #27: A Ramsey-like quantity, "by Warren D. Smith with extra contributions/improvements by Geoff Exoo".

The stuff sounds interesting, and worth its own article. The fact that seemingly its relation to ordered subsets in preference patterns attracted the interest of some guys advocating an electional reform doesn't make it less interesting. If Smith or Exoo or any other who knows more about this subject would like to make a stand-alone article, I'd appreciate it. (We then could refer to this as the main article for the section in the Ramsey theory article.) I surmise that the tables I found following the external links supra are due to Exoo, but I didn't refind them on his page.

I cannot exclude that an article about these digraph Ramsey numbers already is written somewhere - under a similar or a quite different name. However, I found none in Category:Ramsey theory or in Category:Extremal graph theory, and I don't know where else to look. JoergenB (talk) 22:51, 26 November 2012 (UTC)

Bounding

I was trying to upper-bound R(10,10) by formula in article, however, log(log(10)) = 0, and division by 0 = infinity. In in cases s<10, it works normally, but at s=10 it is 0. Why it doesn't work? 31.42.239.14 (talk) 12:30, 18 January 2013 (UTC)

log means natural logarithm, i.e. log base e.—GraemeMcRae^talk 17:55, 20 January 2013 (UTC)

Thanks. 31.42.239.14 (talk) 09:42, 26 January 2013 (UTC)