text:
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.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 —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 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). 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. 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 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 10250 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 10220 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*1030.

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 Kn 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. 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.—GraemeMcRaetalk 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)

 * Red information icon with gradient background.svg 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)
 * Padlock-silver-open.svg 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 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  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, 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 makes use of the notation $[k](n)$, 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)

title: Talk:Ramsey's theorem


text:
Hypergraphia

Hypergraphia is a behavioral condition characterized by the intense desire to write or draw. Forms of hypergraphia can vary in writing style and content. It is a symptom associated with temporal lobe changes in epilepsy and in Geschwind syndrome. Structures that may have an effect on hypergraphia when damaged due to temporal lobe epilepsy are the hippocampus and Wernicke's area. Aside from temporal lobe epilepsy, chemical causes may be responsible for inducing hypergraphia.

Writing style
American neurologists Stephen Waxman and Norman Geschwind were the first to describe hypergraphia, in the 1970s. The patients they observed displayed highly compulsive detailed writing, sometimes with literary creativity. The patients kept diaries, which some used to meticulously document minute details of their everyday activities, write poetry, or create lists. Case 1 of their study wrote lists of her relatives, her likes and dislikes, and the furniture in her apartment. Beside lists, the patient wrote poetry, often with a moral or philosophical undertone. She described an incident in which she wrote the lyrics of a song she learned when she was 17 several hundred times and another incident in which she felt the urge to write a word over and over again. Another patient wrote aphorisms and certain sentences in repetition.

A patient from a separate study experienced continuous "rhyming in his head" for five years after a seizure and said that he "felt the need to write them down." The patient did not talk in rhyme, nor did he read poetry. Language capacity and mental status were normal for this patient, except for recorded right-temporal spikes on electroencephalograms. This patient had right-hemisphere epilepsy. Functional MRI scans of other studies suggest that rhyming behavior is produced in the left hemisphere, but Mendez proposed that postictal hypoactivity of the right hemisphere may induce a release of writing and rhyming abilities in the left hemisphere.

Content

In addition to writing in different forms (poetry, books, repetition of one word), hypergraphia patients differ in the complexity of their writings. While some writers (e.g. Alice Flaherty and Dyane Harwood ) use their hypergraphia to help them write extensive papers and books, most patients do not write things of substance. Flaherty describes hypergraphia as a result of decreased temporal lobe function which disinhibits frontal lobe idea and language generation, "sometimes at the expense of quality." Patients hospitalized with temporal lobe epilepsy and other disorders causing hypergraphia have written memos and lists (like their favorite songs) and recorded their dreams in extreme length and detail.

There are many accounts of patients writing in nonsensical patterns including writing in a center-seeking spiral starting around the edges of a piece of paper. In one case study, a patient even wrote backward, so that the writing could only be interpreted with the aid of a mirror. Sometimes the writing can consist of scribbles and frantic, random thoughts that are quickly jotted down on paper very frequently. Grammar can be present, but the meaning of these thoughts is generally hard to grasp and the sentences are loose. In some cases, patients write extremely detailed accounts of events that are occurring or descriptions of where they are.

In some cases, hypergraphia can manifest with compulsive drawing. The composer Robert Schumann, during periods of high musical output, also wrote many long letters to his sister Clara; similarly, Vincent van Gogh had much more written correspondence during bouts of intense painting. Many drawings by patients with hypergraphia exhibit repetition and a high level of detail, sometimes mixing both compulsive writing and drawing together.

Causes
Some studies have suggested that hypergraphia is related to bipolar disorder, hypomania, and schizophrenia. Although creative ability was observed in the patients of these studies, signs of creativity were observed, not hypergraphia specifically. Therefore, it is difficult to say with absolute certainty that hypergraphia is a symptom of these psychiatric illnesses because creativity in patients with bipolar disorder, hypomania, or schizophrenia may manifest into something aside from writing. However, other studies have shown significant accounts between hypergraphia and temporal lobe epilepsy and chemical causes.

