Talk:Ramsey's theorem

The intro

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.wiki.x.io/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 —Preceding undated comment added 22:59, 27 March 2013 (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)

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[3] 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). [4] 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)

In my humble opinion the figure representing the untwisted graph is wrong: it is not complete. The top vertex, for instance, is not connected to the bottom right vertex. But it is connected twice (with a red and a blue edge) to the first vertex to the bottom right of the center. --Renaud Pacalet (talk) 06:35, 17 May 2022 (UTC)

The untwisted graph looks correct to me. The top vertex is connected by a blue straight line to the bottom right vertex. But the twisted graph looks like it has a similar issue to the one you're describing. The three vertices closest to the center do not seem to be connected, nor do the three vertices farthest from the center. Meanwhile, there are multiple edges between two vertices in various places. In particular, the top vertex is connected to the closest vertex below and to the right of the center with a red and a blue edge, just like you describe. Are you sure you were looking at the untwisted graph? I would agree with this if it were about the twisted graph. 144.51.12.2 (talk) 14:56, 27 April 2023 (UTC)

Hello, new potential "editor" here, I think there is a typo in that the first para shows that any complete graph with no monochromatic triangle can have at MOST 16 vertices and this surely implies that R(3.3.3) is at MOST 17 rather than at least 17 as stated. That's why it is sufficient to construct a 16-vertex non-monochromatic-triangle-containing complete graph to narrow it down to 17 exactly. but please re-edit and reply here if I have made some elementary error! and sorry if i have broken some rule or other.

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)

Proof of infinite version

The proof given for the infinite case for two colours actually works for any number of colours with just a tiny modification to the discussion of the base case. Also the proof is an ordinary induction not a complete induction. To give the more general proof, change the first five sentences of the proof to read:

The proof is by induction on n, the size of the subsets. For n = 1,the statement is equivalent to saying that if you split an infinite set into a finite number of sets, one of them is infinite. This is evident.

Then change "2-colouring" to "c-colouring" throughout the rest of the proof.

Arjayay asked for a reference: e.g., see these notes by Martin Gould.

Bandanna (talk) 20:54, 6 October 2014 (UTC)

Not done: as you have not cited reliable sources to back up your request, without which no information should be added to, or changed in, any article. - Arjayay (talk) 12:27, 7 October 2014 (UTC)

Bandanna (talk) 16:13, 7 October 2014 (UTC)

Bandanna (talk) 05:25, 8 October 2014 (UTC)

Not done: The page's protection level and/or your user rights have changed since this request was placed. You should now be able to edit the page yourself. If you still seem to be unable to, please reopen the request with further details. Stickee (talk) 00:16, 9 November 2014 (UTC)

Applications and reason why these numbers have any importance

There should be a section on applications. Dr. Universe (talk) 03:19, 27 April 2015 (UTC)

R(4,3,3) = 30

The article

showed R(4,3,3) = 30, so that information should be updated. And the statement

 "A multicolour Ramsey number is a Ramsey number using 3 or more colours. There is only one non-trivial multicolour Ramsey number for which the exact value is known, namely R(3, 3, 3) = 17."

should also be updated.

Oliver Kullmann (talk) 03:52, 2 October 2016 (UTC)

This is a primary source and when the result makes it into reliable secondary sources we shall update the article. Wikipedia is an encyclopedia and not a place to announce new results. Bill Cherowitzo (talk) 04:37, 2 October 2016 (UTC)

I don't believe this is a correct summary of the rules. There is no policy against using primary sources in articles. McKay (talk) 02:05, 27 January 2017 (UTC)

