Ramseyev teorem

[Gost]

kaze: za svako r, m iz IN, i sve prirodne brojeve r_1, r_2, ..., r_m>=r postoji najmanji prirodni broj N tako velik da ako imamo skup od n>=N elemenata, i ako u tom skupu razvrstamo sve r-podskupove u m klasa K_1, .., K_m, onda postoji

ili r_1 elemenata ciji su svi r-podskupovi u K_1,
ili r_2 el. ciji su svi r-podskupovi u K_2,
....

ili r_m elemenata ciji su svi r-podskupovi u K_m

broj N=R(r_1, r_2, ..., r_m;r) zove se (opci) Ramseyev broj.


Jesu li te klase K_1, ..., K_m inducirane relacijom ekvivalencije na skupu r-podskupova, ili na skupu svih elemenata skupa?
Kao ilustracija tvrdnje R(3,2;2)=3 je u knjizi naveden primjer "Od troje obicnih ljudi, dvoje moraju biti istog spola." Klase su inducirane relacijom ekvivalencije "biti istoga spola".
Onda bi to znacilo da medju troje ljudi postoje ili troje od kojih koji su svaka dva u klasi "muskarci", ili dvoje koje su u drugoj klasi, dakle klasi "zene".

[Gost]

Ili su elementi klasa dvoclani podskupovi, a relacija ekvivalencije na tim "dvojcima" "biti istoga spola"?

[defar]

te klase su s obzirom na relaciju ekvivalencije na skupu iz kojeg su elementi tog N-clanog skupa o kojem se prica. u slucaju R(p, q;2) vrijedi zgodna karakterizacija Ramseyevog broja:
za svaka dva prirodna broja p,q postoji minimalni broj N takav da ako potpun graf K_N obojamo u dvije boje, postoji ili njegov potpun podgraf K_p obojan jednom bojom, ili njegov potpun podgraf K_q obojan drugom bojom. (taj N je R(p,q;2))

za R(3,2;2):
ako je neki istaknuti vrh muskarac, onda ako su oba dva preostala vrh ekvivalentna s njime, ocito moraju i oni biti ekvivalentni medjusobno (zbog...errr...tranzitivnosti(?) kojom se odlikuje relacija ekvivalencije), dakle svi bridovi obojani jednom bojom,
ili preostala dva vrha nisu ekvivalentna s njime, daklem, oni su ekvivalentni medjusobno, pa postoji ili troclani podskup cija su svaka dva elementa ekvivalentna medjusobno, ili dvoclani podskup.....

_________________
`To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'