Temporal lobe epilepsy
Hypergraphia was first studied as a symptom of temporal lobe epilepsy, a condition of reoccurring seizures caused by excessive neuronal activity, but it is not a common symptom among patients. Less than 10 percent of patients with temporal lobe epilepsy exhibit characteristics of hypergraphia. Temporal lobe epilepsy patients may exhibit irritability, discomfort, or an increasing feeling of dread if their writing activity is disrupted. To elicit such responses when interrupting their writing suggests that hypergraphia is a compulsive condition, resulting in an obsessive motivation to write. A temporal lobe epilepsy may influence frontotemporal connections in such a way that the drive to write is increased in the frontal lobe, beginning with the prefrontal and premotor cortex planning out what to write, and then leading to the motor cortex (located next to the central fissure) executing the physical movement of writing.

Most temporal lobe epilepsy patients who suffer from hypergraphia can write words, but not all may have the capacity to write complete sentences that have meaning.

Bipolar disorder
The disorder most often associated with high-output writers is bipolar disorder, especially during hypomania. In fact, temporal lobe epilepsy is more likely to produce hypergraphia if it also produces manic symptoms. While depression has been linked to increased writing, it appears that most writers with depression write little while depressed, and high output periods correspond to rebound mood elevation after the end of a depression, or in mixed mood states.

Chemicals
Drugs that boost mood and energy have been known to induce hypergraphia, possibly by increasing activity in brain networks utilizing one of the body's neurotransmitters, dopamine. Dopamine has been known to decrease latent inhibition, which causes a decrease in the ability to habituate to screen out unexpected stimuli. Low latent inhibition leads to an excessive level of stimulation and could contribute to the onset of hypergraphia and general creativity. This research implies that there is a direct correlation between the levels of dopamine between neuronal synapses and the level of creativity exhibited by the patient. Dopamine agonists increase the levels of dopamine between synapses which results in higher levels of creativity, and the opposite is true for dopamine antagonists.

In one case study, a patient taking donepezil reported an elevation in mood and energy levels which led to hypergraphia and other excessive forms of speech (such as singing). Six other cases of patients taking donepezil and experiencing mania have been previously reported. These patients also had cases of dementia, cognitive impairment from a cerebral aneurysm, bipolar I disorder, and/or depression. Researchers are unsure why donepezil can induce mania and hypergraphia. It could potentially result from an increase in acetylcholine levels, which would have an effect on the other neurotransmitters in the brain.

Pathophysiology
Several regions of the brain are involved in the act of written composition. Handwriting depends on the superior parietal cortex, and motor control areas in the frontal lobe and cerebellum. An area of the frontal lobe that is especially active is Exner's area, located in the premotor cortex. Writing creatively and generating ideas, on the other hand, activates multiple sites in the limbic system and cerebral cortex, including the left inferior frontal gyrus (BA 45) and the left temporal pole (BA 38). Lesions to Wernicke's area (in the left temporal lobe) can increase speech output, which can sometimes manifest itself in writing. In one study, patients with hippocampal atrophy showed signs of having Geschwind syndrome, including hypergraphia. While epilepsy-induced hypergraphia is usually lateralized to the left cerebral hemisphere in the language areas, hypergraphia associated with lesions and other brain damage usually occurs in the right cerebral hemisphere. Lesions to the right side of the brain usually cause hypergraphia because they can disinhibit language function on the left side of the brain. Hypergraphia has also been known to be caused by right hemisphere strokes and tumors.

Society and culture
Hypergraphia was one of the central issues in the 1999 trial of Alvin Ridley for the imprisonment and murder of his wife Virginia Ridley. The mysterious woman, who had died in bed of apparent suffocation, had remained secluded in her home for 27 years in the small town of Ringgold, Georgia, United States. Her 10,000-page journal, which provided abundant evidence that she suffered from epilepsy and had remained housebound of her own will, was instrumental in the acquittal of her husband.

In 1969, Isaac Asimov said "I am a compulsive writer". Other artistic figures reported to have been affected by hypergraphia include Vincent van Gogh, Fyodor Dostoevsky, and Robert Burns. Alice in Wonderland author Lewis Carroll is also said to have had the condition, having written more than 98,000 letters in various formats throughout his life. Some were written backward, in rebus, and in patterns, as with "The Mouse's Tale" in Alice.

Eleanor Alice Burford, whose pen-names included Jean Plaidy, Victoria Holt, Philippa Carr, Eleanor Burford, Elbur Ford, Kathleen Kellow, Anna Percival, and Ellalice Tate, described herself as a compulsive writer.

Naomi Mitchison, often called a doyenne of Scottish literature, writing over 90 books of historical and science fiction, travel writing and autobiography, has been described as a compulsive writer.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Hypergraphia


