Teorema de la amistad

El teorema de amigos y extraños o teorema de la amistad es un teorema en el campo matemático llamado teoría de Ramsey.

YouTube Encyclopedic

1/1
Views:
181 725

Transcription

Formulación del teorema

Supóngase que en una fiesta hay 6 personas. Considérese a dos cualquiera de ellas. Puede ser que se reúnan por primera vez, en cuyo caso son mutuamente desconocidas, o puede ser que se hayan conocido antes, en cuyo caso se les llamará mutuamente conocidas. Ahora, el teorema de la amistad dice:

En cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas.

Conversión a grafos

Es conveniente expresar este problema usando el lenguaje de teoría de grafos.

Supóngase que un grafo tiene 6 vértices y cada par de vértices está unido por una arista. Este grafo se llama grafo completo. Un grafo completo de n vértices se denota por $K_{n}\,$ . En el caso de un grafo de 3 vértices y en donde cada vértice es adyacente a los demás, se trata del grafo completo $K_{3}\,$ o del ciclo de longitud 3: $C_{3}\,$ , comúnmente llamado triángulo.

Ahora tómese un $K_{6}\,$ . Este grafo completo tiene 15 aristas en total. Sean las 6 personas de la fiesta representadas por los 6 vértices. Sean las aristas coloreadas con los colores rojo o azul dependiendo de si las dos personas representadas por los vértices incidentes a la arista son mutuamente conocidos o desconocidos, respectivamente. El teorema de la amistad afirma ahora:

No importa cómo se ha coloreado las aristas de $K_{6}\,$ con los colores rojo o azul, no se puede evitar que exista un triángulo rojo, es decir, un triángulo que tenga sus tres lados de color rojo, lo que representa tres personas mutuamente extrañas o un triángulo azul, que representan tres personas mutuamente conocidas.

Prueba

Elíjase uno de los vértices P. Hay cinco aristas incidentes a P, cada una coloreada con el color rojo o azul. Según el principio del palomar, al menos tres aristas deben ser del mismo color, porque si hay menos de tres de un solo color, por ejemplo roja, entonces hay al menos tres que son de color azul.

Sean A, B, C, los otros vértices extremos de estas tres aristas, todas del mismo color, por ejemplo azul. Si alguna de las aristas AB, BC, CA es azul, entonces esta arista junto con las dos aristas incidentes a P forman los lados de un triángulo azul. Si ninguna de las aristas AB, BC, CA es azul, entonces las tres aristas son de color rojo y se tiene un triángulo rojo de vértices ABC.

Trabajo de Ramsey

La total simplicidad de este argumento, que produce con tanta fuerza una interesante conclusión, es lo que hace atractivo este teorema. En 1930, en un trabajo titulado «On a Problem in Formal Logic» (Sobre un problema en lógica formal), Frank P. Ramsey demostró un teorema muy general, conocido en la actualidad como teorema de Ramsey en el que el teorema de la amistad es un caso particular. El teorema de Ramsey es la base en la que sostiene el área de la combinatoria conocida como teoría de Ramsey.

Ámbito del teorema de la amistad

La conclusión del teorema de la amistad no se tiene en grupos de menos de seis personas. Para demostrar esto, se colorea K₅ de rojo y azul de forma que no contenga un triángulo cuyos lados sean todos del mismo color. Dibujamos K₅ como un pentágono que rodea una estrella y coloreamos de rojo los lados del pentágono y de azul los de la estrella. Por lo tanto, 6 es el mínimo número para el cual se puede dar por buena la conclusión del teorema de la amistad. En la teoría de Ramsey, esto se denota por: