El teorema de Ramsey

El teorema de Ramsey es un teorema de combinatoria sobre particiones de conjuntos, formulado y demostrado por el matemático inglés Frank Ramsey en 1930 [1] . Aparece en la literatura en varias formulaciones. Este teorema marcó el comienzo de la teoría de Ramsey .

Formulaciones

Formulación de teoría de conjuntos

Caso especial N ( p , q , r )

Sean , y números naturales , y . $pags$ $q$ $r$ $p,\;q\geqslant r$

Entonces existe un número con la siguiente propiedad: si todos los subconjuntos de elementos del conjunto de elementos se dividen arbitrariamente en dos familias separadas y , entonces existe un subconjunto de elementos del conjunto cuyos subconjuntos de elementos están contenidos en , o existe un subconjunto de elementos, todos los subconjuntos de elementos cuyos subconjuntos están contenidos en . $N=N(p,\;q,\;r)$ $r$ $norte$ $S$ $\alfa$ $\beta$ $pags$ $S$ $r$ $\alfa$ $q$ $r$ $\beta$

Caso general

Deja que el conjunto tenga elementos. Considere sus subconjuntos , denote la totalidad de todos estos subconjuntos , particiones ordenadas , números que definen la partición . $S$ $norte$ $r$ $r \ geqslant 1$ ${\ Displaystyle P_ {r} (S)}$ $t$ ${\displaystyle P_{r}(S)=A_{1}\cup A_{2}\cup \ldots \cup A_{t))$ ${\displaystyle q_{1},\ q_{2},\ \ldots,\ q_{t))$ ${\displaystyle 1\leqslant r\leqslant q_{1},\;q_{2},\;\ldots,\;q_{t))$

Entonces, para cualquier partición ordenada del conjunto existe un número mínimo tal que si , entonces existe un subconjunto del conjunto , es decir, tal subconjunto del conjunto del cual todos los subconjuntos están contenidos en [2] . $t$ ${\ Displaystyle P_ {r} (S)}$ $N(q_{1},\;q_{2},\;\ldots,\;q_{t};\;r)$ $N\geqslant N(q_{1},\;q_{2},\;\ldots,\;q_{t};\;r)$ ${\ estilo de visualización (q_ {i}, \; A_ {i})}$ $S$ ${\ Displaystyle q_ {i}}$ $S$ $r$ $A_{i},\ 1\leqslant t\leqslant t$

Expresado en el lenguaje de la teoría de grafos

Para cualquier número natural , cualquier coloración de bordes de un gráfico completo suficientemente grande contiene un subgráfico completo con vértices para algún color . En particular, para cualquier y , un gráfico completo suficientemente grande de dos colores (blanco y negro) contiene un subgráfico de vértice negro completo o un subgráfico de vértice blanco completo. $C$ ${\displaystyle n_{1},\ n_{2},\ \ldots,\ n_{c))$ $C$ $n_{yo}$ $i$ $r$ $s$ $r$ $s$

Números de Ramsey

El número mínimo para el que esto se cumple se llama número de Ramsey. $R(r,\;s)$

Por ejemplo, igualdad significa que, por un lado, en cualquier coloración bicolor de un gráfico completo hay un triángulo monocolor, y por otro lado, que el gráfico completo admite una coloración bicolor sin monocolor. triangulos. ${\ estilo de visualización R (3, \; 3) = 6}$ $K_{6}$ $K_{5}$

En general, para la coloración de -color se utiliza la notación del número mínimo de vértices que asegura la existencia de algún color . $C$ $R(n_{1},\;n_{2},\;\ldots,\;n_{c})$ $K_{n_{i))$ $i$

Demostración del teorema de Ramsey

Estuche bicolor

Lema 1. $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1).$

Prueba. Probemos usando el método de inducción matemática sobre . ${\ estilo de visualización r + s}$

base de inducción. , ya que un grafo de 1 vértice puede considerarse un grafo completo de cualquier color. ${\ estilo de visualización R (n, \; 1) = R (1, \; n) = 1}$

transición de inducción . Sea y . Considere un gráfico de vértice completo en blanco y negro . Tome un vértice arbitrario y denote con y los conjuntos incidentes en los subgrafos en blanco y negro, respectivamente. Dado que en el gráfico de vértices, según el principio de Dirichlet (combinatoria) , , o . $r>1$ $s>1$ $R(r-1,\;s)+R(r,\;s-1)$ $v$ $METRO$ $norte$ $v$ $R(r-1,\;s)+R(r,\;s-1)=|M|+|N|+1$ ${\ estilo de visualización | M | \ geqslant R (r-1, \; s)}$ ${\ estilo de visualización | N | \ geqslant R (r, \; s-1)}$

