Saltar a contenido

Teoría de Ramsey

Introducción

Empecemos con un problema ya clásico:

Amigos y desconocidos

Cenando con mi amigo Martín en un restaurante, nos fijamos en una mesa de seis personas:

– ¿Qué te parece? –le dije–, ¿crees que son compañeros de trabajo? ¿O quizás son antiguos compañeros de colegio?

– ¡Y yo qué sé! –respondió Martín con su habitual brusquedad–. No tengo ni idea. Pero de una cosa sí estoy seguro: en esa mesa hay 3 personas que o bien se conocían anteriormente o bien no se conocían hasta esta noche.

– ¿Y por qué estás tan seguro?

– ¡Pues porque \(R(3,3) = 6\)!

¿Sabrías demostrar lo que dice Martín? Aquella noche yo no entendí nada, así que me puse a aprender algo de teoría de Ramsey, nombrada así por el matemático Frank Ramsey, que en su artículo de 1928 On a Problem of Formal Logic demostró un teorema que dio origen a esta rama de la combinatoria. Veamos ahora en qué consiste con los siguientes problemas.

Frank P. Ramsey

El orden es inevitable

Existe un extraño fenómeno en matemáticas que suele expresarse con la frase el orden es inevitable. Aunque ocurre en muchas áreas distintas, inicialmente se descubrió en el contexto de la teoría de grafos. Como sabrás, un grafo es un objeto matemático formado por vértices (también llamados nodos) y aristas (también llamadas conexiones) que conectan pares de vértices.

  1. Un grafo completo es aquel en el que cada par de vértices está unido por una arista. Al grafo completo de \(n\) vértices lo llamamos \(K_n\).

    Los grafos completos K3, K4 y K5

    1. ¿Cuántas aristas tiene \(K_4\)? ¿Y \(K_5\)?
    2. Encuentra una fórmula para el número de aristas en \(K_n\) y comprueba que funciona en los primeros 5 casos.
    3. ¿Cuántas aristas tiene \(K_{20}\)?
    4. ¿Cuál es una forma sistemática de dibujar todas las aristas y asegurarte de que no has olvidado ninguna?
    Solución
    1. Hay una arista por cada pareja de vértices. Por lo tanto, \(K_4\) tiene \({4 \choose 2} = 6\) aristas y \(K_5\) tiene \({5 \choose 2} = 10\) aristas.
    2. \(n \choose 2\)
    3. \(20 \choose 2\)
    4. Dibujar todas las aristas que salen del vértice 1, luego todas las que salen del vértice 2 (menos la que llega a 1, que ya está dibujada), luego todas las que salen del vértice 3 (menos las que llegan a 1 y a 2, que ya están dibujadas), etcétera.

  2. Una 2-coloración de las aristas de un grafo completo es una coloración en la que cada arista usa uno de dos colores.

    2-coloración de K3

    ¿Cuántas maneras diferentes hay de 2-colorear las aristas de \(K_n\)?

    Solución

    Si un grafo tiene \(a\) aristas, hay \(2^a\) 2-coloraciones posibles, ya que cada arista se puede colorear de dos colores. Por lo tanto, el número de 2-coloraciones de \(K_n\) es \(2^{n \choose 2}\).

  3. Decimos que un cierto subgrafo de un grafo coloreado es monocromático si todas las aristas de ese subgrafo son del mismo color.

    Esta 2-coloración de K4 contiene un triángulo monocromático

    1. ¿Puedes 2-colorear las aristas de \(K_4\) para que no haya triángulos monocromáticos?
    2. ¿Puedes hacer lo mismo con \(K_5\)?
    Solución
    1. Sí. Una forma es colorear el cuadrado exterior de un color y las dos diagonales del otro.
    2. Sí. Una forma es colorear el pentágono exterior de un color y las cinco diagonales, que forman una estrella, del otro.

  4. Juega con tus compañeros a este juego: Por turnos, coloread las aristas de \(K_6\) de vuestro color. Quien forme un triángulo monocromático, pierde. ¿Qué observas? ¿Es posible el empate?

    Solución

    Puedes clicar en el grafo para obtener una nueva 2-coloración. Parece que siempre se forma algún triángulo monocromático, por lo que es imposible empatar…

  5. Probablemente has visto que siempre se forma un triángulo monocromático. Pero hay \(2^{6 \choose 2} = 2^{15} = 32 768\) maneras posibles de 2-colorear las aristas de \(K_6\), y seguro que no has intentado ni siquiera el 1 % de todas ellas. Así que cabría la posibilidad de que simplemente no hayáis podido encontrar una coloración sin triángulos monocromáticos… ¿O no? ¿Puedes demostrar que no existe tal coloración? Es decir, ¿puedes demostrar que, sin importar cómo 2-colorees las aristas, siempre habrá un triángulo monocromático?

    Solución

    Elige un vértice \(v\) cualquiera. De este vértice salen cinco aristas, por lo que seguro que habrá tres del mismo color. Sigue esas tres aristas del mismo color hasta los vértices correspondientes (\(x\), \(y\), \(z\)) y observa el triángulo que forman. Hay dos opciones:

    • Si el triángulo es monocromático (como en la imagen), ya hemos terminado.
    • Si el triángulo no es monocromático, contiene aristas de ambos colores. Concretamente, contiene al menos una arista del color de las tres aristas que conectaban con el vértice \(v\). Por lo tanto, se forma un triángulo monocromático.

    Demostración de que R(3, 3) = 6

  6. Considera ahora un \(K_{12}\). Basándote en el problema anterior, ¿puedes demostrar que hay al menos dos triángulos monocromáticos? (No necesariamente del mismo color.)

    Solución

    Separa los 12 vértices en dos conjuntos de 6 vértices. Por lo que hemos visto, cada conjunto contiene al menos un triángulo monocromático, por lo que \(K_{12}\) contiene al menos dos.

  7. Demuestra ahora que cualquier 2-coloración de \(K_{12}\) contiene al menos tres triángulos monocromáticos.

    Solución

    Empieza como antes. Los dos triángulos monocromáticos contienen 6 de los vértices. Los otros 6 forman un \(K_6\) que contiene al menos otro triángulo monocromático.

  8. ¿Puedes demostrar que una 2-coloración de las aristas de \(K_{12}\) tiene al menos dos triángulos monocromáticos del mismo color?

    Pista

    Busca tantos triángulos monocromáticos como puedas y después trata de encontrar dos del mismo color.

    Solución

    Ya hemos visto que contiene tres triángulos monocromáticos, por lo que necesariamente habrá dos del mismo color.

  9. Ahora apuntemos más alto e intentemos encontrar no solo un triángulo monocromático (es decir, un \(K_3\)) sino un \(K_4\) monocromático. ¿Puedes demostrar que una 2-coloración de las aristas de \(K_{27}\) necesariamente contiene un \(K_4\) monocromático?

    Pista

    Usa el argumento del problema 5 dos veces.

    Solución

    Elegimos un vértice \(v\) cualquiera. De \(v\) salen 26 aristas, de las cuales al menos 13 son del mismo color, digamos que azul. Sea \(w\) uno cualquiera de los 13 vértices correspondientes. De las doce aristas que unen \(w\) con cada uno de los otros 12 vértices, habrá al menos 6 del mismo color, cuyos vértices nombramos \(u_1\), \(\dots\), \(u_6\). Ahora tenemos dos opciones: que el color de las aristas \(w u_i\) sea azul, como las 13 del principio, o rojo.

    Si son de color azul, buscamos una arista \(u_i u_j\) azul. Entonces, el \(K_4\) formado por los vértices \(\{v, w, u_i, u_j\}\) es monocromático azul. Si no hay ninguna arista \(u_i u_j\) azul, entonces todas son rojas y tenemos un \(K_4\) monocromático rojo.

    Si, por el contrario, las aristas \(w u_i\) son rojas, nos fijamos en el \(K_6\) formado por los vértices \(\{u_1, \dots, u_6\}\). Por ser \(R(3,3)=6\), sabemos que ese grafo contiene algún \(K_3\) monocromático. Si es azul, podemos añadir el vértice \(v\) para tener un \(K_4\) monocromático azul. Si es rojo, podemos añadir el vértice \(w\) para tener un \(K_4\) monocromático rojo. \(\Box\)