text:
Oliphant v. Suquamish Indian Tribe

Oliphant v. Suquamish Indian Tribe, 435 U.S. 191 (1978), is a United States Supreme Court case deciding that Indian tribal courts have no criminal jurisdiction over non-Indians. The case was decided on March 6, 1978 with a 6–2 majority. The court opinion was written by William Rehnquist, and a dissenting opinion was written by Thurgood Marshall, who was joined by Chief Justice Warren Burger. Justice William J. Brennan did not participate in the decision.

Congress partially abrogated the Supreme Court's decision by enacting the Violence Against Women Reauthorization Act of 2013, which recognizes the criminal jurisdiction of tribes over non-Indian perpetrators of domestic violence that occur in Indian Country when the victim is Indian.

Background
In August 1973 Mark David Oliphant, a non-Indian living as a permanent resident with the Suquamish Tribe on the Port Madison Indian Reservation in northwestern Washington, was arrested and charged by tribal police with assaulting a tribal officer and resisting arrest during the Suquamish Tribe's Chief Seattle Days. Knowing that thousands of people would gather in a small area for the celebration, the tribe requested Kitsap County and the Bureau of Indian Affairs for additional law enforcement assistance. The county sent just one deputy, and the Bureau of Indian Affairs sent no one. When Oliphant was arrested, at 4:30 a.m., only tribal officers were on duty.

Oliphant applied for a writ of habeas corpus in federal court and claimed he was not subject to tribal authority because he was not Native American. He challenged the exercise of criminal jurisdiction by the tribe over non-Indians.

Procedural history
Oliphant's application for a writ of habeas corpus was rejected by the lower courts. The Ninth Circuit upheld tribal criminal jurisdiction over non-Indians on Indian land because the ability to keep law and order on tribal lands was an important attribute of tribal sovereignty that had been neither surrendered by treaty nor removed by the US Congress under its plenary power over Tribes. Judge Anthony Kennedy, then a judge of the Ninth Circuit Court of Appeals, dissented from the decision and said he found no support for the idea that only treaties and acts of Congress could take away the retained rights of tribes. He considered that doctrine of tribal sovereignty was not "analytically helpful" in resolving the issue.

Ruling
The Supreme Court ruled in Oliphant's favor by holding that Indian tribal courts do not have criminal jurisdiction over non-Indians for conduct occurring on Indian land and reversed the Ninth Circuit's decision. More broadly, the Supreme Court held that Indian tribes cannot exercise powers "expressly terminated by Congress" or "inconsistent with their status" as "domestic dependent nations."

Analyzing the history of Congressional actions related to criminal jurisdiction in Indian Country, the Supreme Court concluded that there was an "unspoken assumption" that tribes lacked criminal jurisdiction over non-Indians. While "not conclusive," the "commonly shared presumption of Congress, the Executive Branch, and lower federal courts that tribal courts do not have the power to try non-Indians carrie[d] considerable weight."

The Court incorporated that presumption into its analysis of the Treaty of Point Elliot, which was silent on the issue of tribal criminal jurisdiction over non-Indians. The Court rejected the Ninth Circuit's approach, which interpreted the treaty's silence in favor of tribal sovereignty and applied the "long-standing rule that legislation affecting the Indians is to be construed in their interest." Instead, the Court revived the doctrine of implicit divestiture. Citing Johnson v. McIntosh and Cherokee Nation v. Georgia, the Court considered criminal jurisdiction over non-Indians an example of the "inherent limitations on tribal powers that stem from their incorporation into the United States," similar to tribes' abrogated rights to alienate land.

By incorporating into the United States, the Court found that Tribes "necessarily [gave] up their power to try non-Indian citizens of the United States except in a manner acceptable to Congress". Arguing that non-Indian citizens should not be subjected to another sovereign's "customs and procedure", the Court analogizes to Crow Dog. In Crow Dog, which was decided before the Major Crimes Act, the Court found exclusive Tribal jurisdiction over Tribe-members because it would be unfair to subject Tribe-members to an "unknown code" imposed by people of a different "race [and] tradition" from their own.

Although the Court found no inherent Tribal criminal jurisdiction, it acknowledged the "prevalence of non-Indian crime on today's reservations which the tribes forcefully argue requires the ability to try non-Indians" and invited "Congress to weigh in" on "whether Indian tribes should finally be authorized to try non-Indians".

