14.2: Teoría de Ramsey

Última actualización
Guardar como PDF

Page ID: 114404

Joy Morris
University of Lethbridge

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

Aunque la Teoría Ramsey es una parte importante de la Combinatoria (junto con la Enumeración, la Teoría de Gráficas y la Teoría del Diseño), este curso la tocará solo muy a la ligera. La idea básica es que si un objeto muy grande se corta en dos piezas (o un pequeño número de piezas), entonces al menos una de las piezas debe contener un subconjunto muy agradable. Aquí hay una ilustración.

Ejemplo$\PageIndex{1}$

Supongamos que cada borde de$K_6$ es de color rojo o azul. Mostrar que o hay un triángulo cuyos bordes son todos rojos, o hay un triángulo cuyos bordes son todos azules. Es decir,$K_6$ contiene una copia de la$K_3$ que tiene todos sus bordes del mismo color. Para abreviar, decimos que$K_6$ contiene un triángulo monocromático.

Solución

Elige algún vértice$v$. Dado que los$5$ bordes con los que inciden$v$ están coloreados con solo dos colores, el Principio de Pigeonhole generalizado implica que tres de estos bordes son del mismo color. Por definición, digamos que tres bordes$vu_1$,$vu_2$, y$vu_3$ son todos rojos.

Ahora,$u_1$,$u_2$, y$u_3$ son los vértices de una copia de$K_3$ que está dentro$K_6$. Si los tres bordes de esto$K_3$ son azules, entonces tenemos nuestro triángulo monocromático deseado (es decir, un triángulo azul). Entonces podemos suponer que uno de los bordes es rojo; digamos,$u_1u_2$ es rojo. Ya que los bordes$vu_1$ y también$vu_2$ son rojos, vemos eso$v$,$u_1$, y$u_2$ son los vértices de un triángulo monocromático (es decir, un triángulo rojo).

Definición: Número Ramsey

Vamos$k$,$\ell ∈ \mathbb{N}^+$.

1) Supongamos que cada borde de$K_n$ es de color rojo o azul. Decimos que hay una copia roja de$K_k$ si existen$k$ vértices$u_1, . . . , u_k$, de tal manera que el borde$u_iu_j$ es rojo para todos$i$ y$j$ (con$i \neq j$). De igual manera, decimos que hay una copia azul de$K_{\ell}$ si existen$\ell$ vértices$v_1, . . . , v_{\ell}$, de tal manera que el borde$v_iv_j$ es azul para todos$i$ y$j$ (con$i \neq j$).

2) El número Ramsey$R(k, \ell)$ es el número más pequeño$n$, de tal manera que siempre que cada borde de$K_n$ esté coloreado ya sea rojo o azul, siempre hay una copia roja de$K_k$, o una copia azul de$K_{\ell}$.

Ejemplo$\PageIndex{2}$

1) Tenemos$R(k, 1) = 1$ para todos$k$. Esto se debe a que no$K_1$ tiene bordes, por lo que, para cualquier coloración de alguna$K_n$, es cierto (a la vacuidad) que todos los bordes de$K_1$ son azules.

2) Tenemos$R(k, 2) = k$ para todos$k$. Es decir, si algún borde es azul, entonces hay un azul$K_2$, mientras que si no hay bordes azules, entonces toda la gráfica es roja$K_k$.

3) Tenemos$R(3, 3) = 6$. Para ver esto, tenga en cuenta que el Ejemplo 14.2.1 muestra$R(3, 3) ≤ 6$, mientras que la coloración del borde de$K_5$ a la derecha no tiene triángulo monocromático (porque los únicos ciclos monocromáticos son de longitud$5$), entonces$R(3, 3) > 5$.

$clipboard_ea0572a5ff789332d67343c231836fb83.png$

4) Tenemos$R(k, \ell) = R(\ell, k)$ para todos$k$ y$\ell$. Es decir, si cada coloración de$K_n$ tiene un rojo$K_k$ o un azul$K_{\ell}$, entonces vemos que cada coloración de$K_n$ debe tener un rojo$K_{\ell}$ o un azul$K_k$, simplemente cambiando rojo y azul en la coloración.