deja _ Entonces, o bien en (y por lo tanto en todo el gráfico) hay blanco , que completa la demostración, o bien hay negro en , que junto con forma negro . El caso se trata de manera similar. ${\ estilo de visualización | M | \ geqslant R (r-1, \; s)}$ $METRO$ $Kansas}$ $METRO$ $K_{r-1}$ $v$ ${\ Displaystyle K_ {r}}$ ${\ estilo de visualización | N | \ geqslant R (r, \; s-1)}$

Comentario. Si ambos son pares, la desigualdad se puede acentuar: . ${\ estilo de visualización R (r-1, \; s)}$ ${\ estilo de visualización R (r, \; s-1)}$ $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)-1$

prueba _ Supongamos que ambos son pares. Establezca y considere un gráfico de vértices en blanco y negro . Si el grado del vértice -ésimo en el subgrafo negro, entonces, de acuerdo con el lema del apretón de manos , es par. Como es impar, debe haber un par . Para mayor precisión, asumimos que es par. Denote por y los vértices incidentes al vértice 1 en los subgrafos en blanco y negro, respectivamente. Entonces ambos son pares. Según el principio de Dirichlet (combinatoria) , o , o . Como es par e impar, la primera desigualdad se puede reforzar, por lo que o , o . $p=R(r-1,\;s)$ ${\ estilo de visualización q = R (r, \; s-1)}$ ${\ estilo de visualización t = p + q-1}$ $t$ $d_{i}$ $i$ ${\ estilo de visualización \ suma _ {i = 1} ^ {t} d_ {i}}$ $t$ $d_{i}$ $d_{1}$ $METRO$ $norte$ ${\ estilo de visualización | M | = d_ {1}}$ ${\ estilo de visualización | N | = t-1-d_ {1}}$ ${\ estilo de visualización | M | \ geqslant p-1}$ ${\ Displaystyle N \ geqslant q}$ $|M|$ $p-1$ ${\ estilo de visualización | M | \ geqslant p}$ ${\ estilo de visualización | N | \ geqslant q}$

Supongamos . Entonces, el subgrafo generado por el conjunto contiene white y la prueba está completa, o contiene black , que junto con el vértice 1 forma black . El caso se trata de manera similar. $|M|\geqslant p=R(r-1,\;s)$ $METRO$ $Kansas}$ $K_{r-1}$ ${\ Displaystyle K_ {r}}$ ${\ estilo de visualización | N | \ geqslant q = R (r, \; s-1)}$

Un estuche de más colores.

Lema 2. Si , entonces ${\ estilo de visualización c> 2}$ $R(n_{1},\;\ldots,\;n_{c})\leqslant R(n_{1},\;\ldots,\;n_{c-2},\;R(n_ {c-1},\;n_{c})).$

