WIKIPEDIA Ramsey's theorem In combinatorial mathematics,Ramsey's theorem,in one of its graph-theoretic forms,states that one will find demonstrat edge nd sufficiently large complete two colours(say,blue red), let and s integers.1 louring of the complete grahon Rr)vertices contains a blue clique onverticesr an nsey's rem sta s that there exist least positive n every bl red edge vertices.(Here R(r,s)signifies an integer that depends on both r and s.) Ramsey's theorem isa foundational result in combinatorics.The first version of this resut was proved by F.P. I theory now called R msey theory,tha seeks regular mid diso ondition for the existence with regular properties.In this application it is a question An extension of this theorem applies to any finite number of colours,rather than just two.More precisely.the tha r any given numb urs,c,and any given integers n,.nthere R(n,...,n),such that if the edges of a complete graph of order R(n,..n)are coloured with c different colours,then for some ibetween 1 and c,it must contain a complete subgraph of order n;whose edges are all colour i.The special case above has c=2(and n=r and n2=s). Contents Example:R(3,3)=6 Proof of the theorem 2-colour case Case of more colours Ramsey numbers Asymptotics A multicolour example:R(3,3,3)=17 Extensions of the theorem Infinite Ramsey theorem Infinite version implies the finite Directed graph Ramsey numbers Ramsey computation and quantum computers See also Notes References External links Example:R(3,3)=6Ramsey's theorem In combinatorial mathematics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. [1] Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.) Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. This initiated the combinatorial theory now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of monochromatic subsets, that is, subsets of connected edges of just one colour. An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colours, c, and any given integers n1 , …, nc , there is a number, R(n1 , …, nc ), such that if the edges of a complete graph of order R(n1 , ..., nc ) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour i. The special case above has c = 2 (and n1 = r and n2 = s). Example: R(3, 3) = 6 Proof of the theorem 2-colour case Case of more colours Ramsey numbers Asymptotics A multicolour example: R(3, 3, 3) = 17 Extensions of the theorem Infinite Ramsey theorem Infinite version implies the finite Directed graph Ramsey numbers Ramsey computation and quantum computers See also Notes References External links Contents Example: R(3, 3) = 6