Dissenting opinion

Justice Thurgood Marshall dissented. In his view, the right to punish all individuals who commit crimes against tribal law within the reservation was a necessary aspect of the tribe's sovereignty:

"I agree with the court below that the 'power to preserve order on the reservation ... is a sine qua non of the sovereignty that the Suquamish originally possessed.' Oliphant v. Schlie, 544 F.2d 1007, 1009 (CA9 1976). In the absence of affirmative withdrawal by treaty or statute, I am of the view that Indian tribes enjoy, as a necessary aspect of their retained sovereignty, the right to try and punish all persons who commit offenses against tribal law within the reservation. Accordingly, I dissent."

Chief Justice Warren Burger joined the dissenting opinion.

Effects
In 1990 the Supreme Court extended Oliphant to hold that tribes also lacked criminal jurisdiction over Indians who were not members of the tribe, exercising jurisdiction in Duro v. Reina. Within six months, however, Congress abrogated the decision by amending the Indian Civil Rights Act to affirm that tribes had inherent criminal jurisdiction over nonmember Indians. In 2004, the Supreme Court upheld the constitutionality of the legislation in United States v. Lara.

Scholars have extensively criticized Oliphant. According to Professor Bethany Berger, "By patching together bits and pieces of history and isolated quotes from nineteenth century cases, and relegating contrary evidence to footnotes or ignoring it altogether, the majority created a legal basis for denying jurisdiction out of whole cloth." Rather than legal precedent, the holding was "dictated by the Court's assumptions that tribal courts could not fairly exercise jurisdiction over outsiders and that the effort to exercise such jurisdiction was a modern upstart of little importance to tribal concerns." Professor Philip Frickey describes Oliphant, along with the subsequent decisions limiting tribal jurisdiction over non-Indians, as rooted in a "normatively unattractive judicial colonial impulse," and Professor Robert Williams condemns the decision as "legal auto-genocide." According to Dr. Bruce Duthu, the case showed "that the project of imperialism is alive and well in Indian Country and that courts can now get into the action."

"The Oliphant Court essentially elevated a local level conflict between a private citizen and an Indian tribe into a collision of framework interests between two sovereigns, and in the process revived the most negative and destructive aspects of colonialism as it relates to Indian rights. This is a principal reason the decision has attracted so much negative reaction ... Oliphant impact on the development of federal Indian law and life on the ground in Indian Country has been nothing short of revolutionary. The opinion gutted the notion of full territorial sovereignty as it applies to Indian tribes."

Evolution
Congress allowed the tribal courts the right to consider a lawsuit if a non-Indian man commits domestic violence towards a Native American woman on the territory of a Native American tribe by passing Violence Against Women Reauthorization Act of 2013 (VAWA 2013), signed into law on March 7, 2013, by President Barack Obama. It was motivated by the high percentage of Native American women being assaulted by non-Indian men, who felt immune because of the lack of jurisdiction of tribal courts. The new law allowed tribal courts to exercise jurisdiction over non-Indian domestic violence offenders but also imposed other obligations on tribal justice systems, including the requirement for tribes to provide licensed attorneys to defend the non-Indians in tribal court. The new law took effect on March 7, 2015, but also authorized a voluntary "Pilot Project" to allow certain tribes to begin exercising special jurisdiction earlier. On February 6, 2014, three tribes were selected for this Pilot Project: the Pascua Yaqui Tribe (Arizona), the Tulalip Tribes of Washington, and the Confederated Tribes of the Umatilla Indian Reservation (Oregon).

title: Oliphant v. Suquamish Indian Tribe


text:
Nizhnevartovsk

Nizhnevartovsk (Нижневартовск) is a city in Khanty-Mansi Autonomous Okrug–Yugra, Russia. Since the 1960s, the Western Siberian oil boom has led to Nizhnevartovsk's rapid growth from a small settlement to a city due to its location beside the Samotlor oil field along the right bank of the Ob River, 30 km from the border with Tomsk Oblast, and the presence of the petroleum industry has made it one of the wealthiest cities in Russia.

Nizhnevartovsk is one of the few cities in Russia that exceeds the population of the administrative center of its federal subject. Population:

