FACTOID # 19: Cheap sloppy joes: Looking for reduced-price lunches for schoolchildren? Head for Oklahoma!
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Ramsey theory

Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in Ramsey theory typically ask a question of the form: how many elements of some structure must there be to guarantee that a particular property will hold? An oft-quoted slogan for the subject is "complete disorder is impossible" (T. S. Motzkin). Frank Plumpton Ramsey (February 22, 1903 – January 19, 1930) was a British mathematician, philosopher and economist. ... Euclid, detail from The School of Athens by Raphael. ...


Suppose, for example, that we know that n pigeons have been housed in m pigeonholes. How big must n be before we can be sure that at least one pigeonhole houses at least two pigeons? The answer is the pigeonhole principle: if n > m, then at least one pigeonhole will have at least two pigeons in it. Ramsey's theorem generalizes this principle as explained below. The inspiration for the name of the principle: pigeons in holes. ... In combinatorics, Ramseys theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. ...


A typical result in Ramsey theory starts with some mathematical structure, which is then cut into pieces. How big must the original structure be, in order to ensure that at least one of the pieces has a given interesting property?


For example, consider a complete graph of order n; that is, there are n vertices (dots) and each vertex is connected to every other vertex by an edge (a line). A complete graph of order 3 is called a triangle. Now color every edge red or blue. How large must n be in order to ensure that there is either a blue triangle or a red triangle? It turns out that the answer is 6. See the article on Ramsey's theorem for a rigorous proof. In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... In combinatorics, Ramseys theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. ... In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ...


Another way to express this result is as follows: at any party with at least six people, there are either three people who are all mutual acquaintances (each one knows the other two) or mutual strangers (each one does not know either of the other two). See theorem on friends and strangers. The friendship theorem is a mathematical theorem in an area of mathematics called Ramsey theory. ...


This also is a special case of Ramsey's theorem, which says that for any given integer c, any given integers n1,...,nc, there is a number, R(n1,...,nc;c), such that if the edges of a complete graph of order R(n1,...,nc;c) are colored with c different colors, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all color i. The special case above has c = 2 and n1 = n2 = 3. In combinatorics, Ramseys theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. ...


Two other key theorems of Ramsey theory are:

  • Van der Waerden's theorem: For any given c and n, there is a number V, such that if the elements of an arithmetic progression of V numbers are colored with c different colors, then it must contain an arithmetic progression of length n whose elements are all the same color.
  • Hales-Jewett theorem: For any given n and c, there is a number H such that if the cells of a H-dimensional n×n×n×...×n cube are colored with c colors, there must be one row, column, etc. of length n all of whose cells are the same color. That is, if you play on a board with sufficiently many dimensions, then multi-player n-in-a-row tic-tac-toe cannot end in a draw, no matter how large n is, and no matter how many people are playing.

A variant of van der Waerden's theorem is Schur's theorem: for any given c there is a number N, such that if the numbers 1, 2, ..., N are colored with c different colors, then there must be a pair of integers x, y such that x, y, and x+y are all the same color. Many generalizations of this theorem exist, including Rado's Theorem, Rado-Folkman-Sanders theorem, Hindman's theorem, and the Milliken-Taylor theorem. A classic reference for these and many other results in Ramsey theory is [1]. Van der Waerdens theorem is a theorem of the branch of mathematics called Ramsey theory. ... In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. ... In mathematics, the Hales-Jewett theorem [2] is a fundamental combinatorial result of Ramsey theory, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be completely random. An informal geometric statement of the theorem is that for any... Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ... Van der Waerdens theorem is a theorem of the branch of mathematics called Ramsey theory. ... In mathematics, Schurs theorem is either of two different theorems of the mathematician Issai Schur. ... Rados theorem is a theorem from the branch of mathematics known as Ramsey theory. ... Given a set , a collection of subsets is called partition regular if for any , and any finite partition , then for some i ≤ n, contains an element of . ... Let denote the set of finite subsets of . ... The Milliken-Taylor theorem is a generalization of both Ramseys theorem and Hindmans theorem. ...


Results in Ramsey theory typically have two notable characteristics. Firstly, they are often non-constructive; they may show that some structure exists, but they give no recipe for how to actually find this structure (other than brute force search); for instance, the pigeonhole principle is of this form. Secondly, while Ramsey theory results do say that sufficiently large objects must necessarily contain a given structure, often the proof of these results requires these objects to be enormously large - bounds which grow exponentially, or even as fast as the Ackermann function are not uncommon. In many cases these bounds are artifacts of the proof, and it is not known whether they can be substantially improved. In other cases it is known that any bound must be extraordinarily large, sometimes even larger than any primitive recursive function; see the Paris-Harrington theorem for an example. In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ... In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ... The inspiration for the name of the principle: pigeons in holes. ... In mathematics, a quantity that grows exponentially (or geometrically) is one that grows at a rate proportional to its size. ... In the theory of computation, the Ackermann function or Ackermann-Peter function is a simple example of a recursive function that is not primitively recursive. ... In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ... In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory is true but not provable in Peano arithmetic. ...


Reference

  1. R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1980).
  2. B. Landman and A. Robertson, Ramsey Theory on the Integers, Student Mathematical Library Vol. 24, AMS, (2004)

See also


  Results from FactBites:
 
Ramsey theory - definition of Ramsey theory in Encyclopedia (744 words)
Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear.
Van der Waerden's theorem: For any given c and n, there is a number V, such that if the elements of an arithmetic progression of V numbers are colored with c different colors, then it must contain an arithmetic progression of length n whose elements are all the same color.
Secondly, while Ramsey theory results do say that sufficiently large objects must necessarily contain a given structure, often the proof of these results requires these objects to be enormously large - bounds which grow exponentially, or even as fast as the Ackermann function are not uncommon.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m