Un teorema de Ramsey para los enteros

Andrés Eduardo Caicedo · 2025

Read Un teorema de Ramsey para los enteros by Andrés Eduardo Caicedo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-15381.txt.

Introduction

Andres Eduardo Caicedo proves a Ramsey type result for the integers, in work from twenty twenty-five. Ramsey theory asks when order must appear inside large structures. Caicedo finds all pairs of linear orders with a stated arrow property that links the integers to a second order. The key step pins down which orders map to the integers paired with themselves in a simpler one step form. The note is short, formal, and aimed at readers in combinatorics and logic.

Catalog record

CREATORAndrés Eduardo Caicedo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-15381

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Un teorema de Ramsey para los enteros Andrés Eduardo Caicedo Abstract 2020 Mathematics Subject Classification 03E02 1. El teorema de Ramsey En todo grupo de diez personas siempre podemos encontrar, o bien cuatro que se han hablado mutuamente, o bien tres que no se han hablado entre sí. Éste es un caso particular del teorema de Ramsey, un resultado fundamental en la combinatoria de grafos. Teorema 1.1 (Ramsey [ Ram29 , Theorem B] ) . Para todos los enteros positivos n,m podemos encontrar un número N tal que en todo grafo con N vértices podemos encontrar, o bien una copia del grafo completo de n vértices, o bien m vértices sin arcos entre sí. Frank Ramsey [ Ram29 ] estableció (una versión general de) este resultado, con el que se inauguró la teoría que lleva su nombre, con el fin de estudiar la consistencia de ciertas fórmulas de la lógica de primer orden. Desde entonces se han encontrado muchísimas aplicaciones en diversas áreas, así como generalizaciones y variantes. Ramsey presentó dos versiones de su teorema, la versión finita que enunciamos arriba, y una infinita. En esta nota estamos interesados en la versión infinita. Primero, algo de notación: dado un conjunto X , el grafo completo K_{X} tiene a X como conjunto de vértices, con arcos (aristas) entre todo par de vértices distintos. El grafo vacío \bar{K}_{X} tiene a X como conjunto de vértices, y no tiene arcos. Escribimos K_{n} para denotar el grafo completo en un conjunto de n vértices. En esta nota, los subgrafos son siempre inducidos , es decir que si \mathcal{G}=(V_{G},A_{G}) es un grafo, \mathcal{H}=(V_{H},A_{H}) es un subgrafo si y sólo si V_{H}\subseteq V_{G} and A_{H}=\{\{v,w\}\in A_{G}:v,w\in V_{H}\} . En particular, que \mathcal{G} contiene una copia de un grafo \mathcal{J} quiere decir que la contiene como subgrafo inducido. Teorema 1.2 (Ramsey [ Ram29 , Theorem A] ) . Dado un conjunto infinito X , si los arcos de K_{X} se particionan en dos clases, hay un subconjunto infinito H\subseteq X tal que todos los arcos de K_{H} están en la misma clase. De manera equivalente, el teorema dice que para todo grafo \mathcal{G} con conjunto de vértices X hay un subconjunto infinito de vértices H tal que \mathcal{G} contiene o bien al grafo completo K_{H} o bien al grafo vacío \bar{K}_{H} . También podemos formular el resultado diciendo que si coloreamos los arcos de K_{X} rojos o azules, hay un H infinito tal que o bien K_{H} es rojo, o bien es azul. (En lo que sigue, todos los coloreos son siempre de los arcos de un grafo, en rojo y azul.) Definición 1.3 . Un conjunto infinito es contable si y sólo si está en biyección con (es decir, tiene el mismo tamaño que) \mathbb{N} , el conjunto de los números naturales. En cierto sentido, el teorema 1.2 es un resultado acerca del orden de los números naturales. El objetivo de esta nota es demostrar una versión del resultado acerca del orden de los enteros. 2. El cálculo de particiones Es conveniente introducir algo de notación antes de proseguir. Definición 2.1 . Dados enteros positivos N,a,b , escribimos N\to(a,b)^{2} (lo que, tristemente, se lee ‘ N flecha a,b super 2’) para denotar que cualquier coloreo de K_{N} contiene, o bien una copia roja de K_{a} , o bien una copia azul de K_{b} . Escribimos N\nrightarrow(a,b)^{2} para indicar lo contrario. El estudio de esta relación flecha y sus variantes es el cálculo de particiones . El superíndice 2 en la definición 2.1 indica que éste es un caso particular (el caso bidimensional) de notación más general; más adelante discutiremos el caso de superíndice 1 (el principio de casillas). La notación se debe a Rado, quien la introdujo en su artículo [ ER53 ] conjunto con Erdős, considerando más generalmente la versión cardinal , donde N,a,b pueden ser tamaños de conjuntos infinitos. La notación es algo intimidante cuando uno la encuentra por primera vez, pero es muy conveniente en esta área. Ejemplo 2.2 . Que {5\nrightarrow(3,3)^{2}} significa que hay un coloreo de K_{5} tal que no hay triángulos con los tres arcos del mismo color (el triángulo es monocromático ). Por ejemplo, el coloreo ilustrado en la figura de la izquierda. Por otro lado, que 6\to(3,3)^{2} significa que en cualquier coloreo de K_{6} hay un triángulo monocromático: cualquier vértice v (en la figura de la derecha, el vértice verde) está unido a por lo menos otros tres vértices por arcos del mismo color c . Si cualquiera de los arcos entre estos vértices es también de color c , estos dos vértices y v forman un triángulo de color c . En caso contrario, estos tres vértices forman un triángulo del otro color. Se sigue que, para todo N\geq 6 , N\to(3,3)^{2} , y que no podemos reemplazar el 6 por un número menor. Decimos entonces que 6 es el número de Ramsey de 3,3. Definición 2.3 . El número de Ramsey de a,b , R(a,b) , es el menor N tal que N\to(a,b)^{2} . Que N existe es precisamente el contenido del teorema 1.1 . En esta notación, el ejemplo con el que comenzamos la nota, dice que 10\to(4,3)^{2} , de modo que R(4,3)\leq 10 . De hecho, R(4,3)=9 . En lo que sigue, estudiamos la variante de la relación flecha donde, en vez de números, consideramos órdenes lineales. 3. Órdenes lineales Recuérdese que una biyección entre dos conjuntos A y B es una función {\varphi\!:A\to B} que es inyectiva (puntos distintos de A son enviados por \varphi a puntos distintos de B ) y sobreyectiva (todo punto de B es la imagen bajo \varphi de un punto de A ). Intuitivamente, podemos pensar en A y B como dos idiomas y en \varphi como un diccionario que traduce de manera perfecta entre los dos. Si X es contable, por ejemplo X=\mathbb{N} , todo H como en el teorema 1.2 tiene el mismo tamaño que X . Denotando por \aleph_{0} (‘alef-0’) el tamaño de los números naturales, tenemos que \aleph_{0}\to(\aleph_{0},\aleph_{0})^{2} . Sin embargo, y esta observación es la que nos lleva a todo lo que sigue, si imponemos una estructura adicional en X , por ejemplo, si en vez de mirar sólo al conjunto X , consideramos en cambio un orden lineal (X,<) (simplemente diremos un orden), el teorema 1.2 no garantiza que la restricción a H de este orden sea no trivial, en el sentido que explicamos siguiendo la observación 3.2 . Los órdenes finitos son muy simples: para cada n , hay un único orden de tamaño n . Por ejemplo, para n=4 , el orden es \bullet\quad\bullet\quad\bullet\quad\bullet (en términos técnicos, todos estos órdenes son isomorfos). La situación es completamente diferente cuando consideramos conjuntos infinitos: aunque \mathbb{N} , \mathbb{Z} y \mathbb{Q} son contables, como órdenes lineales lucen muy distintos. Definición 3.1 . Decimos que dos órdenes (L_{1},<_{1}) y (L_{2},<_{2}) son isomorfos o tienen el mismo tipo de orden o, simplemente, tienen el mismo tipo si y sólo si hay una biyección \varphi\!:L_{1}\to L_{2} entre ellos que transforma un orden en el otro, es decir que para cualesquiera x_{1},x_{2}\in L_{1} , tenemos que x_{1}<_{1}x_{2}\quad\iff\quad\varphi(x_{1})<_{2}\varphi(x_{2}). En términos técnicos, los tipos de orden son las clases de

Read the complete text