Vés al contingut

Usuari:Jordiventura96/proves/Teoria de Ramsey

De la Viquipèdia, l'enciclopèdia lliure
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[1]

Exemples

[modifica]

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 K5 sense cap K3 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 n1...nc existeix el número R(n1...nc), anomenat número de Ramsey, tal que si les arestes d'un graf compet d'ordre R(n1...nc) 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 n1,...,nc, existe el número: R(n1,...,nc), llamado número de Ramsey, tal que si las aristas de un grafo completo de orden R(n1,...,nc) se colorean con c colores distintos, entonces para algún i entre 1 y c, debe contener un subgrafo completo de orden ni cuyas aristas están todas coloreadas con el color i. El caso especial de arriba tiene c = 2 y n1 = n2 = 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,[2]excepto R(4,6)≥36, probado por Geoffrey Exoo en 2012;[3] R(3,10) ≤ 42,probado por Jan Goedgebeur y Stanisław Radziszowski en 2012;[4] y R(4,8) ≥ 58, probado por Hiroshi Fujita en 2012.[5]

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

[modifica]

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 n2 + 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ó P0 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

[modifica]

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

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

  • Problema del límit de Rk = R(k,k;2): existeix ? I en cas que existeixi, quin és el seu valor?

Vegeu també

[modifica]

Referències

[modifica]
  1. "S. A. Soman". "Computational Methods for Large Sparse Power Systems Analysis", p. 31. 
  2. Error de citació: Etiqueta <ref> no vàlida; no s'ha proporcionat text per les refs nomenades Survey
  3. B. McKay, Ramsey Graphs
  4. Goedgebeur, Jan. New computational upper bounds for Ramsey numbers R(3,k), 2012. 
  5. Fujita, Hiroshi. A New Lower Bound for the Ramsey Number R(4, 8), 2012. 

Bibliografia

[modifica]
  • 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)