Resuélvelo al azar

Acabamos de ver un resultado importante en teoría de Ramsey:

Cualquier 2-coloración de \(K_n\) contiene al menos un \(K_3\) monocromático cuando \(n \geq 6\). Esto no es cierto para \(n < 6\).

Para demostrarlo hemos usado un argumento bastante sencillo que usa el principio del palomar y que permite encontrar un triángulo monocromático. Ahora veremos otro resultado, que demostraremos mediante un argumento probabilístico y que solo demostrará la existencia de la estructura que buscamos. Veremos que existe alguna 2-coloración de \(K_{11}\) que no contiene ningún \(K_5\) monocromático, sin necesidad de mostrar cuál es esa 2-coloración. Esta misma técnica servirá para demostrar, por ejemplo, que existe alguna 2-coloración de \(K_{100}\) que no contiene ningún \(K_{10}\) monocromático. Piensa que \(K_{100}\) es enorme, ¡y el número de 2-coloraciones posibles es aún muchísimo mayor! Así que esta técnica nos ofrece un gran atajo para atacar este tipo de problemas.

  1. ¿Cuántas maneras hay de 2-colorear las aristas de un \(K_{11}\)?

    Solución

    Hay una arista por cada pareja de vértices, es decir, hay \(11 \choose 2\) aristas. Así, el número de 2-coloraciones es

    \[ 2^{11 \choose 2} = 2^{55} \]

  2. ¿Cuántas maneras hay de 2-colorear las aristas de \(K_{11}\) de tal manera que el subgrafo inducido por los vértices \(\{1,2,3,4,5\}\) sea un \(K_5\) monocromático? ¿Qué fracción de todas las coloraciones representan?

    Solución

    De las \(11 \choose 2\) aristas de \(K_{11}\), \(5 \choose 2\) pertenecen a \(K_5\). Así, el número buscado es el número de formas de 2-colorear esas \({11 \choose 2} - {5 \choose 2}\) aristas multiplicado por 2, los colores posibles para el \(K_5\).

    \[ 2 \times 2^{{11 \choose 2} - {5 \choose 2}}= 2 \times 2^{55-10} = 2 \times 2^{45} = 2^{46} \]

    Estas coloraciones son \(\frac{2^{46}}{2^{55}} = \frac{1}{2^9}\) del total.

  3. ¿En qué fracción de las 2-coloraciones de las aristas de \(K_{11}\) el subgrafo inducido por los vértices \(\{4,5,6,7,8\}\) es monocromático? ¿En qué fracción son monocromáticos \(\{1,2,3,4,5\}\) o \(\{4,5,6,7,8\}\) o ambos?

    Solución

    Por simetría, las mismas que antes. Por el principio de inclusión-exclusión, las 2-coloraciones que buscamos son las que contienen \(\{1,2,3,4,5\}\) (que hemos visto que son \(2^{46}\)) más las que contienen \(\{4,5,6,7,8\}\) monocromático (las mismas, por simetría) menos las que contienen ambos subgrafos monocromáticos. Es decir,

    \[ 2^{46} + 2^{46} - 2 \times 2^{{11 \choose 2} - {8 \choose 2}} = 2 \times 2^{46} - 2 \times 2^{55-28} = 2^{47} - 2^{28} \]

    Estas coloraciones son \(\frac{2^{47} - 2^{28}}{2^{55}} = \frac{2^{19} - 1}{2^{27}}\) del total.

  4. ¿Cuántos \(K_5\) hay en \(K_{11}\)? Es decir, ¿cuántos grupos de 5 vértices hay?

    Solución
    \[ {11 \choose 5} = 462 \]

  5. Da una cota superior para la fracción de 2-coloraciones de \(K_{11}\) que contienen al menos un \(K_5\) monocromático.

    Solución

    Sabemos que el número de 2-coloraciones de \(K_{11}\) en las que el subgrafo inducido por los vértices \(\{1,2,3,4,5\}\) es monocromático es de \(2^{46}\). Pero este resultado no depende de cuáles son los 5 vértices elegidos. Dado que hay \({11 \choose 5} = 462\) maneras de elegir 5 vértices, habrá como mucho \(462 \times 2^{46}\) 2-coloraciones con algún \(K_5\) monocromático. Esto es una sobreestimación, ya que estamos contando muchas 2-coloraciones más de una vez: todas aquellas que contienen dos o más \(K_5\) monocromáticos.

    Por lo tanto, una cota superior para la fracción de 2-coloraciones de \(K_{11}\) que contienen al menos un \(K_5\) monocromático es

    \[ \frac{462 \times 2^{46}}{2^{55}} = \frac{462}{2^{9}} = \frac{231}{2^{8}} = \frac{231}{256} \approx 0{,}902 \]

  6. Muestra que hay alguna 2-coloración de \(K_{11}\) que no contiene ningún \(K_5\) monocromático.

    Solución

    Acabamos de ver que la fracción de 2-coloraciones con algún \(K_5\) monocromático es menor que 1. Por lo tanto, ha de existir alguna 2-coloración que no contenga ningún \(K_5\) monocromático.

  7. Adapta este argumento para demostrar que existe alguna coloración de \(K_{100}\) sin ningún \(K_{10}\) monocromático.

  8. Generaliza este argumento. Determina una relación entre \(n\) y \(k\) que asegure que \(K_n\) no contiene un \(K_k\) monocromático.

    Solución

    • Número de aristas de \(K_n\):

      \[ {n \choose 2} \]

    • Número de 2-coloraciones de \(K_n\):

      \[ 2^{n \choose 2} \]

    • Número de 2-coloraciones de \(K_n\) que contienen al menos un \(K_k\) monocromático:

      \[ 2 \cdot 2^{{n \choose 2}-{k \choose 2}} \]

    • Número de \(K_k\) contenidos en \(K_n\):

      \[ n \choose k \]

    • Cota superior para el número de 2-coloraciones con al menos un \(K_k\) monocromático:

      \[ {n \choose k} 2 \cdot 2^{{n \choose 2}-{k \choose 2}} \]

    Si esta cota superior da un número menor que el total de 2-coloraciones, entonces es seguro que existe alguna 2-coloración que no contiene ningún \(K_k\) monocromático. Por lo tanto, la condición se puede expresar como

    \[ {n \choose k} 2 \cdot 2^{{n \choose 2}-{k \choose 2}} < 2^{n \choose 2} \]

    Simplificando,

    \[ {n \choose k} 2^{1-{k \choose 2}} < 1 \]

    Ahora puedes tratar de demostrar que esta desigualdad se cumple si \(n \leq 2^{k/2}\), por lo que \(2^{k/2} \leq R(k,k)\) (problema 6).

    Este es el famoso argumento probabilístico planteado por Erdős en 1947 en su artículo Some remarks on the theory of graphs.

    Paul Erdős (1913-1996)

