Organizar una velada… con restricciones sanitarias -------------------------------------------------
El BDF considera que la fiesta será un éxito si al menos tres invitados se conocen entre sí —pues así sabrán generar una buena dinámica durante la velada— o si, por el contrario, al menos tres invitados no se conocen en absoluto —pues los encuentros siempre son estimulantes—. Consciente de los riesgos sanitarios, el BDF también desea invitar al menor número posible de personas. ¿Cuántos invitados debe elegir al azar para respetar todas estas restricciones?
La respuesta es 6. Pero ¿a cuántas personas habría tenido que invitar el BDF si, en vez de tres, hubiera querido garantizar un grupo de k invitados que se conocieran entre sí o, por el contrario, que no se conocieran en absoluto? Esta cuestión se reformula en el lenguaje de la teoría de grafos: determinar el kº número diagonal de Ramsey R(k).
Formas y colores --------------------------
Traduzcamos el problema del BDF a términos matemáticos. Representemos a cada invitado mediante un punto (un vértice) en una hoja y unamos después cada par de puntos con un trazo (una arista), rojo si los dos invitados que representan se conocen y azul en caso contrario. Así construimos un grafo completo. Exigir que exista un grupo de tres personas que se conozcan mutuamente o un grupo de tres personas que no se conozcan entre sí equivale, por tanto, a exigir que existan en nuestro grafo tres puntos unidos entre sí por aristas rojas (un triángulo rojo) o tres puntos unidos entre sí por aristas azules (un triángulo azul). Determinar R(3) consiste en hallar el número mínimo de vértices que debe tener el grafo para garantizar que, sea cual sea la coloración de las aristas, habrá necesariamente un triángulo rojo o un triángulo azul. Cinco vértices no bastan, como muestra la figura de la izquierda.