Prueba. Considere un gráfico de vértices y coloree sus bordes con colores. Consideraremos temporalmente los colores y un color. Entonces el gráfico se vuelve -coloreado. De acuerdo con la definición de número , dicho gráfico contiene, para algún color , como algo coloreado por el color común y . En el primer caso, la demostración es completa. En el segundo caso, devolvemos los colores anteriores y notamos que, por la definición del número de Ramsey, el gráfico de vértice completo contiene colores o colores , por lo que la afirmación está completamente probada. $R(n_{1},\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$ $C$ ${\ estilo de visualización c-1}$ $C$ ${\ estilo de visualización (c-1)}$ $R(n_{1},\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$ $K_{n_{i))$ $i$ $1\leqslant i\leqslant c-2$ ${\displaystyle K_{R(n_{c-1},\;n_{c)))))$ ${\ estilo de visualización c-1}$ $C$ $R(n_{c-1},\;n_{c})$ $K_{n_{c-1))$ ${\ estilo de visualización c-1}$ $K_{n_{c))$ $C$

El lema 1 implica que los números de Ramsey para . De esto, con base en el Lema 2, se sigue que para cualquier . Esto prueba el teorema de Ramsey. ${\ estilo de visualización c = 2}$ $R(n_{1},\;\ldots,\;n_{c})$ $C$

Significados de los números de Ramsey

Tabla de valores

Hay muy pocos datos para en [3] . La siguiente tabla de valores para los números de Ramsey está tomada de la tabla de Radzishevsky [4] , los datos son a partir de 2020. $N(q_{1},\;q_{2},\;\ldots,\;q_{t};\;t)$ ${\ estilo de visualización t> 2}$ $N(q_{1},\;q_{2};\;2)$

${\ estilo de visualización r, \ s}$	una	2	3	cuatro	5	6	7	ocho	9	diez
una	una	una	una	una	una	una	una	una	una	una
2	una	2	3	cuatro	5	6	7	ocho	9	diez
3	una	3	6	9	catorce	Dieciocho	23	28	36	[40, 42]
cuatro	una	cuatro	9	Dieciocho	25	[36, 41]	[49, 61]	[59, 84]	[73, 115]	[92, 149]
5	una	5	catorce	25	[43, 48]	[58, 87]	[80, 143]	[101, 216]	[133, 316]	[149, 442]
6	una	6	Dieciocho	[36, 41]	[58, 87]	[102, 165]	[115, 298]	[134, 495]	[183, 780]	[204, 1171]
7	una	7	23	[49, 61]	[80, 143]	[115, 298]	[205, 540]	[217, 1031]	[252, 1713]	[292, 2826]
ocho	una	ocho	28	[59, 84]	[101, 216]	[134, 495]	[217, 1031]	[282, 1870]	[329, 3583]	[343, 6090]
9	una	9	36	[73, 115]	[133, 316]	[183, 780]	[252, 1713]	[329, 3583]	[565, 6588]	[581, 12677]
diez	una	diez	[40, 42]	[92, 149]	[149, 442]	[204, 1171]	[292, 2826]	[343, 6090]	[581, 12677]	[798, 23556]

Estimaciones asintóticas

De la desigualdad se sigue que $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)$

R(r,\;s)\leqslant {\binom {r+s-2}{r-1)).

En particular, el límite superior sigue de aquí ( Erdős , Sekeres )

R(s,\;s)\leqslant (1+o(1)){\frac {4^{s-1}}{\sqrt {\pi s}}}.

Línea de fondo

R(s,\;s)\geqslant (1+o(1)){\frac {s}({\sqrt {2}}e}}2^{s/2},

obtenido por Erdős en 1947 utilizando su método probabilístico .

Las estimaciones modernas son de Spencer y Conlon, respectivamente.

(1+o(1)){\frac {{\sqrt {2}}s}{e}}2^{s/2}\leqslant R(s,\;s)\leqslant s^{ -c\log s/\log \log s}4^{s}.

Obviamente, estas estimaciones mejoran ligeramente los primeros resultados y no se acercan entre sí.

Erdős creía que en caso de emergencia, la humanidad aún podría encontrarla , pero no . $R(5,\;5)$ ${\ estilo de visualización R (6, \; 6)}$

También se conoce la estimación hallada por Kim en 1995 . En combinación con la estimación , esta desigualdad establece el orden de crecimiento de . $R(3,\;t)\geqslant \left({\frac {1}{162}}+o(1)\right){\frac {t^{2}}{\ln {t} }}$ ${\displaystyle R(3,\;t)\leqslant (1+o(1)){\frac {t^{2}}{\ln {t))))$ $R(3,\;t)=\Theta \left({\frac {t^{2}}{\ln {t}}}\right)$

Variaciones y generalizaciones

El teorema de Erdős-Rado es una generalización del teorema de Ramsey a conjuntos incontables.

La teoría de Ramsey es una rama de las matemáticas que estudia las condiciones bajo las cuales debe aparecer algún orden en objetos matemáticos arbitrariamente formados.

Notas

↑ F. P. Ramsey Sobre un problema de lógica formal. - Proc. Matemáticas de Londres. Soc.", 2ª ser., 30 (1930), págs. 264-286
↑ Rybnikov, 1972 , pág. 93.
↑ Rybnikov, 1972 , pág. 96.
↑ Stanisław Radziszowski. Small Ramsey Numbers (inglés) // The Electronic Journal of Combinatorics. - 2017. - 3 de marzo. — ISSN 1077-8926 . Archivado desde el original el 29 de mayo de 2017. (revisión 15)

Enlaces

Teorema de Prasolov V. V. Ramsey (ver el análisis del problema 22.7)
teoría ramsey

Literatura

Rybnikov K. A. Introducción al análisis combinatorio. - Universidad Estatal de Moscú, 1972.