Etymology
The name comes from Nizhnevartovsk suitable for building a Marina area along the Ob river, which bore the name Bartowski Yar (ravine called in the old days, concave, steep Bank of the river), in turn derived from Wartofsky Yurt hunt, known since the second half of the XVIII century. The prefix " nizhne-" is due to the fact that 180 versts (192,02 km) upstream of the Ob river was another Yar with the same name. To distinguish it from it, the new pier was named "Nizhne-Vartovskaya", which later passed to the settlement founded under it.

Geographical location
Nizhnevartovsk is located in the Sredneobskaya lowland of the West Siberian plain in the middle reaches of the Ob river on its right Bank.

Moscow time+2 (Yekaterinburg time)

Nizhnevartovsk, like the entire district, is located in the Moscow time zone+2 (Yekaterinburg time). The offset of the applied time relative to UTC is +5: 00

Hydrology
The main watercourse of the city is the Ob river, from the mouth of the Svitlaya Bayou to the Lokosovskaya Bayou. Within the Nizhnevartovsky district, the section of the middle Ob river is 134 km long and the floodplain is 18 to 20 km wide. By the nature of the water regime, it belongs to the type of rivers with spring and summer floods and floods in the warm period of the year. The duration of the flood is on average 60–130 days. The appearance of ice formations on rivers is typical for the second half of October—early November. The average duration of ice build-up is 180–200 days.

In hydrographic terms, the taiga zone of the Ob river differs sharply from the forest-steppe zone adjacent to it from the South; this difference is primarily due to a change in the ratio of water balance elements. With a noticeable increase in precipitation, with a decrease in their losses to evaporation, surface runoff increases sharply here.

In 2015, the largest flooding of territories adjacent to Nizhnevartovsk in thirty years occurred, including numerous dachas and gardening associations. The reason for the dynamics of water level rise was the climatic features of the spring period.

Climate
Nizhnevartovsk is located in the continental climate zone. The climate is characterized by a long winter, long snow cover (200–210 days), short transitional seasons, late spring and early autumn frosts, short frost-free period (100–110 days), and short summer (10–14 weeks). Winter is characterized by significant inter-day variability in air temperature, the average value of which is 5 °C.

The annual precipitation rate is of the continental type. During the cold period, about 20% of the annual amount falls. Most of them fall in the first months of winter. The maximum annual precipitation falls in the summer months of the year — from June to August. In some years, the amount of precipitation may deviate significantly from the norm. The annual minimum precipitation is observed in February. Snow cover is formed in October—early November, and its descent is observed in late April-early may.

As the entire district is equated to the regions of the Far North.

 * Average annual air temperature: −0.9 °C
 * Relative humidity: 73.7%
 * Average wind speed: 3.1 m/s

Vegetation
In the Nizhnevartovsky district, as well as throughout the entire territory of the Middle Ob region, cedar (people in Russia called "cedar" some species of pine, in this case – Siberian pine) forests are indigenous, and birch and aspen trees that have arisen in their place are derived. The basis of the district's forests is made up of three species: pine, cedar and birch. Among the forest formations, the area is dominated by pine trees. Cedar forests cover less than a quarter of the forested area. A third of the area is occupied by small-leaved forests.

Pine trees are found on sandy and sandy loam strongly podzolic soils and are confined to elevated terrain areas. The most common types are lichen and cranberry pines.

For cedar trees, a good development of the grass-shrub layer is characteristic, in which the dominant value belongs to forest shrubs (blueberries, cranberries, watermelons, marsh bagulnik) and taiga smallgrass (Linnea Severnaya, kislitsa, maynik dvulistnogo). Shrubs are represented by Siberian mountain ash, individual specimens. Green mosses are always present in these forests.

History
Nizhnevartovsk was founded in 1909 (or 1905), built as a service point for merchant steamships operating on the Ob River to acquire stocks of firewood to power their boats. The new village had five homes with a population of eleven people, and was named Nizhnevartovskoye (Нижневартовское), in reference to the Vartovskaya River, a tributary of the Ob located 180 verst downstream. In early 1924, Nizhnevartovsky Selsoviet was formed.

