Nùmer ëd Ramsey

Da Wikipedia.
Drapò piemontèis.png Vos an lenga piemontèisa
Për amprende a dovré 'l sistema dle parlà locaj ch'a varda sì


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[modìfica | modifiché la sorgiss]

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.