Números de Ramsey

El número de Ramsey \(R(\textcolor{blue}{m}, \textcolor{red}{n})\) es el número mínimo de vértices que ha de tener un grafo completo para que cualquiera de sus 2-coloraciones contenga un \(\textcolor{blue}{K_m}\) monocromático azul o un \(\textcolor{red}{K_n}\) monocromático rojo. Si interpretamos el color azul como conocerse y el rojo como no conocerse, vemos que \(R(3, 3) = 6\), tal y como Martín me dijo. Más adelante, hemos visto que algunas 2-coloraciones de \(K_{11}\) no contienen ningún \(K_5\) monocromático, es decir, que \(R(5, 5) > 11\).

Esta definición se puede generalizar para coloraciones con más de dos colores:

El número de Ramsey \(R(n_1, n_2, \dots, n_k)\) es el número mínimo de vértices de un grafo completo tal que cualquier \(k\)-coloración suya contenga un \(K_{n_i}\) monocromático de color \(c_i\) para algún \(i\) entre 1 y \(k\).

  1. Halla \(R(2,5)\).

  2. Halla \(R(2,n)\).

    Solución

    Dada una 2-coloración de \(K_n\), hay dos posibilidades: si todas las aristas son rojas, el grafo contiene un \(K_n\) monocromático rojo (el propio grafo); si no todas son rojas, el grafo contiene un \(K_2\) monocromático azul. Por lo tanto, \(R(2,n) \leq n\).

    Por otro lado, si coloreamos todas las aristas de \(K_{n-1}\) de color rojo, no habrá ni un \(K_n\) rojo ni un \(K_2\) azul, así que \(R(2,n) > n-1\).

    Por lo tanto, \(R(2,n)=n\) para todo \(n\).

  3. ¿Es cierto que \(R(m,n) = R(n,m)\) para \(m\), \(n\) cualesquiera? ¿Por qué?

    Solución

    Sí, es cierto.1 Supongamos que \(R(m,n) > R(n,m)\) y construyamos todas las 2-coloraciones posibles del grafo completo con \(R(n,m)\) vértices. Estas se pueden agrupar en parejas simétricas, es decir, con colores invertidos. Si una 2-coloración contiene un \(K_n\) azul o un \(K_m\) rojo, su pareja contiene un \(K_n\) rojo o un \(K_m\) azul. Pero, por construcción, todas las 2-coloraciones contienen un \(K_n\) azul o un \(K_m\) rojo, y como todas son la pareja de alguna otra, todas contienen un \(K_n\) rojo o un \(K_m\) azul. Por lo tanto, nuestra hipótesis es falsa y tenemos que \(R(m,n) \leq R(n,m)\). Podemos hacer el argumento análogo para llegar a \(R(m,n) \geq R(n,m)\), que junto a lo anterior demuestran que ambos números son iguales.

  4. En un campamento de verano hay 17 estudiantes. Cada pareja de estudiantes se puede clasificar en función de si son amigos, si solo se conocían o si nunca se habían visto antes. Demuestra que hay tres alumnos tales que todos son amigos o todos se conocían o ninguno se había visto antes. Expresa esto como una proposición sobre números de Ramsey.

    Solución

    Queremos demostrar que cualquier 3-coloración de \(K_{17}\) contiene un triángulo monocromático. Elegimos un vértice \(v\) cualquiera, del que salen 16 aristas. Necesariamente, habrá 6 aristas del mismo color. Ahora tenemos dos opciones: si entre los 6 vértices correspondientes hay alguna arista de ese mismo color, se forma un triángulo monocromático. Si no hay ninguna arista de ese color, es que ese \(K_6\) usa únicamente los otros dos colores. Pero como \(R(3,3)=6\), necesariamente contendrá algún triángulo monocromático. \(\Box\)

    Hemos demostrado que \(R(3,3,3) \leq 17\). De hecho, \(R(3,3,3)=17\), pero para demostrarlo hace falta mostrar una 3-coloración de \(K_{16}\) sin triángulos monocromáticos.1 La siguiente figura muestra una.

    3-coloración de K16 sin triángulos monocromáticos

  5. Diez personas han quedado atrapadas en un vagón de metro.

    1. Demuestra que o bien hay 3 que se conocen o bien hay 4 que no se conocen entre sí.
    2. Demuestra que esto podría no ocurrir si hubiera solo 8 personas.
    3. Expresa estos resultados como números de Ramsey.
    Solución

    1. Veamos que cualquier 2-coloración de \(K_{10}\) contiene un \(K_3\) azul o un \(K_4\) rojo. Dado que \(R(3,3)=6<10\), sabemos que \(K_{10}\) contiene un \(K_3\) azul o un \(K_3\) rojo. En el primer caso, ya hemos terminado. A partir de ahora, supongamos que el grafo no contiene ningún \(K_3\) azul. Elegimos un vértice \(v\) cualquiera, del que salen 9 aristas, al menos 5 de las cuales del mismo color.

      Supongamos, en primer lugar, que son azules. Entonces, los 5 vértices correspondientes forman un \(K_5\) en el que no puede haber ninguna arista azul (ya que estamos suponiendo que el grafo original no contiene ningún \(K_3\) azul). Por lo tanto, todas son rojas y tenemos un \(K_4\) rojo.

      Supongamos ahora que la mayoría de aristas del mismo color que salen de \(v\) son rojas. Si son 6, los vértices correspondientes forman un \(K_6\) que ha de contener un \(K_3\) rojo (ya que no lo contiene azul), y hemos terminado. Si son solo 5 aristas rojas, entonces hay 4 azules, y entre los vértices correspondientes todas las aristas han de ser rojas, porque si no contendrían un \(K_3\) azul. Por lo tanto, habrá un \(K_4\) rojo, y hemos terminado.

      Este argumento es un caso concreto del que se verá más adelante y que sirve para demostrar el teorema de Ramsey.

    2. Numeramos del 1 al 8 los vértices de \(K_8\). Unimos con aristas rojas los vértices a distancia 1 o 2, suponiendo que el vértice siguiente al 8 es el 1. Unimos con aristas azules el resto de parejas de vértices.

      R(3, 4) > 8. Ejemplo de 2-coloración de K8 sin K3 azul ni K4 rojo.

    3. \(8 < R(3,4) \leq 10\).

