Nùmer ëd Ramsey

Fissà dij nùmer antregh positiv s,t, ël nùmer ëd Ramsey r(s,t) a l'é 'l pì cit antregh tal che minca graf ansima a r(s,t) vértes a l'ha 'n sot-graf andot ch'a l'é na crica d's element opura un sot-graf andot ch'a l'é n'ansem indipendent ëd t element. As dimostra che un nùmer përparèj a esist për da bon. Chèich arzultà an sij nùmer ëd Ramsey An general, ël cont dij nùmer ëd Ramsey a l'é n'afé motobin complicà. Tutun, chèich arzultà as peulo oten-se con dj'osservassion assè sempie. Dagià che ël nùmer ëd crica d'un graf G a l'é ugual al nùmer d'indipendensa ëd sò complementar G', ij nùmer ëd Ramsey a son simétrich, visadì r(s,t)=r(t,s). Dagià che n'ansem d'1 vértes a l'é indipendent, r(s,1)=r(1,s)=1. Dagià che un graf G nen complet ansima a $s\geq 2$ vértes a l'ha nùmer d'indipendensa $\alpha (G)\geq 2$, i l'oma $r(s,2)\leq s$. Dagià che për n<s ël nùmer ëd crica dël graf complet $K_{n}$ ansima a n element a l'é $\omega (K_{n})=n<s$ e che sò nùmer d'indipendensa a l'é $\alpha (K_{n})=1<2$, a-i na ven che $r(s,2)\geq s$. Donca r(s,2)=r(2,s)=s. D'arzultà pì complicà ch'a dan na valutassion dij nùmer ëd Ramsey a son: Ch'as pijo $s,t\geq 2$. Si G a l'é un graf ansima a n=r(s,t-1)+r(s-1,t) vértes, antlora $\omega (G)\geq s$ opura $\alpha (G)\geq t$. Donca $r(s,t)\leq r(s,t-1)+r(s-1,t)$. $r(s,t)\geq (s-1)(t-1)+1$. Si $s\geq 2$, antlora $r(s,s)\geq ({\sqrt {2}})^{s}$. Cost arzultà a l'é dovù a Paul Erdős e a l'é stàit publicà dël 1947.