11.1: Un primer sabor de la teoría de Ramsey

A Bob le gusta pensar en sí mismo como un tipo salvaje y loco, totalmente impredecible. La mayoría de los chicos sí. Pero Alice dice que Bob no puede cambiar su naturaleza básica, lo cual es insoportantemente aburrido. Carlos comenta que quizás no deberíamos ser tan duros con Bob, porque bajo ciertas circunstancias, todos podemos ser forzados a ser aburridos y repetitivos.

Recordemos que cuando\(n\) es un entero positivo, dejamos\([n]=\{1,2,…,n\}\). En este capítulo, cuando\(X\) es un conjunto y\(k\) es un entero no negativo con\(k \leq |X|\), tomamos prestada de nuestra notación en línea para los coeficientes binomiales y dejamos\(C(X,k)\) denotar la familia de todos los subconjuntos\(k\) -elementos de\(X\). Así que\(|C([n],k)|=C(n,k)\) cuando sea\(0 \leq k \leq n\).

Recordemos que el Principio de Agujero Paloma afirma que si\(n+1\) las palomas se colocan en\(n\) agujeros, entonces debe haber algún agujero en el que se hayan colocado dos o más palomas. Más formalmente, si\(n\) y\(k\) son enteros positivos,\(t>n(k−1)\) y\(f:[t] \rightarrow [n]\) es cualquier función, entonces hay un subconjunto\(k\) -elemento\(H⊆[t]\) y un elemento\(f(i)=j\) para\(j \in [n]\) que para cada\(i \in H\).

Ahora nos embarcamos en un estudio de una elegante extensión de este resultado básico, uno que sigue fascinando y desafiando.

Volviendo a la discusión al inicio de esta sección, se podría decir que una subgrafía inducida\(H\) de una gráfica\(G\) es “aburrida” si es una subgrafía completa o un conjunto independiente. En cualquier caso, exactamente cada par de vértices en\(H\) se comporta exactamente de la misma manera aburrida. Entonces, ¿es inevitable el aburrimiento? La respuesta es sí, al menos en un sentido relativo. Como iniciador, mostremos que cualquier gráfica en seis (o más) vértices tiene una subgrafía aburrida de tamaño tres.

Lema 11.1

Dejar\(G\) ser cualquier gráfica con seis o más vértices. Entonces o bien\(G\) contiene una subgrafía completa de tamaño 3 o un conjunto independiente de tamaño 3.

Prueba

Deja\(x\) ser cualquier vértice adentro\(G\). Luego divide los vértices restantes en dos conjuntos\(S_1\) y\(S_2\)\(S_1\) siendo los vecinos de\(x\) y\(S_2\) los no vecinos. Ya que\(G\) tiene al menos seis vértices, sabemos que\(|S_1| \geq 3\) o bien\(|S_2| \geq 3\). Supongamos primero eso\(|S_1| \geq 3\) y dejar\(y_1, y_2\) y\(y_3\) ser distintos vértices de\(S_1\). Si\(y_iy_j\) es un borde\(G\) para algún par distinto\(i,j \in \{1,23\}\), entonces\(\{x,y_i,y_j\}\) es un subgrafo completo de tamaño 3 pulg\(G\). Por otro lado, si no hay aristas entre los vértices en\(\{y_1,y_2,y_3\}\), entonces tenemos un conjunto independiente de tamaño .3.

El argumento cuando\(|S_2| \geq 3\) es dual.

Observamos que el límite de seis en el lema anterior es agudo, ya que un ciclo sobre cinco vértices no contiene ni un conjunto completo de tamaño 3 ni un conjunto independiente de tamaño 3.

A continuación, aquí está la afirmación que generaliza este resultado.

Teorema 11.2. Teorema de Ramsey para Gráficas

Si\(m\) y\(n\) son enteros positivos, entonces existe un número entero menos positivo de\(R(m,n)\) modo que si\(G\) es una gráfica y\(G\) tiene al menos\(R(m,n)\) vértices, entonces ya sea \(G\)contiene un subgrafo completo en\(m\) los vértices, o\(G\) contiene un conjunto independiente de tamaño\(n\).

Prueba

Demostramos que\(R(m,n)\) existe y es como mucho\(\binom{m+n-2}{m-1}\). Esta afirmación es trivial cuando cualquiera\(m \leq 2\) o\(n \leq 2\), por lo que podemos suponer que\(m,n \geq 3\). A partir de este punto, se procede por inducción al\(t=m+n\) asumir que el resultado se mantiene cuando\(t \leq 5\).

Ahora vamos a\(x\) ser cualquier vértice adentro\(G\). Luego hay al menos\(\binom{m+n-2}{m-1}-1\) otros vértices, que particionamos como\(S_1 \cup S_2\), donde\(S_1\) están esos vértices adyacentes a\(x\) in\(G\) y\(S_2\) son aquellos vértices que no son adyacentes a\(s\).

Recordamos que los coeficientes binomiales satisfacen

\(\dbinom{m+n-2}{m-1} = \dbinom{m+n-3}{m-2} + \dbinom{m+n-3}{m-1} = \dbinom{m+n-3}{m-2} + \dbinom{m+n-3}{n-2}\)

Entonces, ya sea\(|S_1| \geq \binom{m+n-3}{m-2}\) o\(|S_1| \geq \binom{m+n-3}{m-1}\). Si la primera opción se mantiene, y\(S_1\) no tiene un conjunto independiente de tamaño\(n\), entonces contiene un subgrafo completo de tamaño\(m−1\). De ello se deduce que podemos agregar\(x\) a este conjunto para obtener una subgrafía completa de tamaño\(m\) en\(G\).

Del mismo modo, si la segunda opción se mantiene, y\(S_2\) no contiene un subgrafo completo de tamaño\(m\), entonces\(S_2\) contiene un conjunto independiente de tamaño\(n−1\), y podemos agregar\(x\) a este conjunto para obtener un conjunto independiente de tamaño\(n\) en\(G\).