Teorema de Ramsey

Para cualesquiera \(m, n \geq 2\), el número de Ramsey \(R(m,n)\) es finito.

Demostraremos por inducción la siguiente desigualdad, que implica que si \(R(m-1,n)\) y \(R(m,n-1)\) son finitos, \(R(m,n)\) también lo es:

\[ R(m,n) \leq R(m-1,n) + R(m,n-1) \]

La idea es construir un grafo completo con \(R(m-1,n) + R(m,n-1)\) vértices y demostrar que necesariamente contiene o bien un \(K_m\) monocromático azul o bien un \(K_n\) monocromático rojo. Esto desmostrará la desigualdad.

  1. (Caso base) Demuestra que \(R(m,2)\) y \(R(2,m)\) son finitos.
  2. Elige un vértice cualquiera \(v\) y clasifica los vértices restantes en dos conjuntos \(A\) y \(R\) en función de si la arista que los conecta con \(v\) es azul o roja, respectivamente. Halla \(|A| + |R|\).
  3. Supongamos que \(|A| \geq R(m-1,n)\).
    1. ¿Qué podemos deducir del grafo completo formado por los vértices de \(A\)?
    2. ¿Qué podemos deducir del grafo completo formado por los vértices de \(A\) y \(v\)?
  4. Supongamos que \(|A| < R(m-1,n)\), es decir, \(|A| \leq R(m-1,n) - 1\).
    1. Demuestra que \(|R| \geq R(m,n-1)\).
    2. ¿Qué podemos deducir del grafo completo formado por los vértices de \(R\)?
    3. ¿Qué podemos deducir del grafo completo formado por los vértices de \(R\) y \(v\)?