5) Si$k ≤ k'$ y$\ell ≤ \ell'$, entonces$R(k, \ell) ≤ R(k' , \ell')$. A saber, tenemos una coloración de$K_n$ que contiene ya sea un rojo$K_{k'}$ o un azul$K_{\ell'}$. Desde$k ≤ k'$ y$\ell ≤ \ell'$, sabemos que cualquiera$K_{k'}$ contiene una copia de$K_k$, y cualquiera$K_{ \ell'}$ contiene una copia de$K_{\ell} $.

No es nada obvio que$R(k, \ell)$ existe: teóricamente,$R(4, 4)$ podría no existir, porque podría ser posible colorear los bordes de una muy grande de tal$K_n$ manera que no haya monocromática$K_4$. Afortunadamente, la siguiente extensión de la prueba del Ejemplo 14.2.1 implica que$R(k, \ell )$ sí existe para todos$k$ y$\ell$. De hecho, proporciona un límite sobre qué tan grande$R(k, \ell)$ puede ser (ver Ejercicio 14.2.1 (3) a continuación).

Proposición$\PageIndex{1}$

$R(k, \ell) ≤ R(k − 1, \ell) + R(k, \ell − 1)$para todos$k$,$ \ell ≥ 2$

Prueba

Vamos$n = R(k − 1, \ell) + R(k, \ell − 1)$, y supongamos que cada borde de$K_n$ es de color rojo o azul. Deseamos mostrar que hay un rojo$K_k$ o un azul$K_{ \ell}$.

Elija algún vértice$v$ de$K_n$. Entonces el número de bordes incidentes con$v$ es

\[n − 1 = R(k − 1, \ell) + R(k, \ell − 1) − 1 > (R(k − 1, \ell) − 1) + (R(k, \ell − 1) − 1),\]

por lo que el muy generalizado Principio de Pigeonhole implica que cualquiera$R(k − 1, \ell)$ de estos bordes son rojos, o$R(k, \ell − 1)$ de estos bordes son azules.

Por definición, supongamos que los bordes$vu_1, vu_2, . . . , vu_r$ son todos azules, dónde$r = R(k, \ell − 1)$. Ahora,$u_1, u_2, . . . , u_r$ son los vértices de una copia de$K_r$ que está dentro$K_n$. Ya que$r = R(k, \ell − 1)$, sabemos que este$K_r$ contiene ya sea un rojo$K_k$ o un azul$K_{\ell−1}$.

Si contiene un rojo$K_k$, entonces tenemos el rojo deseado$K_k$. Entonces podemos suponer que$u_1, . . . , u_{\ell−1}$ son los vértices de un azul$K_{\ell-1}$. Dado que los bordes también$vu_1, vu_2, . . . , vu_{\ell−1}$ son azules, vemos que$v, u_1, u_2, . . . , u_{\ell -1}$ son los vértices del azul deseado$K_{\ell}$.

Ejercicio$\PageIndex{1}$

1) Mostrar$R(3, 4) > 6$.

2) Usando la Proposición 14.2.1 y los valores$R(k, \ell)$ dados en el Ejemplo 14.2.2, encuentra el mejor límite superior$R(k, \ell)$ para el que puedas$3 ≤ k ≤ \ell ≤ 6$.

3) Mostrar$R(k, \ell) ≤ 2^{k+\ell}$ para todos$k$ y$\ell$.

[Pista: Use la Proposición 14.2.1 y la inducción en$k + \ell$.]

4) Se sabe que$40 ≤ R(3, 10) ≤ 42$. Usando esta información, ¿qué puedes decir sobre$R(3, 11)$?

5) Mostrar que hay al menos dos triángulos monocromáticos en cada coloración de los bordes de$K_6$ con dos colores.