Nizhnevartovsk remained a relatively small settlement until the 1960s when the Soviet authorities began widespread prospecting for the petroleum industry in the Western Siberia region, discovering the Samotlor oil field, one of the largest oil fields in the world, beneath the nearby Lake Samoltor to the north of Nizhnevartovsk. The discovery saw its rapid development and growth from a large village to a boomtown, Komsomol volunteers were brought in from across the country to construct the city, and Nizhnevartovsk's population skyrocketed from 2300 people in 1959 to 15,663 in 1970. Town status was granted to Nizhnevartovsk on March 9, 1972.

Administrative and municipal divisions
Within the framework of administrative divisions, Nizhnevartovsk serves as the administrative center of Nizhnevartovsky District, even though it is not a part of it. As an administrative division, it is incorporated separately as the city of okrug significance of Nizhnevartovsk—an administrative unit with the status equal to that of the districts. As a municipal division, the city of okrug significance of Nizhnevartovsk is incorporated as Nizhnevartovsk Urban Okrug.

Economy
Nizhnevartovsk is the center of the West Siberian oil-producing region and one of the wealthiest cities in the country.

Education
Nizhnevartovsk is home to Nizhnevartovsk State University, a higher education institution with over 5,000 students.

Notable people

 * Ksenia Sukhinova, Miss World 2008

In popular culture
Nizhnevartovsk features prominently in the opening of Tom Clancy's novel Red Storm Rising, which details a hypothetical war between NATO and the Warsaw Pact. In the novel, Nizhnevartovsk is depicted as a significant center for petroleum in the Soviet Union until it is sabotaged, causing a major economic crisis which triggers World War III.

title: Nizhnevartovsk


text:
Ponza

Ponza (Italian: isola di Ponza ) is the largest island of the Italian Pontine Islands archipelago, located 33 km south of Cape Circeo in the Tyrrhenian Sea. It is also the name of the commune of the island, a part of the province of Latina in the Lazio region.

History
The island was inhabited from neolithic through Roman times. According to local legends, Ponza was named after Pontius Pilate, Roman governor of Judea who tried Jesus of Nazareth for sedition against Roman rule. Pontius Pilate's family owned a grotto on Ponza, which is still named after him. The Pontius Pilate legend of Ponza's name has recently come into dispute amongst historians, because the name "Pontia" appears in Strabo's Geography. This pre-dates the birth of Pilate. It is not known if this is the same name as Ponza or a similar name. Also, Pontia means "Land of Bridges" in Latin, a name which could have been applied for Ponza's many naturally occurring arches and bridge-like landforms. Another theory is that the name is of Greek origin, from Greek pontos, πόντος, sea (see also Pontus).

Greek and Roman periods
In ancient times the island was called Tyrrhenia. Legend says that Ponza is what is left of the lost island of Tyrrhenia. Ponza is said to have been connected to the mainland by a narrow strip of land, which sank into the sea with most of the island below the water, with the parts remaining above sea level. The same exact phenomenon happened at Capri. According to legend, there was a large city on the ancient island. There has been significant archaeological progress recently that shows this may be true. For example, it was discovered that the harbor floor of nearby Pozzuoli had sunk and risen several times in the last 5,000 years, revealing sunken Roman temples.

Ponza was first colonised by Etruscans. The island was heavily forested with giant trees in ancient times, but the forest is gone and the hills are covered with man-made terraces. Most of these terraces are no longer being used to grow food and grapes and are falling apart, due to lack of maintenance. The tallest hill on the island, called Monte Guardia, still has the rotting stumps of the extinct giant trees over eight feet wide. Crops are grown on these terraces like grapes for wine and cactus pears and fig trees.

Ponza is also suspected to be the island of Aeaea in Homer's Odyssey, as the island of Circe the sorceress, where her cave or grotto was. Today it is known as Grotta della Maga Circe on the west side of the island, between Capo Bianco and Chiaia di Luna beach. She was said to have lived in this cave in the winter months, spending the summer atop nearby Mount Circe on the mainland of Italy. This is where Circe turned Odysseus' men into animals and cast her spell on and seduced and lived with him for over a year. On the west side of Ponza is the Grotta di Ulisse O Del Sangue, which means Cave of Ulysses or the Blood. The Grotto or cave is almost directly underneath the hill/peninsula called Il Belvedere, which has the Giardino Botanico Ponziano a botanical garden with a villa and the remains of a castle. These caves or grottoes are popular destinations to visit by boat only.

