Teoría estructural de Ramsey

En matemáticas, la teoría estructural de Ramsey es una generalización categórica de la teoría de Ramsey , arraigada en la idea de que muchos resultados importantes de la teoría de Ramsey tienen una estructura lógica "similar". La observación clave es señalar que estos teoremas de tipo Ramsey se pueden expresar como la afirmación de que una determinada categoría (o clase de estructuras finitas) tiene la propiedad de Ramsey (definida a continuación).

La teoría estructural de Ramsey comenzó en la década de 1970 ^[1] con el trabajo de Nešetřil y Rödl , y está íntimamente relacionada con la teoría de Fraïssé . Recibió cierto interés renovado a mediados de la década de 2000 debido al descubrimiento de la correspondencia Kechris-Pestov-Todorčević , que conectaba la teoría estructural de Ramsey con la dinámica topológica .

Historia

Leeb  [ de ] recibe crédito ^[2] por haber inventado la idea de una propiedad de Ramsey a principios de los 70, y la primera publicación de esta idea parece ser el artículo de 1972 de Graham , Leeb y Rothschild sobre el tema. ^[3] El desarrollo clave de estas ideas fue realizado por Nešetřil y Rödl en su serie de artículos de 1977 ^[4] y 1983 ^[5] , incluido el famoso teorema de Nešetřil-Rödl. Este resultado fue reprobado independientemente por Abramson y Harrington , ^[6] y luego generalizado por Prömel  [ de ] .^[7] Más recientemente, Mašulović ^{[8] [9] [10]} y Solecki ^{[11] [12] [13]} han realizado un trabajo pionero en el campo.

Motivación

Este artículo utilizará la convención de la teoría de conjuntos de que cada número natural puede considerarse como el conjunto de todos los números naturales menores que él: es decir . Para cualquier conjunto , un color de es una asignación de una de etiquetas a cada elemento de . Esto se puede representar como una función que asigna cada elemento a su etiqueta en (que usará este artículo), o de manera equivalente, como una partición de en piezas.${\displaystyle n\in \mathbb {N} }$${\displaystyle n=\{0,1,\ldots ,n-1\}}$${\displaystyle A}$${\displaystyle r}$${\displaystyle A}$${\displaystyle r}$${\displaystyle A}$${\displaystyle \Delta :A\to r}$${\displaystyle r=\{0,1,\ldots ,r-1\}}$${\displaystyle A=A_{0}\sqcup \cdots \sqcup A_{r-1}}$${\displaystyle r}$

Estos son algunos de los resultados clásicos de la teoría de Ramsey:

• (Finito) Teorema de Ramsey : para cada , existe tal que para cada color- de todos los subconjuntos de elementos -de , existe un subconjunto , con , tal que es -monocromático.${\displaystyle k\leq m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \Delta :[n]^{(k)}\to r}$${\displaystyle k}$${\displaystyle n=\{0,1,\ldots ,n-1\}}$${\displaystyle A\subseteq n}$${\displaystyle |A|=m}$${\displaystyle [A]^{(k)}}$${\displaystyle \Delta }$
• Teorema (finito) de van der Waerden : para cada , existe tal que para cada -coloración de , existe una progresión aritmética -monocromática de longitud .${\displaystyle m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \Delta :n\to r}$${\displaystyle n}$${\displaystyle \Delta }$${\displaystyle \{a,a+d,a+2d,\ldots ,a+(m-1)d\}\subseteq n}$${\displaystyle m}$
• Teorema de Graham-Rothschild : fija un alfabeto finito . A - palabra parámetro de longitud más de un elemento , de manera que todo el aparecer, y sus primeras apariciones son en orden creciente. El conjunto de palabras de todos los parámetros de longitud superior se indica mediante . Dado y , formamos su composición reemplazando cada aparición de in con la entrada th de . Entonces, el teorema de Graham-Rothschild establece que para cada , existe tal que para cada color de todos los parámetros de palabras de longitud${\displaystyle L=\{a_{0},a_{1},\ldots ,a_{d-1}\}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle L}$${\displaystyle w\in (L\cup \{x_{0},x_{1},\ldots ,x_{k-1}\})^{n}}$${\displaystyle x_{i}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle L}$${\displaystyle \textstyle [L]{\binom {n}{k}}}$${\displaystyle \textstyle w\in [L]{\binom {n}{m}}}$${\displaystyle \textstyle v\in [L]{\binom {m}{k}}}$ ${\displaystyle \textstyle w\circ v\in [L]{\binom {n}{k}}}$${\displaystyle x_{i}}$${\displaystyle w}$${\displaystyle i}$${\displaystyle v}$
  ${\displaystyle k\leq m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \textstyle \Delta :[L]{\binom {n}{k}}\to r}$${\displaystyle k}$${\displaystyle n}$, existe , tal que (es decir, todas las subpalabras del parámetro -de ) es -monocromático.${\displaystyle \textstyle w\in [L]{\binom {n}{m}}}$${\displaystyle \textstyle w\circ [L]{\binom {m}{k}}=\{w\circ v:v\in [L]{\binom {m}{k}}\}}$${\displaystyle k}$${\displaystyle w}$${\displaystyle \Delta }$
