Тетрадка.бгПримери за класически числа на Рамзи и няколко примера за обобщени числа на Рамзи.

Теоремата на Ремзи гласи,че за всеки двойка естествени числа (r,s) ,съществува цяло число R(r,s),такова че за всяко черно-бяло оцветяване на пълен граф с R(r,s) върха,същвствува или пълен изцяло черен подграф с r върха, или пълен изцяло бял подграф с s върха,т.е. R(r,s) зависи изцяло от r и s. Доказателството на теоремата се прави като се намира точна горна граница на R(r,s)<= R(r−1,s) + R(r,s−1) и се прави по индукция. Накратко е изложено в следния вид: “We prove the theorem for the 2 colour case, by induction on r+s. It is clear from the definition that for all n, R (n, 1) = R (1, n) = 1. This starts the induction. We prove that R(r, s) exists by finding an explicit bound for it. By the inductive hypothesis R (r−1, s) and R (r, s−1) exist. Claim: R(r,s) ≤ R(r−1,s) + R(r,s−1): Consider a complete graph on R(r−1,s) + R(r,s−1)vertices. Pick a vertex v from the graph and consider two subgraphs M and N where a vertex w is in M <==>(v, w) is blue and is in N otherwise. Now |M| ≥ R(r −1,s) or |N| ≥ R(r,s −1), again by the pigeonhole principle. In the former case if M has a red Ks then so does the original graph and we are finished. Otherwise M has a blue Kr-1 and so M union {v} ha