Demostración completa
  1. Caso base. Hemos visto que \(R(m,2) = R(2,m) = m < \infty\).

  2. Paso inductivo. Suponemos que \(s=R(m-1,n)\) y \(t=R(m,n-1)\) son finitos. Construimos el grafo completo \(K_{s+t}\) y elegimos un vértice \(v\) cualquiera. Clasificamos los \({s+t-1}\) vértices restantes en dos conjuntos \(A\) y \(R\) en función de si la arista que los conecta con \(v\) es azul o roja, respectivamente, de manera que \({|A|+|R| = s+t-1}\). Ahora tenemos dos casos posibles, \(|A| \geq s\) o \(|A| \leq s-1\).

    1. Dado que \(|A| \geq s=R(m-1,n)\), sabemos que el grafo formado por todos los vértices de \(A\) contiene o bien un \(K_{m-1}\) monocromático azul o bien un \(K_n\) monocromático rojo. En el primer caso, el \(K_{m-1}\) azul junto a \(v\) forma un \(K_m\) monocromático azul, ya que todas las aristas que unen sus vértices con \(v\) son azules, por la construcción de \(A\), y hemos terminado. En el segundo caso, el grafo original ya contiene un \(K_n\) monocromático rojo, y hemos terminado.

    2. Tenemos dos relaciones,

      \[ \begin{align*} |A| &\leq s-1 \\ |A|+|R| &= s+t-1 \end{align*} \quad\Rightarrow\quad \begin{align*} 0 &\leq s - 1 - |A| \\ |R| - t &= s - 1 - |A| \end{align*} \]

      Por lo tanto, \(|R| \geq t\) y tenemos una situación análoga a la anterior. \(\Box\)

