Coloración de aristas y teorema de Ramsey#
Introducción#
Cuando anteriormente hablamos de emparejamientos, nos referimos a un subconjunto de aristas que no tienen vértices en común. Luego, cuando hablamos de conjuntos independientes, nos referimos a un subconjunto de vértices que no definen aristas. Vimos que la idea de conjuntos independientes era muy cercana a la de coloraciones de vértices. Pero aún no hemos hablado de coloraciones de aristas. Haremos esto a continuación.
Como problema introductorio, imagina que eres un profesor de educación básica, y que has detectado que algunos de tus alumnos todavía no se conocen muy bien. Hiciste una gráfica en donde cada vértice es un alumno, y una arista indica que dos estudiantes todavía no se llevan.
Te gustaría que en el transcurso de los siguientes días los alumnos se conocieran mejor. Para ello, cada día harás una actividad en parejas, en donde cada estudiante puede o no participar. ¿Cuántos días necesitarás para que todos los alumnos se conozcan?
Por ejemplo, en el primer día puedes poner a trabajar en parejas a los alumnos que tienen una arista en rojo de la siguiente figura. Al siguiente día, puedes poner a trabajar en parejas a los alumnos que tienen una arista en azul. Y así sucesivamente.
Como en la gráfica hay \(5\) colores, esto hace que necesites \(5\) días para que todos los alumnos se conozcan. ¿Se podrá organizar las actividades para que tomen menos días?
Coloraciones de aristas#
Comenzamos dando la definición de lo que es una coloración de las aristas de una gráfica.
Definición. Una coloración con \(k\) colores de las aristas de una gráfica con conjunto de aristas \(E\) es una función \(f:E\to \{1,2,\ldots,k\}\).
Usualmente, cuando estamos trabajando de manera informal, en vez de usar los números de \(1\) a \(k\) hacemos dibujos con colores. A una coloración con \(k\) colores también se le conoce como una \(k\)-coloración.
Ejemplo. En la siguiente gráfica se muestra una \(4\)-coloración de las aristas.
\(\square\)
El problema que planteamos al inicio requere que en cada día se trabaje en parejas, así que las aristas de un mismo día no pueden tener vértices en común. Esto nos lleva a la siguiente definición.
Definición. Una coloración de las aristas de una gráfica es propia si no hay dos aristas del mismo color que lleguen al mismo vértice.
Ejemplo. Notemos que la coloración del ejemplo anterior no es propia pues en el vértice superior izquierdo llegan dos aristas rojas.
La siguiente coloración sí es propia pues se puede verificar que a todos los vértices llegan aristas de color distinto.
\(\square\)
Si tenemos muchos muchos colores a nuestra disposición, entonces parece ser fácil dar una coloración propia. Lo difícil es encontrar coloraciones propias con poquitos colores. Esto motiva la siguiente definición.
Definición. El índice cromático de una gráfica \(G\) es el menor entero \(k\) tal que \(G\) tiene una \(k\)-coloración propia. Lo denotaremos por \(\chi'(G)\).
Ejemplo. Una forma de colorear de manera propia la gráfica \(G\) de los ejemplos anteriores es la siguiente:
Sin embargo, esta forma de colorear requiere de muchos colores. Una forma con menos colores es la que ya habíamos visto.
Esta coloración con \(4\) colores nos dice que \(\chi'(G)\leq 4\). Necesitamos un argumento para ver que \(\chi'(G)\geq 4\), es decir, que no se puede dar una coloración propia con menos colores. El argumento es el siguiente. Al vértice marcado con rojo en la siguiente figura llegan \(4\) aristas, que tienen que ser todas de colores diferentes y por lo tanto se necesitan al menos \(4\) colores.
Concluimos entonces que \(\chi'(G)=4\). \(\square\)
En el ejemplo anterior usamos al vértice de grado máximo para acotar al índice cromático. Este argumento sirve en general, y nos permite concluir el siguiente resultado.
Proposición. Sea \(G\) una gráfica y \(\Delta(G)\) su grado máximo. Se tiene que
Un resultado muy sorprendente de Vizing es que la cota anterior en realidad es bastante buena. El índice cromático debe ser mayor o igual al grado máximo. ¡Pero de hecho puede ser a lo más uno más que el grado máximo!
Teorema (Vizing). El índice cromático de una gráfica \(G\) es o bien \(\Delta(G)\) o bien \(\Delta(G)+1\).
No veremos la demostración de este teorema, pero en la lista de ejercicios propuestos se te invitará a que la busques y la estudies.
El teorema de Ramsey#
Hay otro fenómeno interesante que sucede cuando «pintamos con pocos colores las aristas de una gráfica completa grande». La intuición que debes tener al hacer esto es la misma que la del principio de las casillas. Si la gráfica es muy grande, entonces hay muchas aristas. Si hay pocos colores, entonces algo especial debe suceder.
Como ejemplo sencillo, pensemos nuevamente en un salón de clases y en estudiantes que se conocen y que no se conocen. Como estas dos opciones cubren todas las posibilidades, podemos hacer una gráfica completa donde los vértices son los estudiantes y donde pintamos de azul la arista correspondiente a dos estudiantes si se conocen, y de rojo si no. Quedaría algo como en la siguiente figura.
Aquí observa que hay tres estudiantes que sí se conocen mutuamente: \(B\), \(D\) y \(E\). Esto podría parecer una casualidad y de hecho no siempre pasa, por ejemplo en el siguiente ejemplo no hay tres estudiantes que se conozcan mutuamente.
Sin embargo, en este ejemplo sí hay tres estudiantes que no se conocen mutuamente: \(A\), \(E\) y \(F\). ¿Será nuevamente casualidad? La respuesta es que no. Como veremos a continuación, siempre, sin importar cómo estén definidas las amistades, siempre habrá o bien tres estudiantes que se conocen mutuamente o bien tres estudiantes que no se conocen mutuamente.
Proposición. Cualquier \(2\)-coloración de las aristas de una gráfica completa de \(6\) vértices siempre tiene un triángulo monocromático, es decir, siempre aparece un triángulo hecho por vértices de la gráfica en donde las tres aristas que definen son rojas, o bien las tres aristas que definen son azules.
Demostración. Pensemos que estamos coloreando las aristas con rojo y azul. Tomemos un vértice \(v\) de la gráfica cualquiera. Por principio de las casillas, al menos tres de las cinco aristas que salen de \(v\) son del mismo color, sin perder generalidad, digamos rojo.
Llamemos \(x,y,z\) a los vértices a donde llegan tres aristas rojas desde \(v\). Si alguna de las aristas \(xy,yz,zx\) son rojas, entonces se hace ya sea el triángulo rojo \(xyv\), el \(yzv\) o el \(zxv\) respectivamente. Si las tres son azules, se hace el triángulo azul \(xyz\). Así, en cualquier caso tenemos un triángulo monocromático.
\(\square\)
¿Será que \(6\) es un número especial que esto suceda? Por supuesto, cualquier gráfica completa y con aristas bicoloreadas tendrá un triángulo monocromático, pues basta fijarse en \(6\) vértices cualesquiera para encontrar en ellos un triángulo monocromático. ¿Y con menos vértices? Aquí no siempre es posible garantizar la existencia de tal triángulo monocromático. Por ejemplo, con cuatro vértices hay coloraciones que no tienen triángulos monocromáticos como la siguiente:
Así,
Toda coloración de la gráfica completa en \(6\) vértices tiene un triángulo monocromático.
Existe al menos una coloración de la gráfica completa en \(4\) vértices sin triángulo monocromático.
En los ejercicios tendrás que pensar qué sucede con \(5\) vértices.
Resulta que el fenómeno que vimos en el ejemplo anterior es muy general. A continuación presentamos una versión extendida (aunque hay algunas versiones que lo son mucho más). En la siguiente versión seguimos usando dos colores. Sin embargo, ahora en vez de buscar triángulos monocromáticos lo que queremos es que o bien haya \(m\) vértices todos conectados por aristas rojas, o bien haya \(n\) vértices todos conectados por aristas azules.
Teorema (de Ramsey para dos colores). Para cualesquiera dos enteros \(m\) y \(n\) existe un número \(R:=R(m,n)\) tal que si coloreamos con dos colores las aristas de una gráfica completa con \(R\) vértices siempre podemos encontrar:
O bien \(m\) vértices tales que todas sus aristas son del primer color.
O bien \(n\) vértices tales que todas sus aristas son del segundo color.
Los ejemplos de arriba muestran que \(R(3,3)\geq 5\) y \(R(3,3)\leq 6\). ¿Podrás dar cotas superiores o inferiones para \(R(3,4)\)?
La demostración de esta versión del teorema de Ramsey no es muy difícil y está al alcance de las herramientas que hemos adquirido hasta ahora.
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.
Encuentra el índice cromático de la siguiente gráfica:
Como sugerencia, encuentra el grado máximo de la gráfica. El teorema de Vizing te dará dos posibilidades. Después de eso, sólo enfócate en encontrar cuál de esas dos posibilidades es la correcta.
En términos del teorema de Ramsey, ¿qué sucede con las gráficas completas de \(5\) vértices? ¿Será que en cualquier bicoloración de sus aristas aparece un triángulo monocromático? ¿O habrá una bicoloración sin triángulos monocromáticos?
Sea \(G=(V,E)\) una gráfica, \(\nu(G)\) su número de emparejamiento y \(\chi'(G)\) su índice cromático.
Demuestra que \(\nu(G) \chi'(G) \geq |E|\).
Encuentra una gráfica donde se cumple la igualdad.
Encuentra una gráfica donde \(\nu(G) \chi'(G) > |E|\).
Sea \(G\) una gráfica bipartita en la que cada vértice tiene grado \(3\). Demuestra que \(\chi'(G)=2\). Como sugerencia, utiliza el teorema de Hall tres veces. ¿Puedes generalizar este resultado a gráficas bipartitas en donde cada vértice tiene grado \(k\)?
Demuestra el teorema de Ramsey para dos colores. Observa que no es necesario encontrar el valor exacto de \(R(m,n)\) (de hecho esto es un problema muy difícil). Como sugerencia, procede por inducción y usa un argumento tipo teorema de las casillas, como en el ejemplo de \(6\) vértices.
Investiga y estudia con detalle la demostración del teorema de Vizing.