• (Finito) Teorema de Folkman : para cada , existe tal que para cada -coloración de , existe un subconjunto , con , tal que , y es -monocromático.${\displaystyle m,r\in \mathbb {N} }$${\displaystyle n\in \mathbb {N} }$${\displaystyle r}$${\displaystyle \Delta :n\to r}$${\displaystyle n}$${\displaystyle A\subseteq n}$${\displaystyle |A|=m}$${\displaystyle \textstyle {\big (}\sum _{k\in A}k{\big )}<n}$${\displaystyle \textstyle \operatorname {FS} (A)=\{\sum _{k\in B}k:B\in {\mathcal {P}}(A)\setminus \varnothing \}}$${\displaystyle \Delta }$

Todos estos teoremas de "tipo Ramsey" tienen una idea similar: fijamos dos enteros y , y un conjunto de colores . Luego, queremos mostrar que hay algunos lo suficientemente grandes, de modo que para cada color de las "subestructuras" de tamaño en el interior , podemos encontrar una "estructura" adecuada en el interior , de tamaño , de modo que todas las "subestructuras" de tamaño tienen el mismo color.${\displaystyle k}$${\displaystyle m}$${\displaystyle r}$${\displaystyle n}$${\displaystyle r}$${\displaystyle k}$${\displaystyle n}$${\displaystyle A}$${\displaystyle n}$${\displaystyle m}$${\displaystyle B}$${\displaystyle A}$${\displaystyle k}$

Los tipos de estructuras permitidos dependen del teorema en cuestión, y esto resulta ser prácticamente la única diferencia entre ellos. Esta idea de un "teorema de tipo Ramsey" conduce a la noción más precisa de la propiedad de Ramsey (abajo).

La propiedad de Ramsey

Sea una categoría . tiene la propiedad de Ramsey si para cada número natural , y todos los objetos en , existe otro objeto en , tal que para cada color , existe un morfismo que es -monocromático, es decir, el conjunto${\displaystyle \mathbf {C} }$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle A,B}$${\displaystyle \mathbf {C} }$${\displaystyle D}$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle \Delta :\operatorname {Hom} (A,D)\to r}$ ${\displaystyle f:B\to D}$${\displaystyle \Delta }$

${\displaystyle f\circ \operatorname {Hom} (A,B)={\big \{}f\circ g:g\in \operatorname {Hom} (A,B){\big \}}}$

es -monocromático. ^[14]${\displaystyle \Delta }$

A menudo, se toma como una clase de estructuras finitas sobre algún lenguaje fijo , con incrustaciones como morfismos. En este caso, en lugar de colorear morfismos, uno puede pensar en colorear "copias" de en , y luego encontrar una copia de en , de modo que todas las copias de en esta copia de sean monocromáticas. Esto puede prestarse más intuitivamente a la idea anterior de un "teorema de tipo Ramsey".${\displaystyle \mathbf {C} }$${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$${\displaystyle A}$${\displaystyle D}$${\displaystyle B}$${\displaystyle D}$${\displaystyle A}$${\displaystyle B}$

También existe la noción de una propiedad dual de Ramsey; tiene la propiedad de Ramsey dual si su categoría dual tiene la propiedad de Ramsey como arriba. Más concretamente, tiene la propiedad dual de Ramsey si para cada número natural , y todos los objetos en , existe otro objeto en , de modo que para cada -color , existe un morfismo para el que es -monocromático.${\displaystyle \mathbf {C} }$ ${\displaystyle \mathbf {C} ^{\mathrm {op} }}$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle A,B}$${\displaystyle \mathbf {C} }$${\displaystyle D}$${\displaystyle \mathbf {C} }$${\displaystyle r}$${\displaystyle \Delta :\operatorname {Hom} (D,A)\to r}$ ${\displaystyle f:D\to B}$${\displaystyle \operatorname {Hom} (B,A)\circ f}$${\displaystyle \Delta }$