Problemas

  1. Teorema de Schur. Para cualquier \(k \geq 2\), existe \(n>3\) tal que en cualquier \(k\)-coloración del conjunto \(\{1,2,3,\dots,n\}\) existen tres números (no necesariamente distintos) \(x\), \(y\), \(z\) del mismo color tales que \(x+y=z\).

    1. Demuestra el teorema de Schur para \(k=2\).

    2. Demuestra el teorema de Schur para cualquier \(k\).

      Pista 1

      Construye el grafo completo con \(n = R(\overbrace{3,3,\dots,3}^k)\) vértices.

      Pista 2

      Para cualquier coloración \(c:[n] \to [k]\), colorea la arista \(\{i,j\}\) del color \(c(|i-j|)\).

      Solución

      Construimos el grafo completo \(K_n\), con \(n = R(\overbrace{3,3,\dots,3}^k)\), y numeramos sus vértices desde \(1\) hasta \(n\). Elegimos una \(k\)-coloración cualquiera de \(\{1,2,3,\dots,n\}\). Ahora coloreamos el grafo, asignando a la arista que une los vértices \(i\),\(j\) el color que corresponde al número \(|i-j|\). Por construcción, el grafo contendrá algún triángulo monocromático. Sean \(i<j<k\) los vértices del triángulo y sean \(x=j-i\), \(y=k-j\), \(z=k-i\). Entonces, los números \(x\), \(y\), \(z\) son del mismo color, y además \(x+y=(j-i)+(k-j)=k-i=z\). \(\Box\)

  2. Demuestra la siguiente desigualdad:

    \[ R(m,n) \leq {{m+n-2} \choose {m-1}} \]
    Pista

    Usa inducción y la desigualdad \(R(m,n) \leq R(m-1,n) + R(m,n-1)\).

    Solución
    • Caso base: La desigualdad se cumple cuando \(m=n=2\), ya que \(R(2,2) = 2\) y \({{m+n-2} \choose {m-1}} = {{2+2-2} \choose {2-1}} = {2 \choose 1} = 2\).

    • Paso inductivo: Hemos demostrado previamente que \(R(m,n) \leq R(m-1,n) + R(m,n-1)\). Entonces, suponiendo que la desigualdad que queremos demostrar es válida para \(R(m-1,n)\) y para \(R(m,n-1)\), tenemos que

      \[ \begin{align*} R(m,n) &\leq R(m-1,n) + R(m,n-1) \\ &\leq {{(m-1)+n-2} \choose {(m-1)-1}} + {{m+(n-1)-2} \choose {m-1}} \\ &= {{m+n-3} \choose {m-2}} + {{m+n-3} \choose {m-1}} \\ &= {{m+n-2} \choose {m-1}} \end{align*} \]

      El último paso es una aplicación directa de la regla de Pascal.

  3. Demuestra que \(K_7\) contiene 4 triángulos monocromáticos.

    1. Definimos un biángulo como una tripleta de vértices \((a,b,c)\) tales que la arista \(ab\) es azul y la arista \(bc\) es roja. Al vértice \(b\) le llamamos la punta del biángulo. Calcula el número máximo de biángulos de los que un vértice dado de \(K_7\) puede ser punta.
    2. Calcula el número máximo de biángulos en \(K_7\).
    3. ¿Cuántos biángulos aporta un triángulo no monocromático?
    4. ¿Cuántos triángulos hay en \(K_7\)?
    5. Termina la demostración.
    Solución
    1. De un vértice cualquiera de \(K_7\) salen 6 aristas. Si \(r\) son rojas, hay \(r(6-r)\) biángulos, por lo que el número máximo de biángulos es \(9\), que se consigue cuando \(r=3\).
    2. Si cada vértice puede ser punta de \(9\) biángulos, en \(K_7\) puede haber un máximo de \(7 \times 9 = 63\) biángulos.
    3. Un triángulo no monocromático aporta exactamente \(2\) biángulos.
    4. Hay \({7 \choose 3} = 35\) triángulos.
    5. Si el número máximo de biángulos es de \(63\), el número máximo de triángulos no monocromáticos es de \(31\). Como hay \(35\) triángulos posibles, tendrá que haber al menos \(35-31=4\) triángulos monocromáticos.

  4. Sea \(R_k = R(\overbrace{3,3,\dots,3}^k)\). Demuestra que \(R_k \leq \lceil k!e \rceil\).

    1. Demuestra que \(R_k \leq (R_{k-1}-1)k+2\).
    2. Si \(a_1 = 3\), \(a_k = (a_{k-1}-1)k+2\) y \(a_k = k! \lambda_k\), halla una expresión para \(\lambda_k\).
    3. Sabiendo que \(e = \sum_0^\infty \frac{1}{i!}\), completa la demostración.
    Solución

    Podemos generalizar el argumento que hemos usado anteriormente para demostrar que \(R(3,3,3) \leq 17\). Sea \({R_k = R(\overbrace{3,3,\dots,3}^k)}\). Entonces, \(R_1 = R(3) = 3 \leq \lceil 1!e \rceil = 3\). Ahora, sea una \(k\)-coloración del grafo completo con \({(R_{k-1}-1)k+2}\) vértices y \(v\) un vértice suyo cualquiera. De \(v\) salen \((R_{k-1}-1)k+1\) aristas, de las cuales habrá necesariamente \(R_{k-1}\) del mismo color, digamos azul. Si el subgrafo generado por los \(R_{k-1}\) vértices correspondientes contiene alguna arista azul, se forma un triángulo monocromático azul. Si no es así, tenemos un grafo completo con \(R_{k-1}\) vértices coloreado con los \(k-1\) colores restantes, por lo que seguro que contiene un triángulo monocromático. Por inducción, queda demostrado que \(R_k \leq (R_{k-1}-1)k+2\).

    Definamos ahora la recurrencia

    \[ \begin{cases} \begin{align*} a_1 &= 3 \\ a_k &= k (a_{k-1} - 1) + 2 \quad \text{para } k \geq 2 \end{align*} \end{cases} \]

    Tomando \(a_k = k! \lambda_k\), tenemos

    \[ \lambda_k - \lambda_{k-1} = \frac{-k+2}{k!} = -\frac{1}{(k-1)!} + \frac{2}{k!} \]

    Sumando desde \(2\) hasta \(k\), algunos términos se cancelan, y se obtiene

    \[ \begin{align*} \lambda_k - \lambda_1 &= \overbrace{\frac{2}{k!} -\frac{1}{(k-1)!}}^{\lambda_k-\lambda_{k-1}} + \overbrace{\frac{2}{(k-1)!} -\frac{1}{(k-2)!}}^{\lambda_{k-1}-\lambda_{k-2}} + \cdots + \overbrace{\frac{2}{2!} - \frac{1}{1!}}^{\lambda_2-\lambda_1} \\ &= \frac{1}{k!} + \sum_{i=0}^k \frac{1}{i!} - \frac{2}{1!} - \frac{1}{0!} \end{align*} \]

    Como \(a_1 = 3 = 1!\lambda_1\), entonces \(\lambda_1=3\), \(\lambda_k = \frac{1}{k!} + \sum_0^k \frac{1}{i!}\) y \(a_k=1+k!\sum_0^k \frac{1}{i!}\). El segundo término de esta última expresión se aproxima claramente a \(k!e\) para \(k\) grande. Si escribimos la diferencia \(\delta = k!e - k!\sum_0^k \frac{1}{i!}\), tenemos que

    \[ \begin{align*} \delta &= k! \left(\frac{1}{(k+1)!} + \frac{1}{(k+2)!} + \cdots\right) \\ &= \frac{1}{k+1} + \frac{1}{(k+1)(k+2)} + \cdots \\ &< \frac{1}{k+1} + \frac{1}{(k+1)^2} + \cdots \\ &= \frac{1}{k+1} \frac{1}{1-\frac{1}{k+1}} = \frac{1}{k} \end{align*} \]

    Entonces, \(0 < \delta < 1\) para \(k \geq 1\), y \(\lfloor k!e \rfloor = \lfloor k!\sum_0^k \frac{1}{i!} + \delta \rfloor = k!\sum_0^k \frac{1}{i!}\), por ser este último entero. Finalmente, como \(R_k \leq a_k = 1 + k!\sum_0^k \frac{1}{i!} = 1 + \lfloor k!e \rfloor\), \(R_k \leq \lceil k!e \rceil\), como queríamos demostrar. \(\Box\)

    Esta demostración es la dada por R. C. Walker en su artículo de 1976 A graph-colouring theorem.

  5. Demuestra que \(R(m,m) < 4^m\). Es decir, que en cualquier 2-coloración de \(K_{4^m}\) puedes hallar un \(K_m\) monocromático. Por ejemplo, puedes encontrar un \(K_5\) monocromático en una 2-coloración de \(K_{4^5}=K_{1024}\).

    Solución 1

    Numeremos los vértices de \(K_{2^{2m}}\). Llamemos \(v_1\) al primero. De las \(2^{2m}-1\) aristas que salen de \(v_1\), necesariamente habrá \(2^{2m-1}\) del mismo color. Sea \(A_1\) el conjunto de los vértices correspondientes a esas aristas, y \(v_2\) el vértice de menor número. De \(v_2\) salen \(2^{2m-1}-1\) aristas, de las cuales al menos \(2^{2m-2}\) del mismo color. Sea \(A_2 \subset A_1\) el conjunto de los vértices correspondientes a esas aristas, y \(v_3\) el de menor número. Siguiendo del mismo modo, obtenemos una secuencia de vértices \(v_1\), \(\dots\), \(v_{2m}\) y una secuencia anidada de conjuntos \(A_1 \supset \dots \supset A_{2m}\) tales que \(v_i \in A_{i-1}\) para todo \(i\) y todas las aristas desde \(v_i\) hasta \(A_i\) son del mismo color. Así, el color de la arista entre \(v_i\) y \(v_j\) depende únicamente del menor entre \(i\) y \(j\) y por lo tanto podemos elegir al menos \(m\) vértices de entre \(\{v_1, \dots, v_{2m}\}\) tales que todas las aristas entre ellos son del mismo color. \(\Box\)

    Cada vértice vi está coloreado del mismo color que las aristas que salen de él hacia todos los vértices vj con j > i. Siempre podremos elegir m vértices que formarán un Km monocromático.

    Solución 2

    Usaremos la desigualdad que hemos demostrado anteriormente, \(R(m,n) \leq {{m+n-2} \choose {m-1}}\). Si \(m=n\), entonces \(R(m,m) \leq {{2m-2} \choose {m-1}}\) y podemos acotar el número combinatorio.

    \[ \begin{align*} {{2m-2} \choose {m-1}} &= \frac{(2m-2)!}{(m-1)!(m-1)!} \\ &= \frac{(2m-2)!!(2m-3)!!}{(m-1)!(m-1)!} \\ &= \frac{2^{m-1} \cancel{(m-1)!}(2m-3)!!}{\cancel{(m-1)!}(m-1)!} \\ &= 2^{m-1} \frac{2m-3}{m-1} \frac{2m-5}{m-2} \cdots \frac{3}{2} \frac{1}{1} \\ &= 2^{m-1} \left(2-\frac{1}{m-1}\right) \left(2-\frac{1}{m-2}\right) \cdots \left(2-\frac{1}{2}\right) \left(2-\frac{1}{1}\right) \\ &\leq 2^{m-1} 2^{m-1} = 4^{m-1} \end{align*} \]

    Por lo tanto, \(R(m,m) \leq 4^{m-1} < 4^m\). \(\Box\)

  6. Demuestra que \(2^{k/2} < R(k,k)\) para \(k \geq 3\).

    Pista

    Parte de la conclusión del argumento probabilístico del ejercicio 19. Es decir, sabemos que si

    \[ {n \choose k} 2^{1-{k \choose 2}} < 1 \]

    entonces existe alguna 2-coloración de \(K_n\) que no contiene ningún \(K_k\) monocromático.

    Solución

    Por un lado,

    \[ {n \choose k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1) \cdots (n-k+1)}{k!} < \frac{n^k}{k!} \]

    Entonces, si \(n \leq 2^\frac{k}{2}\),

    \[ \frac{n^k}{k!} \leq \frac{2^{\frac{k^2}{2}}}{k!} = \frac{2^{\frac{k(k-1)}{2}-1+\frac{k}{2}+1}}{k!} = 2^{{k \choose 2}-1}\frac{2^{\frac{k}{2}+1}}{k!} < 2^{{k \choose 2}-1} \]

    donde el último paso se justifica porque \(2^{\frac{k}{2}+1} < k!\) para \(k \geq 3\). Juntando todo, se cumple la condición

    \[ {n \choose k} < 2^{{k \choose 2}-1} \]

    y por lo tanto \(n>2^\frac{k}{2}\) si queremos asegurar la existencia de algún \(K_k\) monocromático. Es decir, \(R(k,k) > 2^\frac{k}{2}\).\(\Box\)

  7. Colorea cada punto de coordenadas enteras del plano de rojo o de azul. Demuestra que existe un rectángulo con sus lados paralelos a los ejes de coordenadas y con sus cuatro vértices del mismo color.

    Solución

    Tomemos las nueve ternas de puntos \((x,0)\), \((x,1)\), \((x,2)\), para \(0 \leq x \leq 8\). Dado que usamos dos colores, hay \(2^3=8\) maneras distintas de colorear una tripleta de números. Por lo tanto, entre esas 9 tripletas habrá dos con los mismos colores. En cualquier tripleta hay al menos dos puntos del mismo color. Esos dos puntos de cada una de las dos tripletas forman un rectángulo con todos sus vértices del mismo color.

    Haz clic para colorear. Siempre habrá al menos dos columnas con la misma coloración.

Referencias

  1. Greenwood, R. E., & Gleason, A. M. (1955). Combinatorial Relations and Chromatic Graphs. Canadian Journal of Mathematics, 7, 1–7. doi:10.4153/cjm-1955-001-4 ↩↩