Teorema de l’amistat

Frank Ramsey (1903 – 1930) va ser un matemàtic anglès. A partir de les seves investigacions s’ha creat la branca de la combinatòria coneguda com a Teoria de Ramsey.

La teoria de Ramsey, busca regularitats en mig del desordre i en quines condicions apareixen.

Considerem per exemple els grafs complets [katex]  \mathbf{K}[/katex] consistents en una sèrie de punts o vèrtexs units entre de totes les maneres possibles per mitjà d’arestes. Amb 3 punts [katex]  \mathbf{K}_{3}[/katex] és un triangle, amb 4 [katex]  \mathbf{K}_{4}[/katex] un quadrilàter i les seves dues diagonals.

Si acolorim les arestes amb dos colors.  Quina mida ha de tenir el graf [katex]  \mathbf{K}[/katex] per estar segurs que apareix un triangle d’un sol color? En aquest cas estem buscant el nombre de Ramsey [katex]  \mathbf{R}(3,3)[/katex] 

La resposta sabem que és 6: ens cal el graf  [katex]  \mathbf{K}_{6}[/katex] amb 6 vèrtexs i les seves 15 arestes com el que tenim.

La demostració és simple:

• • En primer lloc, es veu que amb 3, 4 o 5 vèrtexs hi ha configuracions del graf que no tenen triangles monocolors. 
  • 
  • A continuació cal assegurar que en el cas  [katex]  \mathbf{K}_{6}[/katex] sempre hi ha un triangle monocolor.
  • Ens fixem en un dels seus vèrtexs, de les 5 arestes que surten d’ell n’hi haurà 3 o més del mateix color.
  • Per tal que no es formin triangles monocolors les arestes que uneixen els extrems d’aquestes 3 arestes han de ser de l’altre color.
  • Però llavors es forma un triangle monocolor amb els extrems d’aquestes 3 arestes.
  • Així doncs, un [katex] \mathbf{K}_{6}[/katex] de dos colors sempre contindrà un [katex] \mathbf{K}_{3}[/katex] d’un color.

Aquest és el nombre de Ramsey més petit, el següent és [katex]  \mathbf{R}(4,3)=9[/katex]. Encara es desconeixen molts nombres de Ramsey i en altres sols s’han demostrat el seu límit superior o inferior. Podeu veure els darrers resultats obtinguts a Wolfram Alpha Mathword.