[Pista: Mostrar que debe haber dos triángulos rojos (digamos), o un triángulo rojo y un borde azul cuyos extremos no están en el triángulo. Luego muestra que cualquier coloración de los bordes que unen el triángulo rojo con el borde azul crea ya sea un triángulo azul o un segundo triángulo rojo.

Nota

El valor exacto de$R(k, \ell)$ parece ser extremadamente difícil de encontrar, a excepción de valores muy pequeños de$k$ y$\ell$. Por ejemplo, aunque se ha demostrado que$R(4, 4) = 18$ y$R(4, 5) = 25$, nadie ha podido determinar el valor preciso de$R(k, \ell)$ para ninguna situación en la que$k$ y$\ell$ se encuentren al menos ambos$5$. El legendario combinatorista Paul Erdös ($1913$—$1996$) dijo que sería desesperanza tratar de calcular el valor exacto de$R(6, 6)$, incluso con todos los recursos informáticos y las mentes más brillantes del mundo entero trabajando en el problema durante un año. (Sabemos que$R(6, 6)$ está en algún lugar entre$102$ y$165$.) Para obtener más información sobre los valores que se han calculado, consulte el artículo de Wikipedia sobre el teorema de Ramsey.

Ejercicio$\PageIndex{2}$

Los bordes de también$K_n$ pueden ser coloreados con más de dos colores.

1) Mostrar cada coloración de los bordes de$K_{17}$ con$3$ colores tiene un triángulo monocromático.

2) Supongamos que hay un triángulo monocromático en cada coloración de los bordes de$K_n$ con$c$ colores. Demuestre que si$N −1 > (c+ 1)(n−1)$, entonces cada coloración de los bordes de$K_N$ con$c + 1$ colores tiene un triángulo monocromático.

Argumentos similares (combinados con la inducción sobre el número de colores) establecen el siguiente resultado muy general.

Teorema$\PageIndex{1}$: Ramsey's Theorem

$c$Dados colores y tamaños fijos$n_1, . . . , n_c ≥ 1$, hay un entero

\[r = R(n_1, . . . , n_c)\]

tal que para cualquier$c$ coloración de los bordes de$K_r$, debe haber alguna$i ∈ \{1, . . . , c\}$ tal que$K_r$ tenga una subgrafía isomórfica a$K_{ni}$ todos cuyos bordes hayan sido coloreados con color$i$.

Prueba

Demostraremos este resultado por inducción en$c$, el número de colores.

Casos base: Cuando$c = 1$, todos los bordes$K_r$ están coloreados con nuestro solo color, así que si lo dejamos$r = R(n_1) = n_1$, toda la gráfica es la$K_{n_1}$ totalidad de cuyos bordes han sido coloreados con color$1$.

También requeriremos$c = 2$ ser un caso base en nuestra inducción. Para probar este segundo caso base, realizamos una segunda prueba por inducción, esta vez en adelante$n_1 + n_2$. Para que la prueba sea más fácil de leer, llamaremos a los dos colores en cualquier color de$2$ borde rojo y azul, y si todos los bordes de un$K_i$ han sido coloreados con un solo color, simplemente lo llamaremos rojo$K_i$, o azul$K_i$.

Caso base para la segunda inducción: De hecho, probaremos muchos casos base todos a la vez. Ya que$n_1$ y$n_2$ son el número de vértices de una gráfica completa, debemos tener$n_1$,$n_2 ≥ 1$. A no$K_1$ tiene bordes, así que vacíamente sus bordes tienen el color que deseemos. Así si$n_1 = 1$ o$n_2 = 1$, tenemos$r = R(n_1, n_2) = 1$, ya que para cualquier$2$ coloración -borde-borde de$K_1$, hay un rojo$K_1$ y un azul$K_1$.

