Teoria de Ramsey
La teoria de Ramsey, cridada aixina per Frank P. Ramsey, és un camp de les matemàtiques que estudia les condicions baix les quals deu aparéixer l'orde.
Els problemes de la teoria de Ramsey són típicament de la forma: ¿Quants elements deu contindre una estructura per a garantisar l'existència d'una propietat particular?
Eixemples
[editar | editar còdic]Supongam que n colomes han segut estajades en m nius. ¿Quin tamany ha de tindre n, sobre m, per a que es puga garantisar que a lo manco, un niu continga dos colomes?. La resposta està donada pel principi del colomer: si n > m per lo manco un niu tindrà a lo manco dos colomes. La teoria de Ramsey generalisa este resultat, com s'explica a continuació.
Un resultat típic de la teoria de Ramsey s'inicia en alguna estructura matemàtica que es talla en trossos. ¿Quin tamany ha de tindre l'estructura original en la finalitat de garantisar que a lo manco una de les peces tinga una propietat interessant donada?
Per eixemple, considerem un grafo complet d'orde n, és dir, hi ha n vèrtiços i cada vèrtiç està conectat a tots els atres vèrtiços per mig d'una aresta. Un grafo complet d'orde 3 es diu triàngul. Ara be, cada aresta pot tindre un dels següents colors: roig o blau. ¿Cóm de gran deu ser n per a poder garantisar que existixca un triàngul blau o un triàngul roig? Resulta que la resposta és 6. Vore l'artícul sobre el teorema de Ramsey per a una prova rigorosa.
Una atra manera d'expressar este resultat és el següent: en qualsevol activitat en a lo manco sis persones, hi ha tres persones que són mútuament conegudes o mútuament desconegudes. Vore el teorema de l'amistat.
Est és un cas especial del teorema de Ramsey, que diu que per a qualsevol sancer donat c, i donat els sancers n1,...,nc, existix el número: R(n1,...,nc), cridat número de Ramsey, tal que si les arestes d'un grafo complet d'orde R(n1,...,nc) es colorean en c colores distints, llavors per a algun i entre 1 i c, deu contindre un subgrafo complet d'orde ni les arestes del qual estan totes coloreadas en el color i. El cas especial de dalt té c = 2 i n1 = n2 = 3.
Per a dos colors es coneixen els següents valors exactes i cotes per a R(r, s):
| r, s | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|
| 3 | 6 | |||||||
| 4 | 9 | 18 | ||||||
| 5 | 14 | 25 | 43–48 | |||||
| 6 | 18 | 36–41 | 58–87 | 102–165 | ||||
| 7 | 23 | 49–61 | 80–143 | 115–298 | 205–540 | |||
| 8 | 28 | 59–84 | 101–216 | 134–495 | 219–1031 | 282–1870 | ||
| 9 | 36 | 73–115 | 133–316 | 183–780 | 252–1713 | 329–3583 | 565–6588 | |
| 10 | 40–42 | 92–149 | 149–442 | 204–1171 | 292–2826 | 343–6090 | 581–12677 | 798–23556 |
| 11 | 47-50 | 102-191 | 183-633 | 262-1804 | 405-4553 | 457-10630 | 22325 | 45881 |
| 12 | 53-59 | 128-238 | 203-848 | 294-2566 | 417-6954 | 16944 | 38832 | 81123 |
| 13 | 60-68 | 138-291 | 233-1138 | 347-3703 | 511-10578 | 817-27485 | 64864 | |
| 14 | 67-77 | 147-349 | 267-1461 | 5033 | 15263 | 41525 | ||
| 15 | 74-87 | 158-417 | 275-1878 | 401-6911 | 22112 | 873-63609 | 1313 |
Com a R(r, s) = R(s, r), hi ha una simetria trivial en respecte la diagonal. També és trivial el cas R(n,2) ya que R(n,2)=n.
Esta taula està extreta del survey "Small Ramsey Numbers" de Stanisław Radziszowski,[2] llevat R(4,6)≥36, provat per Geoffrey Exoo en 2012;[3] R(3,10) ≤ 42, provat per Jan Goedgebeur i Stanisław Radziszowski en 2012;[4] i R(4,8) ≥ 58, provat per Hiroshi Fujita en 2012.[5]
Per a tres colors, l'únic valor exacte no trivial conegut és R(3,3,3)=17.
D'idèntica forma es pot definir el número de Ramsey de grafos que no siguen complets, coneixent-se per a dos colors i grafos en a lo més 5 vèrtiços, tots els valors exactes llevat els dos casos formats per dos grafos complets en 5 vèrtiços i per un complet de 5 vèrtiços menys una aresta i un de complet de 5 vèrtiços.
Resultats
[editar | editar còdic]Alguns resultats importants de teoria de Ramsey són:
- Teorema de Ramsey Infinit (1928). Si tenim un conjunt infinit i distribuïm els seus elements en un número finito de caixes, llavors hi ha una caixa que conté infinits elements.
- Teorema de Bolzano. Tota successió infinita d'número real conté una subsucesión infinita creixent o decreixent.
- Problema del final feliç (Erdős, Szekeres & Klein; 1933). Daus 5 punts en el pla (de manera que cada 3 d'ells no siguen colineales), hi ha quatre que formen un quadrilàter convexo.
- Teorema de l'amistat (Ramsey; 1928). En qualsevol reunió de 6 persones, o be 3 d'elles es coneixen entre sí, o be, 3 d'elles no es coneixen entre sí.
- Teorema de Erdős-Szekeres(1936). Si tenim n2 + 1 número real, n + 1 d'ells formen una successió monòtona.
- Teorema de van der Waerden (1927). Per a tot parell de sancers l i c, existix un N tal que, donada una progressió aritmètica P de llongitut a lo menys N (en un grup aditiu Z), i si coloreamos la progressió P en c colores, llavors existix una sub-progressió aritmètica Po monocromàtica de llongitut l.
- Teorema de Hales-Jewett (1963): Per a sancers n i c, existix el número H de manera que les celes d'una gaveta H-dimensional n×n×n×...×n són coloreados en c colores, deu existir una fila, columna, etc. de llongitut n en a on les seues celes estan coloreadas en un sol color. Açò és, si es juga el tres en llínea en un tauler-hipercubo de dimensions suficientment grans, llavors no es pot terminar el joc en empat, no important que tan gran siga n (la llongitut de X o 0 necessària per a guanyar la partida), ni el número c de jugadors. La teorema de Hales-Jewett implica la teorema de Van der Waerden.
- Teorema de Schur. Per a tot número c, hi ha un N tal que si els números 1,2,..., N són coloreados per c colores, existix un parell de sancers x, i tal que x, i, x+i tenen el mateix color.
Vore també
[editar | editar còdic]Notes
[editar | editar còdic]- ↑ "S. A. Soman" (21 d'agost de 2008). "Computational Methods for Large Sparse Power Systems Analysis", pp. 31.
- ↑ "Small Ramsey Numbers" Stanisław P. Radziszowski (primerat versió: Juny 11, 1994; revisió #16: Giner 15, 2021).
- ↑ B. McKay, Ramsey Graphs
- ↑ Plantilla:Cite arXiv
- ↑ Plantilla:Cite arXiv
Referències
[editar | editar còdic]- 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)
https://www.cut-the-knot.org/arithmetic/combinatorics/ramsey44.shtml https://mathworld.wolfram.com/RamseyNumber.html https://www.cut-the-knot.org/arithmetic/combinatorics/ramsey43.shtml https://math.mit.edu/apost/courses/18.204_2018/ramsey-numbers.pdf
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Teoría de Ramsey» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.