During Roman times, Nero Caesar, eldest brother of Caligula, was deported to Ponza in AD 29, where he was put to death the following year. Two of his sisters, Agrippina the Younger (mother of the emperor Nero) and Julia Livilla, were exiled to Ponza in AD 39 for their complicity in a plot to overthrow Caligula. They were recalled to Rome in AD 41. Julia Livilla had a mansion named Palazzo Giulia (Julia's Palace) built specially for her on Ponza. The ruins are still visible. A similar mansion with the same name was also built on nearby Ventotene for Emperor Augustus' exiled daughter, Julia the Elder.

Middle Ages
Ponza was abandoned during the Middle Ages due to constant raids by Saracens and pirates. In 1552, the Ottoman fleet under the command of Turgut Reis (known as Dragut in the West) defeated the Spanish fleet of Emperor Charles V under the command of the famous Genoese admiral Andrea Doria near Ponza.

1700–present
During the 18th century, the Kingdom of Naples re-colonized the island. In 1813 it was captured by British naval captain Charles Napier during the Napoleonic Wars.

The island became part of the Kingdom of Italy in the mid-19th century and it is now part of the Republic of Italy. The island's isolation destined it to serve as a penal colony by various regimes. During the two decades of fascism, Ponza and nearby Ventotene served as a prison for political opponents of Benito Mussolini's regime. The Ethiopian Prince Regent and military leader, Ras Immiru, who was captured by the Italian Army in 1936, was imprisoned in a house in Santa Maria. Mussolini himself was imprisoned on the island for several weeks after being overthrown and arrested in 1943. Left Communist theorist Amadeo Bordiga was also imprisoned on the island, and he returned after his imprisonment to build several houses.

The island is well known for the tragic story of Lucia Rosa who threw herself into the Tyrrhenian Sea rather than being forced to marry a man against her wishes. She is viewed by many women around the world as a martyr for women's rights and symbol for human rights.

A few years ago, engineers working on an ancient Roman tunnel that connected the harbour part of Ponza to the neighborhood of Santa Maria used explosives to dig a conduit nearby — they were supposed to use a chisel. The explosive shock shattered and destroyed a 2,100-year-old Roman gallery tunnel. The tunnel that connects Ponza with Santa Maria is now repaired, but many residents complain that it does not look like it used to, with steel reinforced concrete in place of Roman bricks.

Today, the island is a tourist attraction with sandy beaches like Chiaia di Luna (Half Moon Beach), now permanently closed due to falling rocks from the huge collapsing cliff above. Several tourists were killed a few years ago while sunbathing on the beach. The Italian National Park Service has installed steel cable netting to prevent further rock falls and deaths. The Roman Galleria or Roman Tunnel that connected the beach to the road is now closed because of collapsing Roman brickwork. Many beaches that were very popular are now permanently closed because falling rocks from overhead cliffs have killed vacationers.

In September of 2007, six "aquanauts" spent two weeks living underwater off the coast of Ponza, breaking all other records.

Geography
Ponza and Gavi are the remains of a caldera rim of an extinct volcano, with a surface area of 7.3 km2. Ponza is approximately 5.5 mi long by 1.5 mi at its widest. It is a crescent shaped island with one large beach called Spiaggia di Chiaia di Luna (Half Moon Beach) and a few small beaches and has a mostly rocky coast made of kaolin and tuff rock. The island has layers of Kaolinite and Bentonite which used to be mined. It has many odd natural rock formations, one looks like a monk, another looks like a giant pair of work pants, Spaccapurpo (Arco Naturale O Spaccapolpi), another looks like a patch of flowers and another one looks like mushrooms, another looks like a horseman. It has the Fantasy Rock Castle and several natural bridges and arches. It also has Faragliones or giant sea stacks made of solid rock. It has several small villages, among them are Commune di Ponza, Santa Maria and Le Forna. Ponza is often confused with nearby islands like Ischia and Capri, except Ponza has no active volcanism.

Climate
Ponza has a mediterranean climate (Köppen Csa) with hot and dry summers combined with mild and rainy winters. The annual average temperature is 17.14 C, the hottest month in August is 25.48 C, and the coldest month is 10.36 C in February. The annual precipitation is 627.21 mm, of which November is the wettest with 116.7 mm, while July is the driest with only 9.13 mm.

Archaeology
The island is famed for its Blue Grottoes, which were created by the Etruscans. Among them are Serpents Grotto and the Roman Gallery, a Roman tunnel that connects the town of Ponza to the (now closed) large sandy beach called Chiaia di Luna on the west side. The island has many archeological ruins visible everywhere, including Greek, and Phoenician necropoli ruins in the middle of the island. There are Etruscan ruins on parts of the island jumbled with Roman ruins. A large statue called Il Mamozio ("The Mummy") or Il Mitreo, meaning miter or priest's hat, is a 3,000-year-old marble statue and was found in the harbor. Depicting a local Etrurian consul, it is now displayed in a museum in Naples behind protective plastic, where it was reunited with its head. It is the oldest known Etruscan statue of its kind and extremely rare.

Economy
The town of Ponza is a fishing and boating port with several large docks that can accommodate large ships. Its biggest industry is tourism followed by boatbuilding, boat repair and fishing.

The four mines at the northern end — the most beautiful area of the island — were closed down in 1975 by the Italian Environmental Protection Agency because the mining operation was destroying the wildlife and flora, which are endangered species. The mines produced kaolin and Bentonite. Kaolin is used in making Kaolin-Pectin medicine and the manufacture of porcelain.

Ponza has a two lane road that goes from north to south, but can accommodate small cars only. An airstrip planned for the north of the island was canceled due to environmental concerns. Because there is no airstrip, seaplanes visit the island instead.

Celebrities who have vacationed on Ponza include Kirk Douglas, his son Michael Douglas, Anthony Quinn, Burt Lancaster, Gina Lollobrigida, Elsa Martinelli and Sophia Loren, Jacques Cousteau and his son, Philippe Cousteau, who filmed several documentaries in the area.

Federico Fellini's Satyricon (1969) was filmed on Ponza. Some scenes in Wes Anderson's film The Life Aquatic were filmed on the island; Ponza was instead called in the movie, "Port-au-Patois".

The Rai Fiction television series, "Un'altra Vita" (2014), was largely filmed on Ponza. Many of the scenes showcase the hilly landscape and rugged shoreline of the island.

Most of the people who live there raise rabbits and chickens and other animals in coops for meat to make cacciatore. Other farmed animals include goats, lamb and pigeons.

Many of the original inhabitants of Ponza are now leaving the island. They are steadily being replaced by other Italians from the mainland. Many local children simply move away after becoming adults and never return.

The local economy is in a downturn partly due to the severe restrictions on commercial fishing.

Transportation
Ferries reach Ponza from Naples, Terracina, Formia and Anzio; there are also hydrofoils (aliscafo) from Anzio and Formia that take about 75 minutes. The ferries and hydrofoils may not depart to and from Ponza during severe weather conditions. Much of Ponza is accessible by car and a bus runs the length of the island.

Main sights

 * Giardino Botanico Ponziano "Ponza's Botanical Garden"
 * Capo Bianco "Cape White" Italian National Natural Monument
 * Spiaggia di Chaia di Luna ("Moon Gravel Beach")
 * Grotta della Maga Circe ("Cave of the Sorceress Circe")
 * Grotta di Ulisse o del Sangue "Cave of Ulysses (Odysseus) of the Blood"
 * Monte Guardia ("Watchout Hill"), Ponza's tallest hill
 * Arco Naturale o Spaccapolpi, a natural arch standing in deep water looks like giant pants
 * Grotta Azzurra, a sea cave complex
 * Spiaggia delle Felci, a beach
 * Grotta di Serpent an underground maze of tunnels built by the Romans, much of it blocked off for safety reasons.
 * Grotte di Pilato, built by the Romans.
 * Spiaggia Di Le Forna, a smaller and tourist beach.
 * natural saltwater swimming pool in Le Forna.
 * Faraglioni di Lucia Rosa (Rocky shoals) named in honor of Lucia Rosa
 * Spiaggia di Frontone, a beach
 * Spiaggia di Santa Maria, a beach
 * Cala Fonte Natural fisherman's harbor, swimming on the north side is interesting.
 * Bue marino cave a cave where the seals were used to find cover.
 * cala Gaetano Beautiful sea colors, nice variety of fish during the spring time are visible.
 * La Caletta Also called the sunset coast where is possible to admire some beautiful sunsets.
 * Forte Papa An ancient fortress used to defend the island from Saracens attacks from the sea.

Feasts

 * June 20 feast of St Silverius
 * August 15 feast of the Assumption of Mary

title: Ponza