Subgráficas completas y teorema de Turán#
Introducción#
Anteriormente ya hablamos de conjuntos de vértices en donde ningún vértice estaba conectado con otro. A estos les llamamos los conjuntos independientes de una gráfica. Hay aplicaciones en las que en vez de hablar de conjuntos independientes, nos interesa hablar de conjuntos en los que todos los vértices están conectados entre sí. A estos les llamaremos cliques.
Una posible situación en la que nos interesaría hablar de cliques es la siguiente. Imagina que quieres crear una lista de reproducción de música que usualmente reproducirás en modo aleatorio. No te gusta mucho que tras una canción se reproduzca otra que sea sumamente distinta. Por ejemplo, no te gustaría que tras una canción de meditación sonara una de reggaeton. Como no tienes certeza de cuál canción aparecerá, necesitas que las canciones elegidas sean todas compatibles entre sí.
Para modelar el problema, puedes hacer una gráfica. Pones un vértice por cada canción y pones arista entre dos vértices si las canciones son compatibles. Tras hacer esto, te quedaría una gráfica como la siguiente.
En esta gráfica, podemos encontrar cuatro vértices, todos con aristas entre ellos, como en la siguiente figura.
Esto quiere decir que sus canciones son compatibles entre sí. De esta manera, podrías hacer una lista de reproducción con las canciones correspondientes a esos \(4\) vértices y reproducirla en modo aleatorio sin preocuparte de que haya canciones incompatibles una después de otra. Tomando en cuenta la gráfica anterior, ¿cuál sería la máxima cantidad de canciones que podrías poner en la lista para que se cumpla lo que hemos dicho?
Cliques#
Demos dos definiciones.
Definición. Un clique de una gráfica \(G\) es un subconjunto de sus vértices tales que hay una arista entre cualesquiera dos de ellos.
Definición. El número de clique de una gráfica \(G\) es el número máximo de vértices en un clique de \(G\). Lo denotaremos por \(\omega(G)\).
Ejemplo. Una gráfica típicamente tiene muchos cliques. Retomemos la gráfica del zoológico de un capítulo anterior, en donde los vértices son animales y las aristas están entre animales que no pueden ser transportados simultáneamente.
Un ejemplo de clique sería \(E,H,J\) pues son vértices que están conectados todos entre sí. ¿Qué querría decir en el caso de los animales? Que son tres que no tienen compatibilidad entre sí. Esto nos diría que necesitamos por lo menos \(3\) transportes distintos para transportarlos. En esta gráfica hay otro triángulo: \(I,D,F\). Pero hay también un clique más grande: \(A,F,D,G\). Puedes verificar que, de hecho, es un clique máximo. Esto nos dice que \(\omega(G)=4\).
\(\square\)
Es posible que en este momento tengas la impresión de que estudiar el número de clique de una gráfica es sumamente parecido a estudiar el número de independencia de una gráfica. Y tienes razón. La noción que los conecta es la siguiente.
Definición. Sea \(G=(V,E)\) una gráfica. La gráfica complemento de \(G\) es aquella gráfica cuyo conjunto de vértices también es \(V\) y cuyas aristas son todas aquellas que no están en \(E\).
Ejemplo. A continuación se muestra una gráfica y su complemento.
\(\square\)
Tenemos entonces el siguiente resultado.
Teorema. Sean \(G\) una gráfica y \(G'\) su complemento. Entonces \(\omega(G)=\alpha(G')\).
Esto nos permite traducir prácticamente cualquier resultado que sepamos de número de independencia en una gráfica a un resultado del número de clique en su complemento, y viceversa.
Teorema de Turán#
El principio de las casillas nos ayudó para obtener una intuición importante cuando hablamos del teorema de Ramsey. Ahora usaremos nuevamente esta intuición para entender otro fenómeno que sucede en teoreía de gráficas. Piensa que tienes una gráfica con \(n\) vértices, inicialmente sin aristas. Vamos agregando aristas poco a poco. Evidentemente, será inevitable que conforme hagamos esto, vayan apareciendo sub gráficas completas más y más grandes, es decir, que el número de clique vaya creciendo. Al poner todas las aristas posibles, esto nos dará una gráfica completa en \(n\) vértices. Pero, ¿en qué momento (es decir, a las cuántas aristas) empiezan a aparecer cliques de tamaño \(3\)? ¿En qué momento empiezan a aparecer cliques de tamaño \(4\)?
Sorprendentemente la respuesta se sabe con mucha precisión. Para poder darla, necesitamos definir un par de cosas que extienden algunas nociones que ya habíamos discutido.
Definición. Una gráfica \(G\) es \(r\)-partita si se puede dar una partición de sus vértices en \(r\) partes \(V=V_1\cup\ldots\cup V_r\) tal que no hay aristas entre vértices de la misma parte. A las partes \(V_i\) se les llama clases. Diremos que \(G\) es \(r\)-partita completa si además de ser \(r\)-partita, hay arista entre cualesquiera dos vértices de clases distintas.
Por supuesto, las gráficas bipartitas que habíamos estudiado con anterioridad corresponden a las gráficas \(2\)-partitas de esta definición.
Definición. Diremos que una gráfica \(G\) \(r\)-partita con clases \(V_1,\ldots,V_r\) es balanceada si para cualesquiera dos clases \(V_i\) y \(V_j\) se tiene que \(||V_i|-|V_j||\leq 1\).
Como observación, si una gráfica \(G\) tiene en total \(n\) vértices y es \(r\)-partita balanceada, entonces forzosamente \(|V_i|=\lfloor \frac{n}{r}\rfloor\) o \(|V_i|=\lceil \frac{n}{r}\rceil\). Más aún, se puede decir en términos de \(n\) y \(r\) la cantidad de clases con cada uno de estos dos tamaños. Todo esto lo verificarás en uno de los ejercicios del capítulo. Debido a esto, podemos introducir la siguiente definición.
Definición. Sean \(n\) y \(r\) enteros positivos con \(n\geq r\). La gráfica de Turán, a la que denonaremos \(T(n,r)\), es la gráfica \(r\)-partita completa balanceada en \(n\) vértices.
Veamos unos ejemplos que ilustren todo lo anterior.
Ejemplo. La siguiente gráfica es una gráfica \(3\)-partita.
Una posible separación en \(3\) clases es:
Con esta separación de clases, la gráfica \(3\)-partita no es balanceada, pues hay una clase de tamaño \(2\), una de tamaño \(4\) y \(|3-5|=2>1\). Tampoco es una gráfica \(3\)-partita completa pues, por ejemplo, no hay aristas entre los vértices \(a\) y \(g\) que son de clases distintas.
Curiosamente, también podemos pensar que esta es una gráfica \(4\)-partita, pensando en la siguiente separación en \(4\) clases:
Con esta separación de clases, la gráfica \(4\)-partita sí es balanceada, pues sólo hay clases de tamaño \(2\) y \(3\) (que distan a lo más en uno).
\(\square\)
Ejemplo. A continuación se muestra una gráfica \(4\) partita balanceada y completa. Aunque hay clases de tamaños distintos, esto no es un problema pues el tamaño entre clases difiere en a lo más \(1\).
En este ejemplo, las clases son: los dos vértices superiores, los dos vértices a la derecha, los dos vértices a la izquierda y los tres vértices de abajo.
\(\square\)
Estamos listos para enunciar el teorema de Ramsey.
Teorema. Sea \(G\) una gráfica con \(n\) vértices y número de clique \(\omega(G)=r\). Entonces \(G\) tiene máximo tantas aristas como la gráfica de Turán \(T(n,r)\).
Usualmente este teorema se usa «al revés» es decir, en su verisón contrapositiva.
Corolario. Si \(G\) es una gráfica con \(n\) vértices y más aristas que \(T(n,r)\), entonces podemos encontrar en \(G\) un clique de tamaño \(r+1\).
Para aterrizar las ideas, tomemos por ejemplo el caso \(r=2\). Con esto obtendríamos el llamado teorema de Mantel.
Corolario (teorema de Mantel). Si \(G\) es una gráfica con \(n\) vértices y más de \(\lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil\) aristas, entonces \(G\) tiene un triángulo.
Aunque tenemos todas las herramientas combinatorias para demostrar el teorema de Turán en toda su generalidad, no lo haremos aquí. Sin embargo, en los resultados se te invita a pensar en hacer la demostración para el teorema de Mantel.
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
En este capítulo y los anteriores hemos hablado de las siguientes gráficas:
La del equipo de trabajo en ciencia de datos que quiere repartirse ciertas actividades.
La del zoológico que se está mudando.
La de los estudiantes que se conocen y no se conocen.
La de las canciones compatibles.
Para cada una de esas gráficas, encuentra \(\chi(G), \chi'(G), \alpha(G), \nu(G), \omega(G), \Delta(G)\), e interpreta estos parámetros de la gráfica en el contexto del problema.
Vamos a crear varias gráficas. Todas ellas tendrán como conjunto de vértices a los números de \(1\) a \(20\).
En la gráfica \(G\) habrá una arista entre \(i\) y \(j\) si \(i\) y \(j\) son primos relativos.
En la gráfica \(H\) habrá una arista entre \(i\) y \(j\) si \(i\) y \(j\) comparten alguna de las letras en su nombre.
En la gráfica \(J\) habrá una arista entre \(i\) y \(j\) si \(i-j\) es múltiplo de \(3\).
En la gráfica \(K\) habrá una arista entre \(i\) y \(j\) si \(ij\) es un número cuadrado. Para cada una de estas gráficas, encuentra \(\chi(G), \chi'(G), \alpha(G), \nu(G), \omega(G), \Delta(G)\). Interpreta estos parámetros de la gráfica de acuerdo a cómo se construyó.
Muestra que si una gráfica es \(r\)-partita balanceada y tiene \(n\) vértices, entonces para cualquier clase \(V_i\) se tiene que \(|V_i|=\lfloor \frac{n}{r}\rfloor\) o \(|V_i|=\lceil \frac{n}{r}\rceil\). De hecho, muestra que si escribes \(n=qr+s\) con \(0\leq s < r\), entonces hay exactamente \(s\) clases de tamaño \(\lceil \frac{n}{r}\rceil\) y \(r-s\) clases de tamaño \(\lfloor \frac{n}{r}\rfloor\).
Los parámetros \(\omega(G)\) y \(\chi(G)\) están muy relacionados entre sí. Recuerda qué significa cada uno de ellos y establece una desigualdad que te diga cómo se comparan entre sí.
Las nociones de gráfica \(r\)-partita y de \(r\)-coloración propia están muy relacionadas entre sí. Si una gráfica es \(r\)-partita, ¿qué puedes decir de su número cromático?
Demuestra el teorema de Mantel.