I agree with McKay. In articles concerning mathematics, referring to published results in journals of good standing (adhering to efficient peer's reviewing) seems to be generally acceptable. JoergenB (talk) 21:56, 22 April 2017 (UTC)

New lower bounds on small Ramsey numbers

The table was completely out of date. Added: R(4,8)>=59;R(5,9)>=133;R(5,10)>=149;R(6,7)>=115;R(6,8)>=134;R(6,9)>=183;R(6,10)>=204; R(7,9)>=252;R(7,10)>=292;R(8,9)>=329;R(8,10)>=343 from the two sources: https://arxiv.org/abs/1504.02403 and https://arxiv.org/abs/1505.07186 . Obngfs (talk) 19:34, 25 January 2017 (UTC)

Arxiv papers are not a reliable source. When these results make it into the secondary literature we will report on them.--Bill Cherowitzo (talk) 21:10, 25 January 2017 (UTC)

Pretty unfriendly step, note that for example the listed lisp code at the external notes section is also NOT(!!!) published on a peer-review book. Not speaking about the fact that you can check the listed colorings with a shorter code what is the listed lisp code. Obviously only in the case if you have a very basic understanding of Math and programming. Obngfs (talk) 21:28, 25 January 2017 (UTC)

At least one paper was published in The Electronic Journal of Combinatorics in 2015, and if cited to that source, it can be included. —Mark Dominus (talk) 21:36, 25 January 2017 (UTC)

I have added the results from the first paper, Exoo and Tatarevic (2015), with appropriate citations. The other paper (Kuznetzov) does not appear to have been published in a peer-reviewed journal. —Mark Dominus (talk) 21:53, 25 January 2017 (UTC)

The Kuznetsov paper appears at http://www.oalib.com/paper/4074937#.WIkjEme2prl but I am not sure that the OALib Journal is considered a reliable source. —Mark Dominus (talk) 22:18, 25 January 2017 (UTC)

Thanks for tracking that down. I have no problems with the EJC article but I am also uncertain about the reliability of OALib Journal. I can be a bit flexible about secondary sources if something has been reliably published and has been out there for a while, but Arxiv papers, even by well known authors, do not cut it. --Bill Cherowitzo (talk) 23:11, 25 January 2017 (UTC)

I'm glad to help. I agree that arXiv papers aren't normally considered reliable sources, since they are not subject to peer review. —Mark Dominus (talk) 01:38, 26 January 2017 (UTC)

Radziszowski's survey has been updated. (The last update was in January 2014.) Thanks to the anonymous editor for incorporating changes here. There may be further changes that should be incorporated. —Mark Dominus (talk) 18:44, 5 March 2017 (UTC)

Complexity issues, and a dubious quantum computing comparison.

There was a new section Ramsey's theorem#Ramsey computation and quantum computers added fairly recently. It contains inter alia the following:

Ramsey numbers can be determined by some universal quantum computers. The decision question is solved by determining whether the probe qubit exhibits resonance dynamics.

This rather vague formulation was supported by this arXiv article. Now, I am not as sceptical to employing arXiv stuff written by acknowledged experts in the field (as Exoo or McKay) as some others tend to be, but in this case there are some extra reasons to be careful.

1. The claim implicitly gives the impression that (classical) Ramsey numbers could not be determined by conventional computer technique, but could be by quantum computers. However, each Ramsey number is determinable by a finite "brute force" process, where all graph edge colourings of the complete graph order of the potential Ramsey numbers are inspected. The reason that this is not practically feasible is that that number very quickly get much too large. Thus, the "brute force" calculation has a theoretical interest, but no practical one whatsoever. (Cf. McKay's comments in #incorrect claims supra.) With only the "brute force" method available, we nowadays could prove that R(3,4)=9; we might consider an enormous effort in order to prove that R(3,5)=14; but proving R(3,6)=18 would seem to be completely inaccessible with our contemporary hardware. However, there is no "fixed boundary" between what could or could not be calculated, neither for the "brute force" method, nor for the methods actually used.
2. The aforementioned arXiv article treats the "brute force" method as if it were the only possible one, and then goes on to claim that quantum computing would yield a considerable improvement over this (rather useless) method. In fact, the author (Hefeng Wang) misleadingly writes:
   "A total number of $2^{n(n-1)/2}$ different graphs can be formed by n vertices. To determine whether n is the Ramsey number $R(x,y)$, one has to check all the $2^{n(n-1)/2}$ graphs, which grows superexponentially with n, and the task quickly becomes intractable." (my boldface emphasis)
   Wang then goes on to discuss how to inspect all these graphs by quantum techniques, and claims that "the algorithm shows a quadratic speedup over its classical counterparts". (I'm not sure precisely what "a quadratic speedup" is supposed to mean.) However, even if that claim is correct, that would not make Wang's algorithm better than the presently used algorithms. In fact, a "quadratic speedup" of the extremely impossible "brute force" method still would be very much slower than the present-day methods.

Now, I'm not saying that Wang's work is uninteresting. I cannot understand their explanations (since I know practically nothing about quantum computing); but I note that they give references to a physicist article, where they claim that a not as good quantum computing algorithm for calculating Ramsey numbers was given. It is possible that "brute force" calculation of Ramsey numbers has become or will become some kind of benchmark for quantum computing. This means that Wang's article might contribute to the development of that technique, although it seems to have no bearing at all on the actual calculation of the $R(m,n)$. Also, such a use as "benchmarks" could be worth mentioning in our article.

In view of this, and of the previous discussion over the mentioning of "brute force" in the section Ramsey's theorem#Ramsey numbers, I propose the following:

1. Retain a Ramsey computation section, but rewrite it.
2. Move the discussion of the "brute force" method to this section. (Since it has no connection at all with either present or historical calculations of Ramsey numbers, it is irrelevant in the Ramsey numbers section.)
3. If some published work suggesting quantum computing methods for effectivising the "brute force" method can be found, then the material about such methods should be retained, but rewritten (with an emphasis of the importance for quantum computing rather than for Ramsey number calculation).
4. A few sentences about the actually used methods for calculating concrete bounds on Ramsey numbers should be added. JoergenB (talk) 21:46, 22 April 2017 (UTC)

---

FYI, you might be tickled to know that one of the games being played in computational complexity is the question: "what is the fastest classical (i.e. non-quantum, ordinary turning machine) algorithm that accurately simulates a quantum algorithm to within epsilon?" It turns out that various quantum systems can be simulated very efficiently.

More generally, quantum computing is a special case of applying a sequence of transformations to some geometric manifold, such as (for example) the manifold of a Lie group or a homogenous space, and then watching how a distribution on that manifold evolves as the transformations are applied. The test function for determining if a computation has stopped can be taken to be "is some of the distribution localized in some particular shape?" You can view this as a coloring problem: you color the manifold in N different colors, apply a sequence of transformations, and then ask where the colors went to. This is sort-of-ish like the infinite Ramsey theorem. For quantum computing with n qubits, this is just the complex projective space CP^n and the quantum operators are just misc unitary transforms applied to it. So, now think of trying to simulate this (infinitely smooth) manifold by a discrete set of K points (so now the unitary transforms are replaced by discrete actions on a complete graph of K vertexes). Its perhaps not surprising that elegant algos exist that outperform brute-force. The question is then whether this is always the case. Personally, I would not be surprised if the answer was "yes": viz, a quantum computer can never outperform a classical computer (after dealing with the fact that working with smooth manifolds is kind-of-like computing with inifinite-precision numbers). It just behaves differently, and makes accessible different kinds of answers. 67.198.37.17 (talk) 15:39, 2 August 2017 (UTC)

Remove D-wave advertising

I'm removing the following from the article:

The D-Wave Systems quantum computer can be tasked to perform Ramsey calculations at quantum speeds. Whereas in a universal quantum computer qubits represent numbers and involve error correction; this is not an issue for the D Wave quantum computer, as its qubits are not quantum numbers being calculated on to, rather the qubit outcomes represent sets of probabilities. Said another way, this is unlike circuit quantum computers, where there are single operations such as a CNOT (controlled not, the fundamental logic operation in quantum computing) -- instead, the D wave quantum computer solution to a problem is re-configured so that it is the ground state of an energy landscape.

From what I can tell, this is nothing more than an advertisement for D-wave, and the only thing it appears to be doing is attempting to explain, badly and incoherently, how quantum computing works, without saying anything at all about Ramsey theory. 67.198.37.17 (talk) 14:52, 2 August 2017 (UTC)

Missing treatment of connection to logic

Missing from this article is any mention that the Ramsey theorem is a topic of research in reverse mathematics. That article mentions this; the converse is appropriate; I suspect that the topic needs it's entire own article, but even a short paragraph here explaining the relationship to logic would be appropriate. Specifically, something that goes beyond the pop lit of https://www.quantamagazine.org/mathematicians-bridge-finite-infinite-divide-20160524 or at least something that condenses/elaborates on https://www3.nd.edu/~cholak/papers/tarragona.pdf or http://www.math.nus.edu.sg/~chongct/paper-ams.pdf etc... 67.198.37.17 (talk) 15:29, 2 August 2017 (UTC)

This is not how to write clearly

The first sentence is as follows:

"In combinatorial mathematics, Ramsey's theorem states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph."

This is not how to write clearly. In fact, this arrangement of subject, verb, and object may be the least clear arrangement possible for this sentence.

Do not speak about "edge labelling" and "monochromatic cliques" before the sentence has even mentioned what it is about: graph coloring.

If you pile too many long or uncommon words together in one sentence, anyone unfamiliar with the subject will remain that way.2600:1700:E1C0:F340:8126:6034:4657:3B3F (talk) 20:17, 15 August 2018 (UTC)

It would be more useful if you suggested a better sentence (which I agree is desirable). McKay (talk) 04:12, 16 August 2018 (UTC)

Explanation for undo better lower bound R(t,l)

I undid the contribution of 15 October 2020. It was suggested that by a recent paper of Conlon and Ferber (https://arxiv.org/pdf/2009.10458.pdf), a much better lower bound on the Ramsey number R(t,l) exists. However, in their paper the notation r(t;l) does not stand for the Ramsey number R(t,l). Rather, their r(t;l) stands for the multicolor Ramsey number R(t,t,...,t), with l indices. So the cited paper is very nice, but proves something different. Wikiwiswa (talk) 22:35, 28 October 2020 (UTC)

Thanks for correcting my mistake. —Mark Dominus (talk) 15:54, 29 October 2020 (UTC)

A possible exponential improvement (not yet peer-reviewed)

https://arxiv.org/pdf/2303.09521.pdf

A smaller improvement reported at https://www.nieuwarchief.nl/serie5/pdf/naw5-2020-21-4-232.pdf — Preceding unsigned comment added by 38.140.143.234 (talk) 21:26, 31 March 2023 (UTC)

Why not a simple picture that shows a red or blue clique?

I found this page very hard to understand, especially on first reading. Something that I think would help is a simple picture / sketch (like the one included for K5 that shows no clique) -- show K6 and one example of a (red or blue) clique. Yes, I know there are a lot of possible different arrangements that will produce different specific cliques, so say that in the caption.

Rhkramer (talk) 02:26, 6 May 2023 (UTC)

Obergrenze von R(10,10)

Die Obergrenze von R(10,10) in der Tabelle ist falsch, da schon Erdös bewiesen hat das R höchstens r^4 sein kann ! 80.187.119.226 (talk) 13:45, 14 January 2024 (UTC)

Section "Infinite version implies the finite"

The section Ramsey's theorem#Infinite version implies the finite makes use of the notation [k]⁽ⁿ⁾, but as far as I can see, that notation is not defined anywhere in the article. Someone should add the meaning of the notation. PatrickR2 (talk) 06:46, 1 March 2024 (UTC)

The K16 graph on the right is incorrect

At the very least, the vertex closest to the centre in the blue section has NO lines connecting it with the vertices closest to the centre in the red and green sections and 2 lines connecting it to the vertices farthest from the centre in these sections. Please correct this graph and re-upload. In related news, I managed to create a graph that proves that R(3,3,3) is indeed, in fact, 17 and not just more than 16. What software was used to create these graphs? I'd love to upload the K17 graph based on the left K16 image, but the only graphical software I have right now is MSPaint. 24.69.168.156 (talk) 06:16, 13 November 2024 (UTC)