Usuari:Jordiventura96/proves/Teoria de Ramsey

Segons la teoria de Ramsey', del total d'estrelles del cel, sempre podem seleccionar un subconjunt d'elles per dibuixar diferents objectes com ara un triangle, un quadrilàter, un paraigües o un pop.

En matemàtiques, la Teoria de Ramsey (anomenada així pel matemàtic logicista anglès Frank P. Ramsey) és el camp que estudia les condicions sota les quals ha d'aparèixer l'ordre. Els problemes de la teoria de Ramsey són normalment de la forma: Quants elements ha de contenir una estructura per tal que es doni necessàriament una propietat?

«	El desordre absolut és impossible	»
— Theodore S. Motzkin

Exemples

Suposem que n coloms han estat allotjades en m nius. Quina mida ha de tenir n, respecte m, per tal que es pugui garantir que com a mínim, un niu tingui més d'un colom? La resposta ve donada pel principi de Dirichlet: si n>m llavors, pel cap baix, un niu tindrà més d'un colom. La teoria de Ramsey generalitza aquest resultat, com s'explica a continuació.

Un resultat típic de la teoria de Ramsey amb una estructura matemàtica que es talla a trossos. Llavors es planteja: quina mida ha de tenir l'estructura original per tal de garantir que almenys una de les peces tingui una propietat interessant donada?

Arestes blaves i vermelles en un graf K₅ sense cap K₃ monocromàtic

Per exemple, considerem un graf complet d'ordre n, és a dir, hi ha n vèrtexs tots connectats entre ells a través d'una aresta. Un graf compet d'ordre 3 es diu triangle. Ara bé, cada aresta pot tenir un dels següents colors: vermell o blau. En un graf, quant ha de valdre n per tal de garantir que existeixi com a mínim un triangle blau o vermell? Resulta que el resultat és 6. En la imatge es mostra una distribució en què per n=5, no s'obté cap triangle del mateix color.

Una altra manera d'expressar aquest resultat és la següent: en qualsevol activitat amb almenys sis persones, hi ha tres persones que són mútuament conegudes o mútuament desconegudes (teorema de l'amistat).

Aquest és un cas especial del teroema de Ramsey, segons el qual per a qualsevol enter donat, c i donats els enters n₁...n_c existeix el número R(n₁...n_c), anomenat número de Ramsey, tal que si les arestes d'un graf compet d'ordre R(n₁...n_c) es pinten amb c colors diferents, llavors par

Este es un caso especial del teorema de Ramsey, que dice que para cualquier entero dado c, y dado los enteros n₁,...,n_c, existe el número: R(n₁,...,n_c), llamado número de Ramsey, tal que si las aristas de un grafo completo de orden R(n₁,...,n_c) se colorean con c colores distintos, entonces para algún i entre 1 y c, debe contener un subgrafo completo de orden n_i cuyas aristas están todas coloreadas con el color i. El caso especial de arriba tiene c = 2 y n₁ = n₂ = 3.

Para dos colores y valores de r y s a lo sumo 10 se conocen los siguientes valores exactos y cotas:

r,s	1	2	3	4	5	6	7	8	9	10
1	1
2	1	2
3	1	3	6
4	1	4	9	18
5	1	5	14	25	43–49
6	1	6	18	36–41	58–87	102–165
7	1	7	23	49–61	80–143	113–298	205–540
8	1	8	28	58–84	101–216	132–495	217–1031	282–1870
9	1	9	36	73–115	126–316	169–780	241–1713	317–3583	565–6588
10	1	10	40–42	92–149	144–442	179–1171	289–2826	331–6090	581–12677	798–23556

Como R(r, s) = R(s, r), hay una simetría trivial con respecto la diagonal.