Paso inductivo para la segunda inducción: Comenzamos con la hipótesis inductiva. Que$k ≥ 2$ sea arbitrario. Supongamos que para cada$k_1, k_2 ≥ 1$ tal que$k_1 + k_2 = k$, hay algún entero$r = R(k_1, k_2)$ tal que para cualquier$2$ coloración -borde-bordes de los bordes de$K_r$, hay un subgrafo que es o un rojo$K_{k_1}$ o un azul$K_{k_2}$.

Dejemos$n_1$,$n_2 ≥ 1$ tal que$n_1 + n_2 = k + 1$. Si cualquiera$n_1 = 1$ o$n_2 = 1$, entonces este fue uno de nuestros casos base y la prueba está completa, por lo que podemos suponer que$n_1$,$n_2 ≥ 2$. Por lo tanto$n_1 −1$,$n_2 −1 ≥ 1$,, y$n_1 +n_2 −1 = k$. Ahora bien, por nuestra hipótesis inductiva, hay algún entero$r1 = R(n_1, n_2 − 1)$ tal que para cualquier$2$ coloración -borde de los bordes de$K_{r_1}$, hay una subgrafía que es o un rojo$K_{n_1}$ o un azul$K_{n_2−1}$. También podemos usar nuestra hipótesis inductiva para concluir que hay algún número entero$r_2 = R(n_1 − 1, n_2)$ tal que para cualquier$2$ coloración -borde de los bordes de$K_{r_2}$, hay un subgrafo que es rojo$K_{n_1−1}$ o azul$K_{n_2}$.

Eso lo afirmamos$R(n_1, n_2) ≤ r_1 + r_2$. Mostraremos esto demostrando que cualquier$2$ coloración -bordeada de los bordes de$K_{r_1}+r_2$ debe tener una subgrafía que sea roja$K_{n_1}$ o azul$K_{n_2}$.

Considera una gráfica completa sobre$r_1 +r_2$ vértices cuyos bordes han sido coloreados con rojo y azul. Elija un vértice$v$ y divida los vértices restantes en dos conjuntos:$u ∈ V_1$ si el borde$uv$ ha sido coloreado de rojo, y$u ∈ V_2$ si el borde$uv$ ha sido coloreado de azul. Dado que esta gráfica tiene

\[r_1 + r_2 = |V_1| + |V_2| + 1\]

vértices, debemos tener cualquiera$|V_1| ≥ r_2$, o$|V_2| ≥ r_1$.

Supongamos primero eso$|V_1| ≥ r_2$. Ya que$r_2 = R(n_1 − 1, n_2)$, el subgrafo cuyos vértices son los elementos de$V_1$ tiene un subgrafo que es un rojo$K_{n_1−1}$ o un azul$K_{n_2}$. En este último caso, esta subgrafía también está en nuestro original$K_{r_1+r_2}$ y ya terminamos. En el primer caso, la subgrafía cuyos vértices son los elementos de$V_1 ∪ \{v\}$ tiene un rojo$K_{n_1}$ y estamos hechos.

Supongamos ahora eso$|V_2| ≥ r_1$ (la prueba es similar). Ya que$r_1 = R(n_1, n_2 − 1)$, el subgrafo cuyos vértices son los elementos de$V_2$ tiene un subgrafo que es un rojo$K_{n_1}$ o un azul$K_{n_2−1}$. En el primer caso, esta subgrafía también está en nuestro original$K_{r_1+r_2}$ y ya terminamos. En este último caso, la subgrafía cuyos vértices son los elementos de$V_2 ∪ \{v\}$ tiene un azul$K_{n_2}$ y estamos hechos.

Por el Principio de Inducción Matemática$n_1$, para cada$n_2 ≥ 1$,, hay algún entero$r = R(n_1, n_2)$ tal que para cualquier coloración de los bordes de$K_r$, hay una subgrafía que es o un rojo$K_{n_1}$ o un azul$K_{n_2}$.

Esta segunda prueba por inducción completa la prueba del segundo caso base para nuestra inducción original en$c$, el número de colores. Ahora estamos listos para el paso inductivo para nuestra prueba original por inducción.

