Hay n apartamentos tipo estudio en un edificio. Algunos de los apartamentos están conectados entre sí por línea telefónica directa. Demostrar que es posible asignar a cada apartamento una mujer o un hombre de tal manera que cada persona tenga relación directa con al menos tantas personas del sexo opuesto como tenga con personas del mismo sexo.
Asigne los apartamentos de manera que maximice la cantidad de líneas directas que conectan a un hombre con una mujer. Considere a cualquier inquilino, asumiendo que el wlog es hombre. Si estuviera conectado con más hombres que mujeres, reemplazarlo con una mujer aumentaría el número de conexiones hombre-mujer, contradiciendo la maximalidad asumida.
Mediante un argumento estándar de "compacidad" [*], el resultado puede generalizarse a gráficos localmente finitos , es decir, el número de apartamentos puede ser infinito, pero cada uno está conectado a un número finito de otros.
El resultado se generaliza fácilmente a cualquier número de sexos. Para ponerlo en terminología estándar de teoría de grafos:
Teorema. Dado un gráfico localmente finito y un conjunto finito no vacío , podemos encontrar una función tal que, para cualquier y cualquier , tenemos
[*] En caso de que alguien esté interesado, aquí está (una versión de) el "argumento de compacidad" usado para pasar del caso finito al localmente finito. Dejar sea el conjunto de todas las funciones . Visto como el producto Tychonoff de copias de dotado de la topología discreta, es un espacio compacto. Por cada vértice , dejar sea el conjunto de todas las funciones tal que la desigualdad mostrada se cumple en (para todos ). Tenga en cuenta que es un conjunto cerrado. (Aquí se utiliza la suposición de finitud local.) Afirmo que la familia tiene la propiedad de intersección finita, es decir, que para cada conjunto finito . Esto se sigue del caso finito del teorema, aplicado al gráfico finito obtenido al restringir al conjunto finito formado por los vértices de y sus vecinos. (La finitud local se usa nuevamente aquí.) Por lo tanto, por compacidad, tenemos , QED
Cadena
Jebediah