Esta tabla está extraída del survey Small Ramsey Numbers de Stanisław Radziszowski,excepto R(4,6)≥36, probado por Geoffrey Exoo en 2012; R(3,10) ≤ 42,probado por Jan Goedgebeur y Stanisław Radziszowski en 2012; y R(4,8) ≥ 58, probado por Hiroshi Fujita en 2012.

Para tres colores, el único valor exacto no trivial conocido es R(3,3,3)=17.

De idéntica forma se puede definir el número de Ramsey de grafos que no sean completos, conociéndose para dos colores y grafos con a lo más 5 vértices, todos los valores exactos salvo los dos casos formados por dos grafos completos con 5 vértices y por uno completo de 5 vértices menos una arista y uno completo de 5 vértices.v

Resultats

Alguns resultats interessants de la teoria de Ramsey són els següents:

• Teorema de Ramsey infinit (1928): si tenim un conjunt infinit i distribuim els seus elements en un nombre finit de caixes, llavors almenys una de les caixes conté un nombre infinit d'elements.

• Teorema de Bolzano. Tota successió infinita de nombres reals conté una subsuccessió infinita creixent o decreixent.

• Problema del final feliç (Erdős, Szekeres i Klein; 1933). Donats 5 punts en el pla (de tal manera que 3 d'ells no siguin colineals), hi ha quatre que formen un quadrilàter convex.

• Teorema de la amistat (Ramsey; 1928). En qualsevol reunió de 6 persones, o bé 3 d'elles es coneixen entre sí, o bé 3 d'elles no es coneixen entre sí.

• Teorema d'Erdős-Szekeres (1936). Si tenim n² + 1 nombres reals, n + 1 d'ells formen una successió monòtona.

• Teorema de van der Waerden (1927). Per a tot parell de nombres enters l i c, existeix un nombre N tal que, donada una progressió aritmètica P de longitud almenys N (en un grup additiu Z) i si pintem la progressió P amb un nombre c de colors, llavors existeix una sub-progressió P₀ monocromàtica de longitud l.

• Teorema de Hales-Jewett (1963): Per a n i c nombres enters, existeix un nombre H tal que si les cel·les d'un cub H-dimensional n×n×n×...×n són pintades amb c colors, ha d'existir una fila, columna, etc. de longitud n on les cel·les estan pintades amb un únic color. Aquest teorema implica el teorema de Van der Waerden.

• Teorema de Schur. Per a tot nombre c, existeix N tal que si els números 1,2,..., N són pintats per c colors, existeixen dos nombres enters x, y tals que x, y, x+y tenen el mateix color.

Naturalesa dels resultats

Els resultats a la teoria de Ramsey tenen noramlement dues característiques bàsiques. En primer lloc, generalment no són constructives, els resultats mostren l'existència d'alguna estructura, però no d'una recepta o procediment per a trobar-la (que no sigui per força bruta). En segon lloc, mentre que els resultats de la teoria de Ramsey ens diuen que un objecte prou gran haurà de contenir necessàriament una estructura donada, sovint al prova d'aquests resultats requereix que aquests objectes siguin enormement grans amb límits que creixen de manera exponencial.

Problemes oberts

• Problema d'Erdős-Szekeres: aquest problema correspon a la generalització del problema del final feliç, i és:

$N(n)=2^{n-2}-1\,$

• Problema del límit de R_k = R(k,k;2): existeix $\lim _{k\to \infty }R_{k}^{\frac {1}{k}}\;$? I en cas que existeixi, quin és el seu valor?

Vegeu també

• Problema del final feliç
• Matemàtica discreta
• Combinatòria

Bibliografia

• R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1990)
• Landman and A. Robertson, Ramsey Theory on the Integers, Student Mathematical Library Vol. 24, AMS (2004)
• F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc., Vol. s2-30, no 1 (1930),
• P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math., Vol. 2, p. 463-470 (1935)
• G. Boolos, J. P. Burgess and R. Jeffrey, Computability and Logic, Cambridge: Cambridge University Press. (1974, revised 2004)