Paso inductivo: Comenzamos con la hipótesis inductiva. Que$m ≥ 2$ sea arbitrario. Supongamos que para cada$k_1, . . . , k_m ≥ 1$, hay un entero$r = R(k_1, . . . , k_m)$ tal que para cualquier mcoloración de los bordes de$K_r$, debe haber alguna$i ∈ \{1, . . . , m\}$ tal que$K_r$ tenga una subgrafía isomórfica a$K_{k_i}$, todos cuyos bordes han sido coloreados con color$i$.

Que$n_1, . . . , n_{m+1}$ sea arbitrario. Tome una gráfica completa sobre

\[r = R(n_1, . . . , n_{m−1}, R(n_m, n_{m+1}))\]

vértices, y colorea sus bordes con$m + 1$ colores. Considerar temporalmente los colores$m$ y$m + 1$ ser los mismos, dando como resultado una coloración de los bordes con$m$ colores. Por nuestra hipótesis inductiva, debe haber alguna$i ∈ \{1, . . . , m − 1\}$ tal que nuestra$K_r$ tenga una subgrafía isomórfica a$K_{n_i}$, todos cuyos bordes han sido coloreados con color$i$, o bien$K_r$ tiene una subgrafía isomórfica a$K_{R(n_m,n_{m+1})}$ todos cuyos bordes han sido coloreados con el$m^{\text{th}}$ color (donde este$m^{\text{th}}$ color es realmente la combinación de los colores$m$ y$m + 1$).

Si hay alguna$i ∈ \{1, . . . , m − 1\}$ tal que nuestra$K_r$ tiene una subgrafía isomórfica a$K_{n_i}$, todos cuyos bordes han sido coloreados con color$i$, entonces ya terminamos. Queda la posibilidad de que nuestro$K_r$ tenga una subgrafía isomórfica a$K_{R(n_m,n_{m+1})}$ todos cuyos bordes hayan sido coloreados con color$m$ o color$m + 1$. Pero según nuestro caso base para$c = 2$, esta gráfica debe tener una subgrafía isomórfica a$K_{n_m}$ todos cuyos bordes han sido coloreados con color$m$, o una subgrafía isomórfica a$K_{n_{m+1}}$ todos cuyos bordes han sido coloreados con color$m + 1$. Esto completa el paso inductivo.

Por el Principio de Inducción Matemática, para todos$c ≥ 1$ y tamaños fijos$n_1, . . . , n_c ≥ 1$, hay un entero$r = R(n_1, . . . , n_c)$ tal que para cualquier$c$ -coloración de los bordes de$K_r$, debe haber alguna$i ∈ \{1, . . . , c\}$ tal que$K_r$ tenga una subgrafía isomórfica a$K_{n_i}$ todos cuyos bordes tienen sido coloreado con color$i$.

Ejercicio$\PageIndex{3}$

Encuentra$R(2, 2, 3)$.
Encuentra$R(2, 4)$.
Encuentra una$2$ coloración de bordes$K_6$ que no tenga una de ninguno$K_4$ de los dos colores.

Ejercicio$\PageIndex{4}$

(Teorema de Schur) Let$c ∈ \mathbb{N}^+$, y let$N = R(3, . . . , 3)$ donde hay$c$ entradas (todas iguales a$3$). Si$\{A_1, A_2, . . . , A_c\}$ es alguna partición de$\{1, 2, . . . , N\}$ en$c$ subconjuntos, mostrar que algunos$A_i$ contienen tres enteros$x$,$y$, y$z$, tal que$x + y = z$.

[Pista: Los vértices de$K_N$ are$1, 2, . . . , N$. Pon color$i$ en cada borde$uv$ con$|u − v| ∈ A_i$. Si$u$,$v$,$w$ son los vértices de un triángulo monocromático de color$i$, con$u > v > w$, entonces$\{u − v, v − w, u − w\} ⊆ A_i$, y tenemos$(u − v) + (v − w) = u − w$.]

Search

Text Color

Text Size

Margin Size

Font Type