Ejemplos

• Teorema de Ramsey: la clase de todas las cadenas finitas , con mapas que preservan el orden como morfismos, tiene la propiedad de Ramsey.
• van der Waerden teorema: en la categoría cuyos objetos son los ordinales finitos , y cuyos morfismos son mapas afines para , , la propiedad Ramsey es válido para .${\displaystyle x\mapsto a+dx}$${\displaystyle a,d\in \mathbb {N} }$${\displaystyle d\neq 0}$${\displaystyle A=1}$
• Teorema de Hales-Jewett : sea ​​un alfabeto finito, y para cada uno , sea ​​un conjunto de variables. Vamos a ser la categoría cuyos objetos son para cada uno , y cuyos morfismos , para , son funciones que son rígidos y sobreyectiva en . Entonces, tiene la propiedad dual de Ramsey para (y , dependiendo de la formulación).${\displaystyle L}$${\displaystyle k\in \mathbb {N} }$${\displaystyle X_{k}=\{x_{0},\ldots ,x_{k-1}\}}$${\displaystyle k}$${\displaystyle \mathbf {GR} }$${\displaystyle A_{k}=L\cup X_{k}}$${\displaystyle k\in \mathbb {N} }$${\displaystyle A_{n}\to A_{k}}$${\displaystyle n\geq k}$${\displaystyle f:X_{n}\to A_{k}}$${\displaystyle X_{k}\subseteq A_{k}=\operatorname {codom} f}$${\displaystyle \mathbf {GR} }$${\displaystyle A=A_{0}}$${\displaystyle B=A_{1}}$
• Teorema de Graham-Rothschild: la categoría definida anteriormente tiene la propiedad dual de Ramsey.${\displaystyle \mathbf {GR} }$

La correspondencia Kechris-Pestov-Todorčević

En 2005, Kechris , Pestov y Todorčević ^[15] descubrieron la siguiente correspondencia (en lo sucesivo denominada correspondencia KPT ) entre la teoría estructural de Ramsey, la teoría de Fraïssé y las ideas de la dinámica topológica.

Sea un grupo topológico . Para un espacio topológico , un -flujo (denotado ) es una acción continua de on . Decimos que es extremadamente susceptible caso -flow en un espacio compacto admite un punto fijo , es decir, el estabilizador de que es en sí.${\displaystyle G}$${\displaystyle X}$${\displaystyle G}$${\displaystyle G\curvearrowright X}$${\displaystyle G}$${\displaystyle X}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G\curvearrowright X}$${\displaystyle X}$ ${\displaystyle x\in X}$${\displaystyle x}$${\displaystyle G}$

Para una estructura Fraïssé , su grupo de automorfismo puede considerarse un grupo topológico, dada la topología de convergencia puntual , o equivalentemente, la topología subespacial inducida por el espacio con la topología del producto . El siguiente teorema ilustra la correspondencia KPT:${\displaystyle \mathbf {F} }$${\displaystyle \operatorname {Aut} (\mathbf {F} )}$${\displaystyle \operatorname {Aut} (\mathbf {F} )}$${\displaystyle \mathbf {F} ^{\mathbf {F} }=\{f:\mathbf {F} \to \mathbf {F} \}}$

Teorema (KPT). Para una estructura Fraïssé , los siguientes son equivalentes:${\displaystyle \mathbf {F} }$

1. El grupo de automorfismos de es extremadamente dócil.${\displaystyle \operatorname {Aut} (\mathbf {F} )}$${\displaystyle \mathbf {F} }$
2. La clase tiene la propiedad Ramsey.${\displaystyle \operatorname {Age} (\mathbf {F} )}$

