Teorema de Ramsey

Teorema de Ramsey

En combinatòria la teorema de Ramsey establix que en qualsevol esquema de color aplicat a un grafo complet suficientment gran, es trobaran subgrafos complets monocromàtics. Per a dos colors, la teorema enuncia que per a qualsevol parell de sancers positius (r,s), existix a lo manco un sancer positiu R(r,s) com aquell per a qualsevol grafo complet en R(r,s) vèrtiços, les arestes dels quals (o branques) estan coloreados de roig o blau, existix un subgrafo complet de r vèrtiços que és totalment blau, o un subgrafo complet de s vèrtiços que és totalment roig. R(r,s) representa un sancer que depén conjuntament de r i s. S'entén que representa al sancer més chicotet per al que la teorema aplica. A eixe número se li crida número de Ramsey.

La teorema de Ramsey és fundacional en combinatoria. La primera versió d'estos resultats varen ser provats per F. P. Ramsey. Açò va iniciar la teoria combinatòria, ara cridada teoria de Ramsey, que busca regularitat en mig del desorde: condicions generals per a l'existència de subestructura en propietats regulars.

Una extensió d'esta teorema s'aplica a qualsevol número finito de colors, en lloc de solament dos. Més precisament, la teorema enuncia que per qualsevol número donat de colors «c», i qualsevol sancer n₁,...,n_c, existix un número, R(n₁, ..., n_c), que si les arestes d'un grafo complet d'orde R(n₁, ...,n_c) es colorea en c colores diferents, llavors per a algun i entre 1 i c, deu contindre un subgrafo complet d'orde n_i les arestes del qual són de color i. El cas especial de dalt a on c = 2 (i n₁ = r i n₂ = s).

Una atra generalisació s'obté en considerar grafos que no siguen complets. Són coneguts tots els valors de R(G₁,G₂) si G₁ i G₂ tenen a lo més 5 vèrtiços llevat quan G₁ o G₂ és el grafo complet de 5 vèrtiços i l'atre és o be el grafo complet de 5 vèrtiços o be el grafo complet de 5 vèrtiços menys una aresta.

Eixemple: R(3,3)=6

2 colors en K₅ en K₃ no monocromàtic.

En el següent eixemple, la fòrmula R(3,3) proveïx una solució a la pregunta sobre el número mínim de vèrtiços que deu contindre un grafo per a assegurar que

1. a lo manco tres vèrtiços del grafo estan conectats o,
2. a lo manco tres vèrtiços estan desconectats.

Note's que per la naturalea simètrica del problema, R(r,s) produïx la mateixa solució que R(s,r). Açò és encara més evident en l'eixemple R(3,3) perque els valors de r i s són els mateixos.

Supongam que les arestes d'un grafo complet de 6 vèrtiços estan coloreadas en roig i vert. En elegir un vèrtiç v, veem que hi ha 5 arestes incidint en ell, i aixina, pel principi del colomer, a lo manco 3 d'ells deuen ser del mateix color. Sense pèrdua de generalitat podem assumir que a lo manco 3 d'estes arestes, que conecten en els vèrtiços r, s i t són blaves (si no ho són, intercanvie's blava en roig en lo que seguix). Si algun de les arestes (r, s), (r, t) o (s, t) és també blava, llavors tenim un triàngul enterament blau. Sino, llavors les tres arestes són roges, i tenim un triàngul enterament roig. Com este argument funciona per a qualsevol esquema de color, qualsevol K₆ conté un K₃ monocromàtic, i llavors R(3,3) ≤ 6. La versió popular d'esta demostració es coneix com teorema de l'amistat.

Bibliografia

• .
• .
• .
• .
• .
• .
• .
• .
• .