Ver también

• Teoría de Ramsey
• Teorema de Fraïssé
• Edad (teoría del modelo)

Referencias

1. Van Thé, Lionel Nguyen (10 de diciembre de 2014). "Una encuesta sobre la teoría estructural de Ramsey y la dinámica topológica con la correspondencia Kechris-Pestov-Todorcevic en mente". arXiv : 1412.3254 [ math.CO ].
2. Larson, Jean A. (1 de enero de 2012), "Combinatoria infinita" , en Gabbay, Dov M .; Kanamori, Akihiro; Woods, John (eds.), Handbook of the History of Logic , Sets and Extensions in the Twentieth Century, 6 , Holanda Septentrional, págs. 145–357, doi : 10.1016 / b978-0-444-51621-3.50003-7 , ISBN 9780444516213, consultado el 30 de noviembre de 2019
3. Graham, R. L; Leeb, K; Rothschild, B. L (1 de junio de 1972). "Teorema de Ramsey para una clase de categorías". Avances en Matemáticas . 8 (3): 417–433. Código Bibliográfico : 1972PNAS ... 69..119G . doi : 10.1016 / 0001-8708 (72) 90005-9 . ISSN 0001-8708 . 
4. Nešetřil, Jaroslav; Rödl, Vojtěch (mayo de 1977). "Particiones de sistemas relacionales y conjuntos finitos". Revista de Teoría Combinatoria, serie A . 22 (3): 289–312. doi : 10.1016 / 0097-3165 (77) 90004-8 . ISSN 0097-3165 . 
5. Nešetřil, Jaroslav; Rödl, Vojtěch (1 de marzo de 1983). "Clases Ramsey de sistemas establecidos". Revista de Teoría Combinatoria, serie A . 34 (2): 183–201. doi : 10.1016 / 0097-3165 (83) 90055-9 . ISSN 0097-3165 . 
6. Abramson, Fred G .; Harrington, Leo A. (septiembre de 1978). "Modelos sin indiscernibles" . El diario de la lógica simbólica . 43 (3): 572. doi : 10.2307 / 2273534 . ISSN 0022-4812 . JSTOR 2273534 .  
7. Prömel, Hans Jürgen (julio de 1985). "Propiedades de partición inducida de cubos combinatorios". Revista de Teoría Combinatoria, serie A . 39 (2): 177-208. doi : 10.1016 / 0097-3165 (85) 90036-6 . ISSN 0097-3165 . 
8. Masulovic, Dragan; Scow, Lynn (2 de junio de 2015). "Construcciones categóricas y la propiedad de Ramsey". arXiv : 1506.01221 [ math.CT ].
9. Masulovic, Dragan (22 de septiembre de 2016). "Pre-adjunciones y la propiedad de Ramsey". arXiv : 1609.06832 [ math.CO ].
10. Mašulović, Dragan (29 de julio de 2017). "Teoremas duales de Ramsey para estructuras relacionales". arXiv : 1707.09544 [ math.CO ].
11. Solecki, Sławomir (agosto de 2010). "Un teorema de Ramsey para estructuras con relaciones y funciones". Revista de Teoría Combinatoria, serie A . 117 (6): 704–714. doi : 10.1016 / j.jcta.2009.12.004 . ISSN 0097-3165 . 
12. Solecki, Slawomir (20 de abril de 2011). "Enfoque abstracto de la teoría de Ramsey finita y un teorema de Ramsey auto-dual". arXiv : 1104.3950 [ math.CO ].
13. Solecki, Sławomir (16 de febrero de 2015). "Teorema dual de Ramsey para árboles". arXiv : 1502.04442 [ math.CO ].
14. Mašulović, Dragan (29 de julio de 2017). "Teoremas duales de Ramsey para estructuras relacionales". arXiv : 1707.09544 [ math.CO ].
15. Kechris, AS; Pestov, VG; Todorcevic, S. (febrero de 2005). "Límites de Fraïssé, teoría de Ramsey y dinámica topológica de grupos de automorfismo" (PDF) . Análisis geométrico y funcional . 15 (1): 106–189. doi : 10.1007 / s00039-005-0503-1 . ISSN 1016-443X .