UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO
FACULTAD DE CIENCIAS
SOBRE LA SUBDIVISIÓN CROMÁTICA
DE UN COMPLEJO SIMPLICIAL
T E S I S
QUE PARA OBTENER EL TÍTULO DE:
M A T E M Á T I C A
P R E S E N T A:
J E N Y L I N Z U Ñ I G A A P I P I L H U A S C O
DIRECTOR DE TESIS:
DR. VINICIO ANTONIO GÓMEZ GUTIÉRREZ
Ciudad Universitaria, Cd. Mx.
2023
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
  
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
  
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
  
 
II
Sobre la subdivisión cromática de um 
compolejo sumplicial
~br&Úf¡ r~iJJfI¡C%fJ~~tUf¡ 
ClJm¡;ltjfJ r~ 
IV
A mis padres, Lupita y Rubén.
A mi hermano Axel.
A Ulises y a Camelia.
VI
Agradecimientos
Para ser sincera, he soñado muchas veces con este día en que escribiera las líneas de agradecimientos de
mi tesis, una vez habiéndola completado. Al principio se veía lejano, muy distante, casi inalcanzable...
luego comenzó a ser un poco más fácil de vislumbrar, pero todavía faltaba algún camino por recorrer,
obstáculos que sortear, trabajo por hacer...
Ahora he llegado a este punto, en el que concluyo un trabajo que representa también el fin de mi recorrido
por la Licenciatura en Matemáticas de la UNAM y el destino de un largo camino en el que he tenido
vastos aprendizajes, mientras me he abierto paso entre los triunfos y desengaños que conlleva estudiar
una carrera, comenzar a dar clases y redactar un trabajo para titularme.
Quisiera poder traer a mi mente los nombres de todas las personas con las que me siento agradecida por
acompañarme durante esta aventura y por hacer posible este trabajo de tesis, para nombrarlas a cada una
en esta página, pero es imposible. Se me ocurren demasiadas: desde los antiguos matemáticos hasta los
actuales, desde personas que ya no frecuento hasta las más cercanas, desde quien inventó el papel hasta
quien creó LATEX... y quizá suene absurdo, pero considero que la vida como la conocemos no sería posible
sin la participación de un gran número de personas: unas que están, otras que ya no. Este trabajo de tesis
ha sido posible gracias a muchas personas que han contribuido directa o indirectamente.
La anterior reflexión es al mismo tiempo una disculpa por no poder incluir los nombres de todas las
personas a quienes recuerdo con cariño. Me veo obligada a escribir agradecimientos puntuales a quienes
han sido más cercanas o cercanos a mí durante el desarrollo y la conclusión de este trabajo y a quienes
tengo más presentes. Pido comprensión de antemano si paso por alto a alguien, ya que este ejercicio de
memoria y selección no me resulta tan sencillo... inclusive ahora pareciera la parte más difícil de la tesis.
En primer lugar, agradezco a la Universidad Nacional Autónoma de México por darme la oportunidad de
estudiar en sus aulas y deleitarme en sus bibliotecas.
Agradezco también a la Comisión de Equidad y Género de la Sociedad Matemática Mexicana (CEG-
SMM) por otorgarme la beca “Women in Combinatorics” para ayudar al desarrollo y conclusión de esta
tesis.
Agradezco a mi tutor, el Dr. Vinicio Antonio Gómez Gutiérrez, por el tiempo que dedicó a brindarme su
guía y su apoyo, por todas las explicaciones y recomendaciones. Por acercarme a los cursos del Dr. José
Carlos y del Dr. José Ángel, además de leer conmigo el libro del Dr. Sergio Rajsbaum. Por las invaluables
explicaciones e ideas y por su gran acompañamiento y ayuda. Sin él, este trabajo no habría sido posible.
Agradezco a mis sinodales (cito en orden alfabético y tomo en cuenta el primer apellido) el Dr. José
Ángel Frías García, el Dr. José Carlos Gómez Larrañaga, la Dra. Lourdes del Carmen González Huesca
y el Dr. Sergio Rajsbaum Gorodezky, por haber aceptado revisar mi tesis, por interesarse en mi trabajo y
VII
VIII
por sus valiosas observaciones que ayudaron a mejorar esta tesis.
Gracias a mi madre María Guadalupe Apipilhuasco Domínguez por apoyarme desde que era pequeña
y por su gran dedicación en todo lo relativo a mis estudios desde entonces, por su ayuda económica,
por comprenderme cuando le he contado de mis éxitos y fracasos, por ayudarme a vivir cerca de la
universidad y por estar ahí cuando la he necesitado.
Gracias a mi padre Efrén Rubén Zúñiga Leonel por todas las veces que me ha llevado de la casa a la es-
cuela y viceversa, por haberme apoyado económicamente cuando iniciaba con este trabajo, por ayudarme
con los cambios de casa y por acudir pronto a ayudarme cuando lo he necesitado, por ser testigo de este
largo camino que he emprendido.
Gracias a mi hermano Axel Rubén por regalarme alguna llamada de vez en cuando y por dejarme saber
que puedo contar con él, por todas las veces que ha puesto gran empeño en que nos podamos llevar bien.
Gracias a mis abuelitas, Faela y Cuca, que quizá no lean esto pero han estado siempre presentes para mí
y las llevo en mi corazón aunque no las vea mucho.
Gracias a Ulises Pérez Cendejas porque me acompañó desde el inicio hasta el final de este trabajo,
brindándome su apoyo sin condiciones y siendo un gran soporte al que siempre he podido recurrir, además
de darme aliento y buenas ideas cuando lo he necesitado. Gracias a su familia, Coralia, Antonio y Toño,
por recibirme calurosamente en su casa y brindarme su apoyo.
Gracias a Jorge Luis Rocha Macías por haber creído en mí y haberme mostrado el maravilloso mundo de
la docencia.
Gracias a José Arnulfo Herrera Lara, Pepe, por las pláticas de matemáticas y de gatos (entre otras), por
sus consejos, por permitirme ser su ayudante de Lineal, por ayudarme cuando Camelia enfermó y por sus
numerosos regalos.
Gracias al profesor Carlos Islas por permitirme ser ayudante de sus cuatro cursos de Cálculo, en los que
aprendí y reforcé mis conocimientos de muchos temas.
Gracias a Álvaro Reyes García porque me gustó mucho que pudiéramos ser ayudantes juntos del curso
de Análisis y por sus ánimos inagotables para asistir a múltiples carreras conmigo. Gracias al profesor
Manuel Falconi por permitirme ser ayudante de su curso de Análisis.
Gracias a Pablo César Palomino Martínez por su alegría y su comprensión, por las sesiones de meditación
afuera del Instituto y por sus consejos. Gracias a Liz por su confianza.
Gracias a Yerenia Amado Fuentes, Yeri, y a Juan Ángeles Hernández, John, por su compañía, por escu-
charme y porque gracias a ustedes este proceso ha sido más llevadero.
Gracias a las y los profesores y ayudantes de la licenciatura que me compartieron su pasión por las ma-
temáticas y sus vastos conocimientos, pero sobre todo que me hicieron sentirme llena de motivación.
Gracias a las y los alumnos que me han brindado su amistad y sus dudas, y que me han dejado compar-
tirles un poco de mi entusiasmo por aprender y enseñar matemáticas.
Gracias muy en especial a Camelia, por luchar cada día para regalarme un poquito más de su vida a mi
lado, después de todos los años que me ha acompañado y de las cosas que hemos pasado juntas. Gracias
por siempre recibirme al llegar a casa y darme motivos para vivir. Has sido y siempre serás la gatita más
hermosa y preciosa del universo.
IX
X
Índice general
Agradecimientos VII
Resumen XIII
1. Introducción 1
1.1. El problema de las niñas enlodadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. El problema del ataque coordenado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3. Estructura de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2. Preliminares 13
2.1. Complejos simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1. Complejos simpliciales geométricos . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2. Complejos simpliciales abstractos . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2. Conceptos de la teoría de categorías . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3. Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3. Subdivisión cromática de un simplejo 31
3.1. Diagramas de Schlegel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2. Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4. Subdivisión cromática de un complejo simplicial 83
5. Aplicación al problema de la isla de los muertos 89
5.1. Primera pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2. Segunda pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
XI
XII ÍNDICE GENERAL
5.2.1. Caso particular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.2. Caso general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3. Tercera pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4. Cuarta pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.5. Quinta pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.6. Sexta pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.7. Séptima pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.8. Octava pregunta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6. Observaciones finales 127
A. Lista exhaustiva de los simplejos 129
B. El problema de las niñas enlodadas 145
B.1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
B.2. Solución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Referencias 151
Resumen
El contenido de este trabajo de tesis se basa principalmente en el artículo “Chromatic subdivision of
a simplicial complex” [Kozlov, 2012] y su objetivo es exponer con todo detalle las construcciones de
las subdivisiones cromáticas de las que es posible obtener una representación geométrica, así como las
pruebas de algunos resultados del artículo. Adicionalmente, aplicamos los conocimientos sobre estos
objetos matemáticos para resolver un problema planteado en el libro Por la senda de los círculos [Neve
y Rosales, 2017, p. 46] que no se ha estudiado antes con este enfoque.
XIII
XIV ÍNDICE GENERAL
Capítulo 1
Introducción
“ Much of the computing world is now concurrent! ”
Gregory R. Andrews, 2000
En esta sección nos proponemos introducir algunos conceptos de computación que ayudan a comprender
una de las principales aplicaciones de nuestro tema de estudio, es decir, la subdivisión cromática de
un complejo simplicial. Es nuestro objetivo explicar de manera intuitiva algunas ideas y problemas de
computación distribuida que pueden estudiarse con ayuda de este concepto que aparece en algunas ramas
de las matemáticas como la topología algebraica o la combinatoria. En el presente apartado todavía no
expondremos de manera formal y rigurosa las definiciones de un complejo simplicial ni de algunos otros
entes matemáticos, mismas que se darán en el siguiente capítulo.
Como en muchas otras áreas del conocimiento humano, en las ciencias de la computación existen distin-
tos campos de estudio. Uno de ellos es la computación distribuida, que se encarga de estudiar los sistemas
distribuidos. Para entender un poco mejor qué significan estos sistemas, primero hablaremos acerca de
qué es un sistema concurrente, pues frecuentemente se entiende un sistema distribuido como el caso par-
ticular de un sistema concurrente cuando sus componentes se encuentran separados desde un punto de
vista geográfico.1
Para reconocer los sistemas concurrentes, conviene observar que hoy en día, al realizar algunas de nues-
tras actividades cotidianas, muchas personas utilizamos una gran cantidad de computadoras, dispositivos
o procesadores que están conectados al mismo tiempo, inclusive sin darnos cuenta. Por ejemplo, segura-
mente hemos solicitado algún dato en internet, para lo que nuestro ordenador hizo una petición a algún
servidor que está conectado en "la nube", o quizá hicimos alguna búsqueda en Google al mismo tiempo
que millones de personas más lo hicieron, o simplemente usamos una laptop que tiene un procesador de
dos núcleos y además está conectada a una impresora o a un teléfono celular, como yo lo estoy haciendo
al escribir estas líneas. Por otro lado, la palabra “concurrente” me hace recordar algún lugar muy “concu-
rrido” como un banco, una fiesta o una avenida, donde muchas personas a pie o en automóvil se reúnen
al mismo tiempo. Es en ese sentido que se habla de sistemas concurrentes, pues la principal característica
1Ver [Rajsbaum et al., 2014, p. 4].
1
2 CAPÍTULO 1. INTRODUCCIÓN
de estos sistemas es que en ellos hay dos o más computadoras, procesos o agentes que realizan una tarea
al mismo tiempo y se pueden comunicar entre ellos.2
A pesar del uso extendido de los sistemas distribuidos, o acaso por su misma generalización, estos están
sujetos a múltiples dificultades, puesto que se han vuelto cada vez más complejos. En [Attiya y Welch,
2004, p. 2] se menciona:
Algunas de las dificultades son pragmáticas, por ejemplo, la presencia de hardware y
software heterogéneo y la falta de adherencia a los estándares. Otras dificultades más im-
portantes se introducen por tres factores: la asincronía, el conocimiento local limitado y las
fallas. El término asincronía significa que los tiempos absolutos e incluso relativos en que
suceden los eventos no siempre se pueden conocer de manera precisa. Además, cada entidad
de cómputo tiene únicamente una visión local de la situación global porque sólo puede co-
nocer la información que recibe. Asimismo, las entidades computacionales pueden fallar de
manera independiente y dejar algunos componentes trabajando, mientras que otros no.3
En términos más simples, podríamos decir que el hecho de poder tener varias computadoras trabajando
al mismo tiempo y que puedan comunicarse entre sí para resolver una tarea, no es gratuito, pues esto
viene acompañado de múltiples problemas, como que las computadoras no tengan certeza de cuándo
alguna de ellas va a acabar un procedimiento o cuándo se va a comunicar; que una computadora sólo
pueda conocer su información inicial y la que le llega; o bien que existan fallas responsables de que
una computadora se detenga o se comporte de manera “rara”. Cabe mencionar que, aunado a esto, en
computación distribuida no hay un modelo único, es decir, no hay una especie de arquetipo que determine
cómo se deben comunicar las computadoras en un sistema distribuido, ni cómo se deben organizar o
almacenar datos en su memoria. Por ello, se procura hacer los estudios sobre sistemas distribuidos de
una manera general, que pueda aplicarse a distintos modelos y además tome en cuenta las dificultades
usuales de este tipo de sistemas.
A pesar de los múltiples obstáculos, la topología, por medio de los complejos simpliciales y algunos
otros de sus elementos, nos ha dado luz en el campo de la computación, al tiempo que nos ha permitido
imaginar varios objetos geométricos singularmente bellos. A continuación presento algunos acertijos, que
aunque muestran situaciones idealizadas, nos permiten aproximarnos a un estudio de la aplicación de la
topología ya mencionada durante esta introducción. Las ideas presentadas a lo largo de esta tesis se han
basado principalmente en el libro [Rajsbaum et al., 2014] y en el artículo [Kozlov, 2012]. En particular,
los siguientes ejemplos fueron tomados de [Rajsbaum et al., 2014]. Algunos temas relacionados se han
desarrollado con otro enfoque en el trabajo de Velázquez Cervantes [2019].
1.1. El problema de las niñas enlodadas 4
Pensemos en el siguiente problema:
2Dado que esta característica es también parte esencial de los sistemas distribuidos, no haremos gran distinción al hablar
de sistemas distribuidos y concurrentes.
3Traducción libre.
4Del inglés “muddy children”, que puede traducirse al español como “las niñas enlodadas” o “los niños enlodados”.
1.1. EL PROBLEMA DE LAS NIÑAS ENLODADAS 3
Un grupo de niñas está jugando en el jardín y algunas de ellas teminan con lodo en la frente. Cada
niña puede ver las frentes de las demás niñas, pero no la suya. Al mediodía, su maestro las convoca y
les dice: “Al menos una de ustedes tiene lodo en la frente. No está permitido que se comuniquen las
unas con las otras acerca de esto de ninguna manera. Pero, cuando estén seguras de que están sucias,
deben anunciarlo a todos, exactamente a la hora.” Las niñas continúan jugando normalmente y nadie
menciona el estado de la frente de nadie más. Hay seis niñas con lodo en la frente, y a las 6:00 p. m.
todas anuncian que están sucias. ¿Cómo es esto posible? [Rajsbaum et al., 2014, p. 13]
En la descripción del problema, se nos dice que al final todas las niñas anuncian que están sucias. Sin em-
bargo, para poder explicarlo, tomaremos en cuenta el número de niñas que podrían estar sucias. Es decir,
el primer caso que analizaremos será cuando sólo una niña está sucia, luego veremos qué pasa cuando
dos niñas están sucias, en seguida veremos cómo es el procedimiento para tres niñas, y así sucesivamente.
Para comenzar, pensemos que sólo hay una niña sucia. Cuando el maestro da el anuncio a las 12:00 del
mediodía, la niña que tiene lodo en la frente se da cuenta de que las demás no están sucias. Por lo tanto,
decide anunciar a la 1:00 p. m. que ella está sucia.
Ahora, ¿qué sucede cuando dos niñas están sucias? A las 12:00 del mediodía todas escuchan el anuncio
del maestro. Una de las niñas que están sucias, digamos A, se da cuenta de que hay otra niña sucia,
digamos B. Entonces A no está segura de que ella está sucia. Sin embargo, a la 1:00 p. m. nadie anuncia
que está sucia, y A razona que si nadie está segura de que está sucia y entre ellas está B, es porque B
debe estar viendo a otra niña sucia, que debe ser ella. Así, A se asegura de que ella está sucia. Por otro
lado, B sigue el mismo razonamiento que A. Por lo tanto, al dar las 2:00 p. m., A y B dan el anuncio de
que están sucias.
En tercer lugar, veamos qué pasa con el caso de tres niñas sucias. Como antes, el maestro da el anuncio a
las 12:00 del mediodía. Una de las niñas que están sucias, llamémosle nuevamenteA, ve a otras dos niñas
sucias, digamos B y C, de manera que A no está segura de que ella esté sucia. A la 1:00 p. m. ninguna
niña anuncia que está sucia, y a las 2:00 p. m. tampoco, entonces A razona que B y C seguramente ven
a otra niña sucia. Como ella no ve otra niña sucia además de B y C, concluye que ella misma debe estar
sucia. El mismo razonamiento siguen B y C. Finalmente, a las 3:00 p. m. A, B y C anuncian que están
sucias.
Una explicación semejante se puede dar para el caso de cuatro, cinco y seis niñas sucias. De hecho,
si el número de niñas al inicio es mayor, también es válido el razonamiento inductivo de los párrafos
precedentes.
En cambio, cuando analizamos el problema de las niñas enlodadas con ayuda de complejos simpliciales,
este objeto geométrico nos proporciona información acerca de cuál es el estado inicial del conocimiento
de cada niña (o su valor de entrada) y cómo ese conocimiento se transforma una vez recibida la infor-
mación del maestro.
¿Qué es un complejo simplicial?
Aquí explicamos de manera intuitiva lo que es un complejo simplicial.
Un ejemplo de complejo simplicial puede ser una gráfica, cuyas aristas se unen (si es que se
unen) por uno de sus extremos.
4 CAPÍTULO 1. INTRODUCCIÓN
Sin embargo, no todos los complejos simpliciales son gráficas, sino que estos pueden in-
cluir (además de vértices y aristas) triángulos, tetraedros, y así sucesivamente, pueden tener
figuras de dimensiones cada vez mayores.
De manera similar a como pedimos que las aristas de una gráfica se unan − si lo hacen−
en un sólo vértice, a los triángulos y demás figuras también les pediremos una condición
parecida.
Comencemos por los triángulos, que además incluyen sus tres vértices y sus tres segmentos
rectilíneos. La condición de intersección que les imponemos es la siguiente, que obtuvimos
del libro [Giblin, 2010, pp. 39-40].
Dos triángulos o bien:
(I) son disjuntos, o bien
(II) tienen un vértice en común, o
(III) tienen dos vértices, y en consecuencia la arista entera que los une, en común.
(I) (II) (III)
Figura 1.1: Condición de intersección para triángulos.
Algunas configuraciones que no están permitidas son las de abajo:
Ahora, las figuras de dimensión tres que permitimos en un complejo simplicial son los te-
traedros, que además incluyen cuatro vértices, seis aristas y cuatro triángulos. Podríamos
extender la condición de intersección que se da en Giblin [2010] para nuestros tetraedros,
entonces tendríamos que imponer también los siguientes requisitos:
Dos tetraedros o bien:
(I) son disjuntos, o bien
(II) tienen un vértice en común, o
(III) tienen dos vértices, y en consecuencia la arista entera que los une, en común, o
(IV) están unidos por un triángulo en común.
1.1. EL PROBLEMA DE LAS NIÑAS ENLODADAS 5
(I) (II)
(III) (IV)
Figura 1.2: Condición de intersección para tetraedros.
No consideraremos en este momento figuras de dimensión más grande porque sería compli-
cado intentar representarlas geométricamente de una manera sencilla.
Por ahora, nos quedaremos con la noción de un complejo simplicial como la de una figura
en el espacio tridimensional formada por aristas, triángulos, vértices y tetraedros que cum-
plen las condiciones de intersección que describimos arriba. Así, los siguientes son todos
ejemplos de complejos simpliciales:
6 CAPÍTULO 1. INTRODUCCIÓN
La siguiente figura es el complejo simplicial que representa el problema de las niñas enlodadas, para el
caso donde sólo hay tres niñas.
0⊥1
10⊥
01⊥
1⊥0
⊥01 ⊥10
⊥00
⊥1 1
1⊥1 1 1⊥
0⊥000⊥
Figura 1.3: Complejo simplicial para el problema de las niñas enlodadas.
Para entender cómo están etiquetados los vértices, imaginemos que asignamos un número a cada niña,
por ejemplo 1, 2 y 3. En cada etiqueta hay tres cifras. La cifra de la primera posición representa el estado
de la niña 1, la cifra de la segunda posición representa el estado de la niña 2 y la cifra de la tercera posición
representa el estado de la niña 3.
Los estados posibles son los siguientes:
• 0 si está limpia
• 1 si está sucia
• ⊥ significa que la niña no sabe su estado
Así, por ejemplo, del vértice etiquetado como
1 ⊥ 0
podemos inferir que la niña 2 no sabe su estado, pero puede ver que la niña 1 está sucia y la niña 3 está
limpia.
Otro ejemplo: del vértice etiquetado como
1 ⊥ 1
podemos inferir que la niña 2 no sabe su estado, pero se da cuenta de que las niñas 1 y 3 están sucias.
Así, cada vértice representa un posible caso de lo que alguna de las niñas sabe antes del anuncio dado por
el maestro a las 12:00 del mediodía. La pertenencia de cada vértice a dos triángulos distintos representa
las únicas dos posibilidades para cada niña: estar limpia o estar sucia. Esto ocurre ya que cada triángulo
del complejo simplicial representa un posible estado de las tres niñas, es decir, cada triángulo es un
1.1. EL PROBLEMA DE LAS NIÑAS ENLODADAS 7
mundo posible. Por ejemplo, el triángulo superior representa el caso en que todas las niñas están limpias
y el triángulo inferior el caso en que todas están sucias.
Como cada niña ve a las otras pero no se ve a sí misma, puede estar en dos triángulos a la vez. Esto
representa la incertidumbre de la niña al no saber si está limpia o sucia: en un triángulo las otras dos
niñas la ven limpia y en el otro las otras dos niñas la ven sucia.
Para sintetizar, el complejo simplicial representa todas las posibilidades compatibles con la información
que se tiene. En consecuencia, este complejo simplicial evoluciona cuando las niñas reciben información,
lo cual sucede cada hora a partir de las 12:00 del mediodía. Recordemos que al mediodía las niñas reciben
la información de que “al menos una de ellas tiene lodo en la frente”. Posteriormente, a la 1:00 p. m.
las niñas saben quién de ellas se anunció, lo cual para ellas es información adicional. A las 2:00 p. m.
también reciben información acerca de quién se anunció a esa hora, y así sucesivamente.
La información recibida a cada hora permite descartar mundos posibles, lo cual se refleja en el complejo
simplicial como quitar los triángulos que no coincidan con la información recibida. Partimos del complejo
simplicial completo, que es la siguiente figura:
En primer lugar, cuando las niñas reciben el anuncio del maestro a las 12:00 del mediodía, se puede
eliminar el triángulo superior, pues ya no existe el caso en que las tres niñas están limpias:
Cuando da la 1:00 p. m. y ninguna niña se ha anunciado, las tres saben que ninguna de ellas está segura de
estar sucia. Esto significa que hay más de una niña enlodada. Con esta información adicional, se pueden
descartar los siguientes tres triángulos, de arriba hacia abajo:
8 CAPÍTULO 1. INTRODUCCIÓN
Si dan las 2:00 p. m. y ninguna niña se ha anunciado, todas reciben la información adicional de que no
hay sólo dos niñas sucias (ya que de haber sido sólo dos, se habrían anunciado a esa hora). Por lo tanto,
este nuevo conocimiento nos permite eliminar los siguientes tres triángulos:
Como resultado, nos quedamos con un sólo triángulo, pues con la información recibida sólo cabe la
posibilidad de que las tres niñas estén sucias. Por ese motivo, a las 3:00 p. m. las tres niñas pueden estar
seguras de que todas están sucias y anunciarse.
Cabe mencionar que la situación aquí descrita es un problema ideal pues no hay fallas en la comunica-
ción de las niñas, y éstas tampoco se comportan mal o se duermen. Además, el razonamiento de las niñas
siempre es el esperado o adecuado para determinar su situación. Empero, ya vimos que en el caso de los
procesos concurrentes, pueden haber errores. Una forma de subsanarlos podría ser cambiar la operación
de quitar un triángulo por la de reemplazarlo con otros. Si la lectora o lector quisiera indagar más profun-
damente en estos temas, le recomendamos consultar el libro −en el que nos hemos apoyado− [Rajsbaum
et al., 2014].
1.2. El problema del ataque coordenado
Imaginemos dos situaciones de nuestro día a día. La primera consiste en hacer una transferencia de
dinero a otra cuenta desde nuestro celular. En este caso, el banco necesita estar seguro de que el saldo
de nuestra cuenta disminuyó y el de la cuenta de nuestro destinatario aumentó. Más aún, estas dos cosas
tienen que pasar al mismo tiempo (o casi). En contraste, podemos encontrarnos otros contextos donde
las operaciones no ocurren de manera simultánea. Por ejemplo, cuando enviamos un correo importante
a otra persona (digamos, a nuestro director de tesis), nos gustaría saber que lo recibió. Puede ser que tal
persona nos responda, pero si ella o él considera primordial asegurarse de que recibimos su respuesta,
tendremos que responderle. Entonces nosotros no sabremos si recibió nuestra respuesta, a menos que nos
vuelva a responder. En este caso, de nuevo, la otra persona no sabrá si recibimos su respuesta, a menos
que le respondamos. En ese caso, no sabremos si recibió nuestra respuesta... y así ad infinitum.
El siguiente problema está relacionado con los dos anteriores, pues se presenta una situación en que dos
cosas deben ocurrir al mismo tiempo o no ocurrir (aunque ahora sí es un asunto de “vida o muerte”).
Dos divisiones del ejército, una comandada por la generala Alice y otra por el general Bob, acampan
en la parte de arriba de dos colinas que miran hacia un valle. El enemigo acampa en el valle. Si ambas
divisiones atacan simultáneamente, ganarán, pero si una división ataca sola, será vencida. Como resul-
tado, ningún general atacará sin una garantía de que el otro atacará al mismo tiempo. En particular,
ningún general atacará sin comunicarse con el otro.
1.2. EL PROBLEMA DEL ATAQUE COORDENADO 9
Mientras las divisiones están desplegadas en la cima de las colinas, los generales no han acordado si
atacar o no, ni a qué hora hacerlo. Ahora Alice decide programar un ataque. Los generales se pueden
comunicar sólo por medio de mensajeros. Normalmente toma a un mensajero exactamente una hora
llegar de un campamento a otro. Sin embargo, es posible que se pierda en la oscuridad o, aún peor, sea
capturado por el enemigo. Afortunadamente, en esta noche en particular todos los mensajeros llegan a
salvo. ¿Cuánto tiempo tomará a Alice y Bob coordinar sus ataques? [Rajsbaum et al., 2014, p. 16]
Supondremos que todos los mensajes se entregan satisfactoriamente y que Alice y Bob no pueden retrac-
tarse: deben atacar.
Como en el ejemplo de las niñas enlodadas, supondremos que los mensajes se entregan cada hora. La
primera en enviar un mensaje, que dice “¡Ataquemos al amanecer!”, es Alice. Esta comunicación es
entregada a Bob a la 1:00 p. m. Sin embargo, Alice se encuentra indecisa para atacar, pues no sabe si
Bob recibió su mensaje. Luego Bob, quien imagina la incertidumbre que debe estar invadiendo a Alice,
le envía un mensaje en respuesta, que le llega a Alice a las 2:00 p. m. ¿Eso resuelve el problema? No,
puesto que ahora Bob no está seguro de atacar, ya que no sabe si su respuesta le llegó a Alice. Enseguida,
Alice decide responder a Bob, pero ahora se encuentra en el mismo dilema del inicio...
Algo que podemos concluir es que, aunque Alice y Bob sigan respondiéndose n número de veces, no
podrán ponerse de acuerdo, a pesar de que todos sus mensajes se entregaron.
De la misma forma en que lo hicimos para el ejemplo de la sección anterior, examinaremos un complejo
simplicial que retrata las circunstancias de lo acontecido entre Alice y Bob.
¡Ataquemos al amanecer! ¡Ataquemos al mediodía!
12:00 del mediodía
Alice Bob Alice
Entregado EntregadoPerdido
1:00 p. m.
Bob Alice Bob Alice Bob
Entregado EntregadoPerdido Perdido
2:00 p. m.
Alice AliceBob Bob BobAlice Alice
Notemos que ahora nuestro complejo simplicial ¡es una gráfica!
10 CAPÍTULO 1. INTRODUCCIÓN
La parte superior de la figura −la primera gráfica− representa las dos opciones iniciales que puede elegir
Alice: el vértice de más a la izquierda es cuando Alice manda un mensaje de “¡ataquemos al amanecer!”
y el de más a la derecha cuando manda un mensaje de “¡ataquemos al mediodía!”. En cambio, como Bob
no ha recibido mensaje de Alice ni enviado nada, entonces está representado por el vértice de en medio.
Esto quiere decir que Bob no sabe cuándo atacar y podría optar por cualquiera de las dos opciones que
proponga Alice.
La segunda gráfica muestra lo que pasa a la 1:00 p. m. Recordemos que a esta hora, Bob ya recibió el
mensaje de Alice. El vértice de más a la izquierda es cuando Bob recibió el mensaje de “¡ataquemos al
amanecer”; el de más a la derecha, cuando recibió el mensaje de “¡ataquemos al mediodía!” y el vértice
central, cuando Bob no recibió ningún mensaje. Los dos vértices sin etiquetar que se encuentran entre los
de Bob, son los posibles estados de Alice, quien ahora tiene incertidumbre: en el de la izquierda no sabe
si le llegó su mensaje de “¡ataquemos al amanecer!” a Bob o no le llegó nada; en el de la derecha no sabe
si le llegó su mensaje de “¡ataquemos al mediodía!” a Bob o si él no recibió ningún mensaje.
En la tercera gráfica se representa lo que pasa a las 2:00 p. m. cuando Bob ya envió su respuesta a Alice.
Los vértices de los extremos muestran el caso en que los respectivos mensajes se entregaron y los vértices
del medio, el caso en que se perdieron. Este procedimiento se puede continuar un número arbitrario de
veces y la gráfica siempre se va a seguir pareciendo a esta última: en el tiempo t será una gráfica de 2t+2
aristas, los vértices de en medio serán los casos en que los mensajes se perdieron y los de los extremos,
en que se entregaron.
Finalmente, podemos darnos cuenta de que Alice y Bob nunca se podrán poner de acuerdo pues, de ser
posible el acuerdo, tendríamos que obtener en algún momento (es decir, en algún tiempo t) una gráfica
donde un vértice de Alice y uno de Bob, etiquetados con el mismo mensaje, estuvieran unidos por una
sola arista. En este caso, nuestra gráfica sería disconexa, como se muestra en la Figura 1.4. Sin embargo,
en las gráficas que hemos obtenido hasta ahora, esto nunca ocurre. En cambio, siempre podemos llegar
de un vértice etiquetado con un mensaje a otro con uno distinto siguiendo las aristas de la gráfica, lo que
nos indica que en algún momento los generales podrían haber tomado decisiones que no concordaran.
¡Ataquemos al amanecer! ¡No ataquemos! ¡Ataquemos al mediodía!
Figura 1.4
Así, los complejos simpliciales junto con una propiedad topológica que se llama conexidad, nos permiten
saber si este problema tiene o no solución.
1.3. Estructura de la tesis
La manera en que está organizada la presente tesis se detalla a continuación:
• En el primer capítulo, se da una introducción a los complejos simpliciales por medio de ejemplos
que han servido para la resolución de problemas de computación distribuida.
1.3. ESTRUCTURA DE LA TESIS 11
• En el segundo capítulo, se introducen formalmente algunos conceptos preliminares como son los de
complejo simplicial abstracto y geométrico, así como algunos conceptos de la teoría de categorías
que se utilizarán más adelante.
• En el tercer capítulo, se estudia la subdivisión cromática de un simplejo. En esta parte se prue-
ban algunos resultados acerca del número de vértices, aristas, triángulos y demás simplejos del
complejo simplicial que es la subdivisión cromática. Cabe mencionar que se da una descripción
combinatoria de la subdivisión cromática de un complejo simplicial que parte de su construcción a
partir de diagramas de Schlegel.
• En el cuarto capítulo, definimos la subdivisión cromática de un complejo simplicial con ayuda de
la teoría de categorías.
• En el quinto capítulo, con la teoría desarrollada anteriormente, se aborda un problema planteado
en el libro Por la senda de los círculos [Neve y Rosales, 2017, p. 46], el cual también estudiamos
simultáneamente con base en la solución propuesta en la Stanford Encyclopedia of Philosophy.
• En el sexto y último capítulo se dan algunas observaciones finales acerca del presente trabajo de
tesis.
12 CAPÍTULO 1. INTRODUCCIÓN
Capítulo 2
Preliminares
En el presente capítulo, con el propósito de facilitar la lectura y convenir la notación usada en esta tesis,
exponemos algunos conceptos preliminares que nos servirán para entender la subdivisión cromática de
un simplejo y de un complejo simplicial. Se incluyen nociones acerca de la teoría de categorías ya que en
el artículo [Kozlov, 2012], el autor hace uso de éstas para aproximarse a la subdivisión cromática de un
complejo simplicial. Varias de las ideas contenidas en este apartado serán utilizadas también en el último
capítulo para estudiar el problema de “La isla de los muertos”.
2.1. Complejos simpliciales
Veamos ahora las definiciones correspondientes a los complejos simpliciales geométricos y los complejos
simpliciales abstractos.
2.1.1. Complejos simpliciales geométricos
Los conceptos presentados en esta parte fueron obtenidos de Giblin [2010].
Definición 1 (Vectores afínmente independientes). Sean v0, . . . , vn, n + 1 vectores en Rm, con n ≥ 1.
Dichos vectores son llamados afínmente independientes (a-independientes) si v1−v0, . . . , vn−v0 son
linealmente independientes. Por convención, si n = 0 entonces el vector v0 es siempre a-independiente
(aún si es cero).
Definición 2 (Vector afínmente dependiente y combinación afín). Sean v0, . . . , vn vectores en Rm. Se
dice que un vector v es afínmente dependiente (a-dependiente) de ellos si existen números reales
λ0, . . . , λn tales que
λ0 + · · · + λn = 1 y v = λ0v
0 + · · · + λnv
n.
En este caso, también se dice que v es una combinación afín de los vectores v0, . . . , vn.
Proposición 1. Sean v0, . . . , vn a-independientes y sea v a-dependiente de ellos. Entonces existen únicos
números reales λ0, . . . , λn tales que
∑
λi = 1 y v =
∑
λiv
i. Los λ’s son llamados las coordenadas
baricéntricas de v respecto a v0, . . . , vn.
13
14 CAPÍTULO 2. PRELIMINARES
Definición 3 (Simplejo geométrico, interior, simplejo geométrico abierto y frontera). Sean v0, . . . , vn
a-independientes. El simplejo geométrico (cerrado) con vértices v0, . . . , vn es el conjunto de puntos a-
dependientes en v0, . . . , vn y con cada coordenada baricéntrica ≥ 0. También se dice que el simplejo
geométrico está generado por v0, . . . , vn. Los puntos cuyas coordenadas son todas > 0 son llamados
el interior del simplejo geométrico, y el conjunto de puntos interiores a veces es llamado el simplejo
geométrico abierto con vértices v0, . . . , vn. La frontera del simplejo geométrico consiste de aquellos
puntos que no son interiores, es decir, que tienen al menos una coordenada baricéntrica = 0.
Definición 4 (Cara y cara propia de un simplejo geométrico). Sea sn = (v0 . . . vn) un simplejo geomé-
trico. Una cara de sn es un simplejo1 cuyos vértices forman un subconjunto (no vacío) de {v0, . . . , vn}.
Si el subconjunto es propio (es decir, no todo el conjunto {v0, . . . , vn}) decimos que la cara es una cara
propia. Si sp es una cara de sn escribimos sp < sn o bien sn > sp; observe que sn < sn para cualquier
simplejo sn.
Definición 5 (Complejo simplicial geométrico). Un complejo simplicial geométrico es un conjunto
finito K de simplejos en Rm que cumple las siguientes dos propiedades:
(I) Si s ∈ K y t < s (t es una cara de s), entonces t ∈ K
(II) Condición de intersección: Si s ∈ K y t ∈ K entonces s ∩ t es el vacío o es una cara tanto de s
como de t.
La dimensión de K es la dimensión del simplejo más grande en K.
Definición 6 (Espacio subyacente). El espacio subyacente de K, denotado como |K|, es el conjunto de
puntos en Rm que pertenecen al menos a un simplejo de K. Es decir, |K| es la unión de simplejos de K. En
ocasiones, si Σ es simplemente un conjunto de simplejos, usamos |Σ| para denotar la unión de simplejos
en Σ.
Definición 7 (Subcomplejo y complejo simplicial orientado). Se definen como sigue:
1. Un subcomplejo de un complejo simplicial geométrico K es un subconjunto L de K que es un
complejo simplicial geométrico en sí mismo. (Esto pasa si y sólo si L tiene la propiedad de que
s ∈ L & t < s⇒ t ∈ L). El subcomplejo K es llamado propio si L 6= K.
2. Un complejo simplicial orientado es un complejo simplicial en el que cada simplejo está provisto
de una orientación.
Definición 8 (Poliedro). Un subconjunto U de Rm que es el espacio subyacente de algún complejo
simplicial geométrico, es llamado poliedro.
Definición 9 (Triangulación). Un complejo simplicial geométrico cuyo espacio subyacente es un poliedro
dado U, es llamado una triangulación de U.
Definición 10 (Cerradura). Sea Σ un conjunto de simplejos de K. La cerradura de Σ (en K) es el sub-
complejo más pequeño de K que contiene a Σ, i.e. se define como:
Σ = {s ∈ K | s < t para algún t ∈ Σ}.
1A partir de ahora, pero sólo en esta sección, cuando hablemos de un “simplejo” nos estaremos refiriendo a un simplejo
geométrico.
2.1. COMPLEJOS SIMPLICIALES 15
Definición 11 (Estrella y estrella cerrada). Sea Σ un conjunto de simplejos de K. La estrella de Σ (en K)
está definida como:
St(Σ) = St(Σ,K) = {s ∈ K | s > t para algún t ∈ Σ}.2
La estrella cerrada de Σ (en K) es la cerradura de la estrella de Σ, y se denota como St(Σ) o como
St(Σ,K). Entonces:
St(Σ) = {u ∈ K | ∃t ∈ Σ y s ∈ K con s > u y s > t}
y St(Σ) es un subcomplejo de K.
Definición 12 (Simplejos acoplables y su yunta). Sean sp = (v0 . . . vp) y sq = (w0 . . . wq) simplejos en
RN. Los simplejos sp y sq son llamados acoplables si los p+ q+ 2 vectores v0, . . . , vp, w0, . . . , wq son
afínmente independientes, y en tal caso su yunta es el p+ q+ 1−simplejo spsq = (v0 . . . vpw0 . . . wq).
Definición 13 (Complejos simpliciales geométricos acoplables y su yunta). Dos complejos simpliciales
geométricos K y L en Rm son llamados acoplables si:
1) para cada s ∈ K y t ∈ L, s y t son acoplables, y si
2) cualesquiera dos uniones st y s ′t ′ se intersectan, a lo más, en una cara común de st y s ′t ′.
La yunta KL de K y L es entonces el complejo simplicial geométrico
KL = K ∪ L ∪ {st : s ∈ K y t ∈ L}.
Definición 14 (Enlace o aureola). Sea s ∈ K. El enlace o aureola de s en K está definido por
Lk(s) = Lk(s, K) = {t ∈ K : st ∈ K}.3
Donde st ∈ K significa que:
I) s y t son acoplables y
II) la yunta st pertenece a K.
De manera que Lk(s) es un subcomplejo de K.
Definición 15 (Subdivisión). Sea K un complejo simplicial geométrico. Un complejo simplicial geomé-
trico K1 es una subdivisión de K si:
1) |K1| = |K|
2) Para todo s1 ∈ K1 existe s ∈ K tal que s1 ⊂ s.
2La notación St viene del inglés star.
3La notación Lk viene del inglés link.
16 CAPÍTULO 2. PRELIMINARES
2.1.2. Complejos simpliciales abstractos
Ahora definimos los complejos simpliciales abstractos y algunos conceptos asociados siguiendo a Kozlov
[2008] y en la parte final también a Giblin [2010].
Definición 16 (Complejo simplicial abstracto finito). Un complejo simplicial abstracto4 finito es un
conjunto finito A junto con una colección ∆ de subconjuntos de A tales que si X ∈ ∆ y Y ⊆ X, entonces
Y ∈ ∆.
Denotamos este complejo simplicial abstracto finito simplemente como ∆. El elemento v ∈ A tal que
{v} ∈ ∆ es llamado un vértice de ∆. Denotamos el conjunto de todos los vértices de ∆ como V(∆).
Cuando ∆ consiste de todos los subconjuntos de A, es llamado un simplejo y se denota como ∆A. De
forma semejante, los conjuntos δ ∈ ∆ son llamados simplejos de ∆. Aquellos simplejos δ ∈ ∆ que no
están contenidos en ningún otro simplejo de ∆ son llamados maximales.
Ejemplo 1. La colección de conjuntos {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}} es un complejo simplicial abs-
tracto. Para obtener el simplejo ∆{1,2,3} se necesitaría añadir a esta colección el conjunto {1, 2, 3}.
Definición 17 (Subcomplejo simplicial abstracto). Dados dos complejos simpliciales abstractos finitos
∆1 y ∆2 tales que σ ∈ ∆1 implica que σ ∈ ∆2, decimos que ∆1 es un subcomplejo simplicial abstracto
de ∆2 y escribimos ∆1 ⊆ ∆2. Si además existe σ ∈ ∆2 tal que σ 6∈ ∆1, decimos que ∆1 es un subcomplejo
propio de ∆2.
Definición 18 (Dimensión). La dimensión de un simplejo es la cardinalidad del simplejo menos 1. Cuan-
do un simplejo tiene dimensión d, le llamamos un d-simplejo. Los vértices tienen dimensión 0. Para los
complejos simpliciales abstractos finitos la dimensión se define como el máximo de las dimensiones de
sus simplejos. La dimensión se denota como dim. Si ∆1 es un subcomplejo simplicial abstracto de ∆2
entonces dim∆1 ≤ dim∆2.
Definición 19 (d-esqueleto). Para cualquier complejo simplicial abstracto finito ∆, la colección de todos
los simplejos de ∆ desde la dimensión 0 hasta la dimensión d es llamado el d-esqueleto de ∆ y se denota
como ∆(d) o Skd(∆).
Observación 1. Acerca del nulo y del vacío.
En la Definición 16 permitimos que ∆ sea la colección vacía de conjuntos, es decir, ∆ = ∅. El complejo
simplicial abstracto correspondiente es llamado el complejo simplicial abstracto nulo y se denota como
∅ o como {}. El complejo simplicial abstracto nulo es el único que no contiene al conjunto vacío como
uno de sus simplejos.
De manera alternativa, podemos tener también la colección que consiste solamente del conjunto vacío,
es decir, ∆ = {∅}. El correspondiente complejo simplicial abstracto es llamado el complejo simplicial
abstracto vacío y se denota como {∅}. Nótese que los conjuntos de vértices de los complejos simpliciales
nulo y vacío son conjuntos vacíos.
Observación 2. Las dimensiones del simplejo vacío y del complejo nulo.
Al determinar la dimensión, uno debería tener en mente el caso degenerado del simplejo ∅ ∈ ∆. Por
definición, como la cardinalidad del conjunto vacío es 0, la dimensión de este simplejo es igual a −1.
De manera correspondiente, la dimensión del complejo simplicial vacío es igual a −1. Establecemos la
dimensión del complejo simplicial nulo como −∞.
4En ocasiones la palabra “abstracto” es omitida por brevedad.
2.1. COMPLEJOS SIMPLICIALES 17
Observación 3. El término “simplejo”.
Anteriormente, usamos el término “simplejo” de dos maneras: primero, para denotar cualquier conjunto
que está en la colección de conjuntos ∆ que define un complejo simplicial abstracto; y segundo, para
denotar el complejo simplicial abstracto cuya colección consiste de todos los conjuntos en el conjunto
potencia deA, es decir,∆ = P(A). La distinción es puramente formal y la razón por la que normalmente
usamos el mismo término para estas dos nociones es que uno puede asociar a cada δ ∈ ∆ el simplejo
∆δ, que será un subcomplejo de ∆.
Definición 20 (Función simplicial). Sean ∆1 y ∆2 dos complejos simpliciales abstractos finitos. Una
función simplicial de ∆1 a ∆2 es una función f : V(∆1) → V(∆2) tal que si σ es un simplejo de ∆1
entonces f(σ) es un simplejo de ∆2. En tal situación, escribiremos simplemente f : ∆1 → ∆2.
Observación 4. En esta definición hemos usado la notación f(S) := {f(s) | s ∈ S} para cualquier con-
junto S y cualquier función f en S.
Ejemplo 2. Sean ∆1 = ∆2 = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}}. Entonces cualquier f : [3] → [3]5 es una
función simplicial, mientras que esto último no es cierto para ∆1 = ∆2 = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}}.
Definición 21 (Isomorfismo de complejos simpliciales abstractos). Sean ∆1 y ∆2 dos complejos simpli-
ciales abstractos y sea f : ∆1 → ∆2 una función simplicial entre ellos. Entonces f es llamada un isomor-
fismo de complejos simpliciales abstractos si la función inducida f : V(∆1) → V(∆2) es una biyección
y su inversa induce una función simplicial también. Si tal isomorfismo existe, entonces se dice que ∆1 y
∆2 son isomorfos como complejos simpliciales abstractos.
Definición 22 (Complejo simplicial abstracto). Un complejo simplicial abstracto es un conjunto A
junto con una colección ∆ de subconjuntos finitos de A tales que si X ∈ ∆ y Y ⊆ X entonces Y ∈ ∆.
Definición 23 (Complejo simplicial abstracto puro). Un complejo simplicial abstracto es llamado puro
si todos sus simplejos maximales tienen la misma dimensión.
Observación 5. Dos complejos simpliciales abstractos ∆1 y ∆2 son isomorfos si y sólo si existe una
biyección f : V(∆1) → V(∆2) con la propiedad de que:
{v0, . . . , vn} ∈ ∆1 ⇔ {f(v0), . . . , f(vn)} ∈ ∆2.
Observación 6. Cualquier complejo simplicial geométrico K determina un complejo simplicial abstracto
∆ mediante el siguiente procedimiento: tómese el conjunto de vértices de K y sea {v0, . . . , vn} ∈ ∆ si y
sólo si (v0 . . . vn) ∈ K.
Definición 24 (Complejos simpliciales geométricos isomorfos). Dos complejos simpliciales geométricos
son llamados isomorfos si los complejos simpliciales abstractos que determinan son isomorfos.
Definición 25 (Realización geométrica de un complejo simplicial abstracto). Una realización geomé-
trica de un complejo simplicial abstracto ∆ es un complejo simplicial geométrico K cuyo complejo
simplicial abstracto correspondiente es isomorfo a ∆.
Observación 7. Los vértices de un complejo simplicial geométrico K pueden ser etiquetados de manera
que un conjunto de vértices de K genere un n-simplejo de K si y sólo si el conjunto de vértices de ∆
correspondiente es un n-simplejo de ∆.
5Adoptaremos la notación [n] para denotar al conjunto [n] := {0, 1, . . . , n} con n ∈ N. Esto lo reiteramos al inicio del
siguiente capítulo.
18 CAPÍTULO 2. PRELIMINARES
Definición 26 (Subdivisión de un complejo simplicial abstracto). Sean∆ y∆1 dos complejos simpliciales
abstractos y sean K y K1 sus respectivas realizaciones. Decimos que ∆1 es una subdivisión de ∆ si y sólo
si K1 es una subdivisión (geométrica) de K.
Teorema 1. Todo complejo simplicial abstracto de dimensión n tiene una realización geométrica en
R2n+1. (Note que cualesquiera dos realizaciones del mismo complejo simplicial abstracto son, por defi-
nición, isomorfas).
2.2. Conceptos de la teoría de categorías
Los conceptos presentados en esta sección han sido obtenidos y estudiados también de Kozlov [2008].
Definición 27 (Categoría). Una categoría C es un par de clases6 (O,M) que satisfacen ciertas propie-
dades. La clase O es llamada la clase de objetos y la clase M es llamada la clase de morfismos.
La clase M es, de hecho, una unión disjunta de conjuntos M(a, b) para todo par a, b ∈ O, con una
regla de composición dada:
M(a, b) × M(b, c) → M(a, c), (m1,m2) → m2 ◦ m1.
Se requiere que esta regla de composición satisfaga los siguientes axiomas:
• Cuando está definida, la composición es asociativa.
• Para cada a ∈ O existe un (necesariamente único) morfismo identidad 1a ∈ M(a, a) tal que
1a ◦ f = f y g ◦ 1a = g, siempre que las composiciones estén definidas.
Definición 28 (Categoría pequeña). Una categoría C se llama pequeña si la clase de los objetos O(C) es
un conjunto.
Notación. Para un morfismo a m
−→ b, escribimos:
 a = domm o a = ∂•m y lo llamamos el dominio dem.
 b = codm o b = ∂•m y lo llamamos el contradominio dem.
Definición 29 (Categoría opuesta). Dada una categoría C, su categoría opuesta, denotada como Cop, es
la que obtenemos al “invertir todas las flechas”, es decir, O(Cop) = O(C) y para todo par de objetos
x, y ∈ O(C), tenemos MCop(x, y) = MC(y, x), con la misma regla de composición de C.
6Utilizamos la palabra clase para evitar entrar en las complicaciones de la teoría de conjuntos. Intuitivamente, esto signi-
fica que asumimos la existencia de un universoU que consiste de todos los conjuntos, y a los subconjuntos deU los llamamos
clases. El problema principal es que si tratamos de considerar todos los conjuntos con cierta propiedad, el cual es llamado
principio de comprensión, entonces podríamos obtener algo que no fuera un conjunto, sino una clase. El famoso ejemplo
de esto [llamado la Paradoja de Russell] es considerar todos los conjuntos que no se tienen a sí mismos como uno de sus
elementos. [Es decir, si consideramos el “conjunto” R = {x : x 6∈ x} entonces R cumple que R ∈ R si y sólo si R 6∈ R y esto
es una paradoja].
2.2. CONCEPTOS DE LA TEORÍA DE CATEGORÍAS 19
Definición 30 (Subcategoría y subcategoría completa). Dadas dos categorías C y D, decimos que D es
una subcategoría de C si:
• O(D) es una subclase de O(C),
• para cada x, y ∈ O(D) tenemos MD(x, y) ⊆ MC(x, y) y
• los morfismos identidad y la regla de composición en D se heredan de C.
Si, además, tenemos MD(x, y) = MC(x, y) para todo x, y en O(D), entonces decimos que D es una
subcategoría completa de C.
La siguiente terminología corresponde a la noción intuitiva de igualdad entre objetos.
Definición 31 (Inverso de un morfismo, isomorfismo, objetos isomorfos). Un morfismo m : a → b en
una categoría C es llamado un isomorfismo si existe un morfismo m̃ : b → a de C que satisface las
relaciones:
m ◦ m̃ = 1b, m̃ ◦ m = 1a.
Dicho morfismo es único ya que si h : b→ a es otro morfismo con las mismas propiedades, es decir,
m ◦ h = 1b, h ◦ m = 1a,
podemos concluir que
m̃ = m̃ ◦ 1b = m̃ ◦ m ◦ h = 1a ◦ h = h.
Al morfismo m̃ lo llamamos el inverso dem y lo denotamos comom−1.
Dos objetos son llamados isomorfos si existe un isomorfismo entre ellos.
Definición 32 (Automorfismo). Un automorfismo es un morfismom que tiene un inverso y cuyo domi-
nio coincide con su contradominio. Los automorfismos de un objeto fijo en la categoría forman un grupo
respecto a la composición.
A continuación damos algunos ejemplos de distintas categorías que podemos encontrar en varias ramas
de las matemáticas:
Ejemplo 3. La categoría de los conjuntos: Sets.
• La clase de objetos consiste de todos los conjuntos.
• Para dos conjuntos A y B, el conjunto M(A,B) consiste de todas las funciones A→ B.
Nótese que A y B son isomorfos en Sets si y sólo si tienen la misma cardinalidad.
20 CAPÍTULO 2. PRELIMINARES
Ejemplo 4. La categoría de los espacios topológicos: Top.
• La clase de objetos consiste de todos los espacios topológicos.
• Para dos espacios topológicos X y Y, el conjunto M(X, Y) consiste de todas las funciones conti-
nuas X→ Y.
Nótese que X y Y son isomorfos en Top si y sólo si X y Y son homeomorfos como espacios topológicos.
Ejemplo 5. La categoría de los grupos: Grp.
• La clase de objetos consiste de todos los grupos.
• Para dos grupos G y H, el conjunto M(G,H) consiste de todos los homomorfismos de grupos
G→ H.
Nótese que G y H son isomorfos en Grp si y sólo si los grupos G y H son isomorfos como grupos.
Ejemplo 6. La categoría de los grupos abelianos: Ab.
• La clase de objetos consiste de todos los grupos abelianos.
• Para dos grupos G y H, el conjunto M(G,H) consiste de todos los homomorfismos de grupos
G→ H.
Nótese que G y H son isomorfos en Ab si y sólo si los grupos abelianos G y H son isomorfos como
grupos.
Ejemplo 7. La categoría de los espacios vectoriales sobre el campo K: VectK.
• La clase de objetos consiste de todos los espacios vectoriales sobre el campo K.
• Para dos espacios vectoriales sobre el campo K, V y W, el conjunto M(V,W) consiste de todas
las transformaciones lineales V → W.
Nótese que V yW son isomorfos en VectK si y sólo si V yW son isomorfos como espacios vectoriales.
Ejemplo 8. La categoría de las gráficas7 Graphs.
• La clase de objetos consiste de todas las gráficas.
• Para dos gráficas T y G, el conjunto M(T,G) consiste de todos los homomorfismos de gráficas
T → G.
Recordaremos aquí la definición de un homomorfismo de gráficas y una propiedad importante de la
composición de homomorfismos de gráficas:
7En este trabajo, consideramos gráficas sin aristas múltiples.
2.2. CONCEPTOS DE LA TEORÍA DE CATEGORÍAS 21
Definición (Homomorfismo de gráficas). Para dos gráficas T y G, un homomorfismo de gráficas de T
a G es una función ϕ : V(T) → V(G) tal que si x, y ∈ V(T) están conectados por una arista entonces
ϕ(x) y ϕ(y) también están conectados por una arista.
En otras palabras, ϕ : V(T) → V(G) induce ϕ × ϕ : V(T) × V(T) → V(G) × V(G), y la condición
de que esta función sea un homomorfismo de gráficas se traduce en que
(ϕ×ϕ)(E(T)) ⊆ E(G).
Proposición. Si ϕ : T → G y ψ : G → H son homomorfismos de gráficas entonces la composición
ψ ◦ϕ : T → H es nuevamente un homomorfismo de gráficas.
Nótese que T y G son isomorfas en Graphs si y sólo si T y G son isomorfas como gráficas.
Ejemplo 9. La categoría de los complejos simpliciales abstractos: ASC.
• La clase de objetos consiste de todos los complejos simpliciales abstractos.
• Para dos complejos simpliciales abstractos∆1, ∆2 ∈ O(ASC), el conjunto de morfismos M(∆1, ∆2)
consiste de todas las funciones simpliciales ∆1 → ∆2.
Nótese que ∆1 y ∆2 son isomorfos en ASC si y sólo si son isomorfos como complejos simpliciales abs-
tractos.
Definición 33 (Objeto inicial y terminal). Se definen de la siguiente manera:
• Un objeto inicial de una categoría C es un objeto init ∈ O(C) tal que para cualquier objeto a ∈
O(C), existe un único morfismo init → a.
• Un objeto terminal de una categoría C es un objeto term ∈ O(C) tal que para cualquier objeto
a ∈ O(C), existe un único morfismo a→ term.
Proposición 2. En una categoría arbitraria C, cualesquiera dos objetos iniciales son isomorfos y cua-
lesquiera dos objetos terminales son isomorfos.
Definición 34 (Coproducto). Sea C una categoría y sean a y b dos objetos de C. El coproducto de a
y b es un objeto c = a
∐
b junto con morfismos α : a → c, β : b → c (llamados los morfismos
estructurales) que satisfacen la siguiente propiedad universal:
Para cualquier objeto d y morfismos α̃ : a→ d, β̃ : b→ d, existe un único morfismo γ : c→ d tal
que el diagrama en la Figura 2.1 conmuta, es decir,
α̃ = γ ◦ α
β̃ = γ ◦ β.
a
α //
α̃ 
c
γ

b
βoo
β̃
d
Figura 2.1: El diagrama universal del coproducto.
22 CAPÍTULO 2. PRELIMINARES
Definición 35 (Producto). Sea C una categoría y sean a y b dos objetos de C. El producto de a y b es
un objeto c = a
∏
b junto con morfismos α : c → a, β : c → b que satisfacen la siguiente propiedad
universal:
Para cualquier objeto d y morfismos α̃ : d→ a, β̃ : d→ b, existe un único morfismo γ : d→ c tal
que el diagrama en la Figura 2.2 conmuta, es decir,
α̃ = α ◦ γ
β̃ = β ◦ γ.
a c
αoo β // b
d
α̃
__
γ
OO
β̃
??
Figura 2.2: El diagrama universal del producto.
Definición 36 (Conjunto parcialmente ordenado o copo.). Un conjunto parcialmente ordenado o, sim-
plemente, un copo (P,≥) es un conjunto P junto con una relación ≥ que satisface las siguientes tres
propiedades:
1. Reflexividad: Para todo x ∈ P se tiene que x ≥ x.
2. Antisimetría: Para todo x, y ∈ P, si x ≥ y y y ≥ x entonces x = y.
3. Transitividad: Para todo x, y, z ∈ P, si x ≥ y y y ≥ z entonces x ≥ z.
Definición 37 (Latiz). Un conjunto parcialmente ordenado P es llamado una latiz si, visto como una
categoría, tiene productos y coproductos.
Definición 38 (Producto directo). Para gráficas arbitrarias T y G, el producto directo T × G se define
como sigue:
V(T × G) = V(T) × V(G)
y
E(T × G) = { {(x, y), (x ′, y ′)} | {x, x ′} ∈ E(T), {y, y ′} ∈ E(G) }.
Ejemplo 10. Sean T y G dos gráficas tales que
V(T) = {0, 1}, E(T) = { {0, 1} },
V(G) = {2, 3} y E(G) = { {2, 3} }.
2.2. CONCEPTOS DE LA TEORÍA DE CATEGORÍAS 23
1
0
(a) Gráfica T .
3
2
(b) Gráfica G.
Entonces
V(T × G) = { (0, 2), (0, 3), (1, 2), (1, 3) }
y
E(T × G) = { {(0, 2), (1, 3)}, {(1, 2), (0, 3)} }.
(0, 2)
(0, 3)
(1, 2)
(1, 3)
Figura 2.3: El producto directo T × G.
Proposición 3. Para gráficas arbitrarias T y G, su producto directo (junto con los homomorfismos de la
gráfica de proyección) y su producto categórico en Graphs coincide.
Definición 39. Sean ∆1 y ∆2 complejos simpliciales abstractos arbitrarios. Definimos ∆1
∏
∆2 como el
siguente complejo simplicial abstracto:
• Para el conjunto de vértices establecemos V(∆1
∏
∆2) := V(∆1) × V(∆2) y las proyecciones
correspondientes son p1 : V(∆1
∏
∆2) → V(∆1) y p2 : V(∆1
∏
∆2) → V(∆2).
• Los simplejos de ∆1
∏
∆2 están definidos por la regla que dice que σ ∈ ∆1
∏
∆2 si y sólo si
p1(σ) ∈ ∆1 y p2(σ) ∈ ∆2.
Los mapeos p1 y p2 de la Definición 39 en realidad inducen funciones simpliciales p1 : ∆1
∏
∆2 → ∆1 y
p2 : ∆1
∏
∆2 → ∆2.
Ejemplo 11. Consideremos los siguientes complejos simpliciales abstractos:
∆1 = { ∅, {0}, {1}, {0, 1} }
∆2 = { ∅, {2}, {3}, {2, 3} },
24 CAPÍTULO 2. PRELIMINARES
{1}
{0}
(a) Complejo simplicial ∆1.
{3}
{2}
(b) Complejo simplicial ∆2.
entonces
V(∆1) = {0, 1} y V(∆2) = {2, 3},
por lo cual
V
(
∆1
∏
∆2
)
= { (0, 2), (0, 3), (1, 2), (1, 3)}.
Entonces
∆1
∏
∆2 = { ∅, {(0, 2)}, {(0, 3)}, {(1, 2)}, {(1, 3)},
{(0, 2), (0, 3)}, {(0, 2), (1, 2)}, {(0, 2), (1, 3)},
{(0, 3), (1, 2)}, {(0, 3), (1, 3)}, {(1, 2), (1, 3)},
{(0, 2), (0, 3), (1, 2)}, {(0, 2), (0, 3), (1, 3)},
{(0, 2), (1, 2), (1, 3)}, {(0, 3), (1, 2), (1, 3)},
{(0, 2), (0, 3), (1, 2), (1, 3)} }.
De manera que el complejo simplicial∆1
∏
∆2 es (geométricamente) un tetraedro como el de la siguiente
figura:
{(0, 3)}
{(1, 3)}
{(1, 2)}
{(0, 2)}
Además, para cada simplejo σ ∈ ∆1
∏
∆2 se cumple que p1(σ) ∈ ∆1 y p2(σ) ∈ ∆2.
2.2. CONCEPTOS DE LA TEORÍA DE CATEGORÍAS 25
• Tomemos, por ejemplo, el simplejo σ = {(0, 2), (0, 3), (1, 2), (1, 3)} ∈ ∆1
∏
∆2.
Observemos que
p1(σ) = {0, 1} ∈ ∆1 y p2(σ) = {2, 3} ∈ ∆2.
• Otro ejemplo:
Tomemos el simplejo σ = {(1, 2), (1, 3)}, entonces
p1(σ) = {1} ∈ ∆1 y p2(σ) = {2, 3} ∈ ∆2.
Proposición 4. Para complejos simpliciales arbitrarios∆1 y∆2, el complejo simplicial abstracto∆1
∏
∆2,
junto con los mapeos proyección p1 y p2, es el producto categórico de ∆1 y ∆2 en ASC.
Proposición 5. Sea C una categoría arbitraria y sean a y b objetos de C. Cualesquiera dos coproductos
de a y b son isomorfos. También, cualesquiera dos productos de a y b son isomorfos.
Demostración. Mostraremos que cualesquiera dos productos de a y b son isomorfos. La demostración
de que cualesquiera dos coproductos de a y b son isomorfos es análoga.
En la categoría C consideremos dos productos de los objetos a y b: el primero formado por el objeto p
con los morfismos pa : p → a y pb : p → b, y el segundo formado por el objeto q con los morfismos
qa : q→ a y qb : q→ b.
Como p con los morfismos pa y pb es un producto, entonces por la propiedad universal de la Definición
35 existe un morfismo r : q→ p tal que
qa = pa ◦ r (2.1)
qb = pb ◦ r. (2.2)
(Ver Figura 2.4).
Análogamente, como q con los morfismos qa y qb es un producto, entonces nuevamente por la propiedad
universal de la Definición 35 existe un morfismo s : p→ q tal que
pa = qa ◦ s (2.3)
pb = qb ◦ s. (2.4)
(Ver Figura 2.5).
a p
paoo pb // b
q
qa
^^
r
OO
qb
@@
Figura 2.4
a q
qaoo qb // b
p
pa
^^
s
OO
pb
@@
Figura 2.5
26 CAPÍTULO 2. PRELIMINARES
Ahora, si vemos al objeto p con pa y pb como un producto, por la propiedad universal de la Definición
35, para el mismo objeto p con los morfismos pa y pb existe un único morfismo t : p→ p tal que
pa = pa ◦ t
pb = pb ◦ t.
(2.5)
(Ver Figura 2.6).
a p
paoo pb // b
p
pa
^^
t
OO
pb
@@
Figura 2.6
Un morfismo que cumple las relaciones 2.5 es t = 1p.
Por otro lado, veamos que el morfismo t = r ◦ s también cumple las relaciones 2.5.
Al sustituir 2.1 en 2.3 obtenemos
pa = pa ◦ (r ◦ s)
y al sustituir 2.2 en 2.4 tenemos que
pb = pb ◦ (r ◦ s).
Así, como t es único, podemos concluir que
r ◦ s = 1p. (2.6)
De manera semejante veremos que s ◦ r = 1q.
Como q es un producto, por la propiedad universal de la Definición 35, para el objeto q con los morfismos
qa y qb existe un único morfismom : q→ q tal que
qa = qa ◦ m
qb = qb ◦ m.
(2.7)
(Ver Figura 2.7).
2.2. CONCEPTOS DE LA TEORÍA DE CATEGORÍAS 27
a q
qaoo qb // b
q
qa
^^
m
OO
qb
@@
Figura 2.7
Observemos quem = 1q cumple las relaciones 2.7.
Además t = s ◦ r también cumple las relaciones 2.7, ya que al sustituir 2.3 en 2.1 obtenemos
qa = qa ◦ (s ◦ r)
y al sustituir 2.4 en 2.2 tenemos que
qb = qb ◦ (s ◦ r).
Comom es único, podemos concluir que
s ◦ r = 1q. (2.8)
De acuerdo a las igualdades 2.6 y 2.8 tenemos que
r ◦ s = 1p y s ◦ r = 1q
por lo que r y s son morfismos inversos, de acuerdo a la Definición 31.
Por lo tanto, los productos p y q son isomorfos.

Definición 40 (Funtor). Dadas dos categorías C1 y C2, un funtor F : C1 → C2 es un par de funciones
FO : O(C1) → O(C2) y FM : M(C1) → M(C2) tales que:
• FM(M(x, y)) ⊆ M(FO(x), FO(y)) para todo x, y ∈ O(C1);
• FM(ida) = idFO(a) para todo a ∈ O(C1)
• FM(m1 ◦ m2) = FM(m1) ◦ FM(m2), para todom1,m2 ∈ M(C1)
Definición 41. La categoría de las categorías pequeñas, Cat, se define como sigue:
• La clase de los objetos de Cat consiste de todas las categorías pequeñas;
• Para dos categorías pequeñas C1 y C2, el conjunto M(C1, C2) consiste de todos los funtores C1 → C2.
28 CAPÍTULO 2. PRELIMINARES
Definición 42 (Pozo o sumidero). Sean C1 y C2 dos categorías y sea F : C1 → C2 un funtor. Llamamos
pozo o sumidero de F a un objeto L de C2 junto con una colección de morfismos que apuntan de los
objetos en el diagrama al objeto L, i.e., F(a) λa−→ L, para todo a ∈ O(C1), tales que estos nuevos mor-
fismos conmutan apropiadamente con los antiguos morfismos en el diagrama. Formalmente, requerimos
que para todom ∈ MC1
(a1, a2) tengamos que λa2 ◦ F(m) = λa1 (ver Figura 2.8).
a1
F //
m

F(a1)
λa1
!!
F(m)

L
a2
F // F(a2)
λa2
==
Figura 2.8
Definición 43 (Colímite). Dado un funtor F : C1 → C2, llamamos a un pozo de F, (L, {λa}a∈ O(C1)), su
colímite si éste es universal, es decir, para cualquier otro pozo (L̃, {λ̃a}a∈ O(C1)) existe un único morfismo
L
ϕ
−→ L̃ tal que λ̃a = ϕ ◦ λa, para todo a ∈ O(C1). Escribimos L = colim F.
Una noción dual importante de la noción de colímite, es la de límite. Esta se obtiene de la definición de
colímite al invertir todas las flechas.
Definición 44 (Fuente). Sean C1 y C2 dos categorías y sea F : C1 → C2 un funtor. Llamamos fuente de
F a un objeto L de C2, junto con una colección de morfismos L λa−→ F(a), para todo a ∈ O(C1), tal que
para todom ∈ MC1
(a1, a2) tenemos F(m) ◦ λa1 = λa2 (ver Figura 2.9).
a1
F //
m

F(a1)
F(m)

L
λa1
aa
λa2}}
a2
F // F(a2)
Figura 2.9
Definición 45 (Límite). Dado un funtor F : C1 → C2, llamamos a una fuente de F, (L, {λa}a∈ O(C1)), su
límite si éste es universal, es decir, para cualquier otra fuente (L̃, {λ̃a}a∈ O(C1)) existe un único morfismo
L̃
ϕ
−→ L tal que λ̃a = λa ◦ϕ, para todo a ∈ O(C1). Escribimos L = lim F.
2.3. Conclusión
Una vez que hemos recopilado los conceptos anteriores y explicado algunos de ellos, estamos listos para
estudiar la construcción general de la subdivisión cromática de un simplejo y de un complejo simplicial,
2.3. CONCLUSIÓN 29
desde los puntos de vista geométrico, abstracto y de la teoría de categorías. En particular, estamos en
condiciones de aplicar los conceptos de colímite y de la categoría de los complejos simpliciales abstractos
ASC, lo cual es esencial para entender las ideas planteadas por Kozlov en su artículo [Kozlov, 2012].
30 CAPÍTULO 2. PRELIMINARES
Capítulo 3
Subdivisión cromática de un simplejo
En el presente capítulo definiremos el concepto central de este trabajo de tesis y analizaremos algunas de
sus propiedades, así como su interpretación en la computación distribuida1. Para comenzar, nos resulta
conveniente adoptar la siguiente notación:
Notación. Sea n ∈ N.
[n] := {0, 1, . . . , n}.
Notación. ∆n denota al simplejo (abstracto) n-dimensional.
Ejemplo 12. Los siguientes cuatro son ejemplos de simplejos n-dimensionales, para n = 0, 1, 2 y 3.
∆0 ∆1 ∆2 ∆3
Desafortunadamente, los simplejos de dimensión mayor a tres son difíciles de dibujar, pero esperamos
que estos ejemplos sean útiles para dar una idea de cómo va aumentando la dimensión y el número de
vértices de los simplejos. Las cuatro figuras anteriores son representaciones de los simplejos geométri-
cos, sin embargo, debemos tener en mente que en realidad consideramos simplejos abstractos para el
desarrollo de la teoría, a menos que indiquemos otra cosa.
Ahora sí, presentamos nuestra definición principal (a la que también podríamos llamar “definición estre-
lla”, por su importancia en este trabajo).
-» ⋆ «-
Definición 46 (Subdivisión cromática). [Kozlov, 2012] Sean n un número natural y ∆n un simplejo n-
dimensional. El complejo simplicial χ(∆n) es llamado la subdivisión cromática de ∆n y es un complejo
n-dimensional abstracto puro definido como sigue:
1En este capítulo, el problema de los desenlaces de una carrera de caballos nos facilita la interpretación de una ejecución
de cierto número de procesos en la computación distribuida.
31
32 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
1. Los vértices de χ(∆n) se indexan por los pares (p, V) tales que V ⊆ [n], y p ∈ V .
2. Los simplejos n-dimensionales de χ(∆n) están formados por todos los conjuntos de vértices
{(0, V0), (1, V1), . . . , (n,Vn)}
que satisfacen las siguientes propiedades:
a) Para todo i, j ∈ [n], tenemos que Vi ⊆ Vj o Vj ⊆ Vi;
b) Para todo i, j ∈ [n], si i ∈ Vj, entonces Vi ⊆ Vj.
Esta subdivisión se llama cromática ya que el punto p de cada vértice (p, V) nos indica el “color” de
dicho vértice. Por ejemplo, consideremos el caso n = 1.
Ejemplo 13. Sea n = 1, por lo que [n] = [1] = {0, 1} y
∆1 = { ∅, {0}, {1}, {0, 1} }.
Entonces la subdivisión cromática χ(∆1) se construye como sigue:
• Los vértices se indexan por los pares (p, V) tales que V ⊆ [1], y p ∈ V . Así, sabemos que los
vértices son:
(0, {0}), (1, {1}), (0, {0, 1}) y (1, {0, 1}).
• Los simplejos 1-dimensionales de χ(∆1) están formados por todos los conjuntos de vértices
{ (0, V0), (1, V1) }
que satisfacen las propiedades 2a y 2b de la Definición 46, por lo cual sabemos que los 1-simplejos
son:
{ (0, {0}), (1, {0, 1}) }, { (0, {0, 1}), (1, {1}) } y { (0, {0, 1}), (1, {0, 1}) }.
En un dibujo, χ(∆1) se ve como se muestra en la Figura 3.1,
(0, {0}) (1, {0, 1}) (0, {0, 1}) (1, {1})
Figura 3.1: El complejo simplicial χ(∆1).
donde hemos asignado el color a cada vértice (p, V) de acuerdo al punto p ∈ V (los vértices corres-
pondientes a p = 0 se han dibujado en rosa y los correspondientes a p = 1, en amarillo).
33
Además, vale la pena detenernos a reflexionar sobre dos posibles interpretaciones que se le pueden dar
a una subdivisión cromática. En primer lugar, para el caso de la computación distribuida, los vértices
(p, V) indican la visión V que tiene cada proceso p al final de una ejecución. Por ejemplo, en la imagen
de abajo se representa que el proceso 0 sólo se puede “ver” a sí mismo, sin embargo, el proceso 1 “sabe”
que el proceso 0 terminó su trabajo o tarea antes o al mismo tiempo que él, porque “ve” tanto al 0 como a
él mismo. Por otro lado, la existencia de una arista entre el vértice (0, {0}) y el vértice (1, {0, 1}) (la arista
más a la izquierda) representa el caso en que el proceso 0 terminó primero su tarea y después el proceso
1 terminó su tarea. 2
(0, {0}) (1, {0, 1}) (0, {0, 1}) (1, {1})
Figura 3.2: Un mundo posible.
El caso de la arista que va del vértice (1, {1}) al vértice (0, {0, 1}) (la arista más a la derecha) es análogo,
basta cambiar 1 por 0 y viceversa − en este caso, el proceso que terminó su tarea primero fue el proceso
1 y después terminó su tarea el proceso 0− .
(0, {0}) (1, {0, 1}) (0, {0, 1}) (1, {1})
Figura 3.3: Otro mundo posible.
Finalmente, en el caso de la arista que va del vértice (1, {0, 1}) al vértice (0, {0, 1}) (la arista de en medio),
ambos procesos terminaron su tarea al mismo tiempo, o sea, de manera concurrente, por lo que cada uno
puede ver al otro: el proceso 0 puede ver al proceso 1 y también el proceso 1 puede ver al proceso 0.
Además, ambos procesos pueden verse a sí mismos.
2Cada vértice representa lo que ve un proceso al final de una ejecución, de esta manera, si un proceso termina antes que
todos los demás, sólo ve un conjunto de un elemento, porque sólo él ha llegado al final de la ejecución. Si un proceso llega
al final de una ejecución después de todos los demás, entonces ve el conjunto que tiene a todos los procesos, pues los demás
llegaron antes o al mismo tiempo que él y nadie falta por llegar. De acuerdo con esto, la notación conjuntista {0, 1} es adecuada
para los dos vértices centrales en la figura, pues representa su visión final, mas no el orden en que terminaron sus tareas.
34 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
(0, {0}) (1, {0, 1}) (0, {0, 1}) (1, {1})
Figura 3.4: Un mundo posible más.
En el caso de este ejemplo, cada arista representa un “mundo posible” en cuanto al orden en que los
procesos pudieron haber terminado su tarea en una ejecución. Más adelante describiremos cómo la sub-
división cromática de un 2-simplejo nos brinda información cuando se ejecutan tres procesos. En general,
la subdivisión cromática de un n-simplejo contiene información acerca del orden en el cual se pudieron
haber ejecutado n+ 1 procesos o, si se prefiere, de todos los “mundos posibles”.
Asimismo, se puede entender la subdivisión cromática del 1-simplejo en otro sentido. Pensemos que
nos encontramos a dos corredores cuadrúpedos muy hábiles: al primero lo llamaremos Rocinante y al
segundo, Spirit. Para poder identificarlos con nuestros vértices, a Rocinante le asignaremos el número 0
y a Spirit el número 1.
Rocinante y Spirit se alistan para salir a todo galope, pues les espera una carrera de unos cuantos metros
en la que cualquier cosa puede pasar. Sin embargo, para fines de este ejemplo, descartaremos que pasen
cosas como que uno de ellos esté muy cansado para salir, se desvíe del camino o haga otra cosa que
no sea competir. Para ser honestos, por “cualquier cosa” nos referimos a sólo tres posibles eventos: que
Rocinante llegue primero y gane, que Spirit gane o que haya un empate entre ambos caballos.
Cada uno de los tres desenlaces posibles de la carrera está representado por una arista del complejo
simplicial de la Figura 3.1. Si la lectora o lector piensa que a los vértices de Rocinante les corresponde
el color rosa y a los de Spirit el amarillo, será fácil que adivine cuál arista corresponde a cada situación.
Una pista: el empate es la arista de en medio.
De este modo, un simplejo n-dimensional de nuestro complejo simplicial χ(∆n) puede representar una
ejecución en la computación distribuida o un desenlace de una carrera de caballos.
Una vez que conocemos estas dos interpretaciones de la Definición 46, podemos entender el resultado del
siguiente teorema como el número total de visiones de todos los procesos o caballos: al ser |[n]| = n+ 1,
sabemos que hay n+ 1 procesos o caballos en total, además, cada uno de ellos tiene 2n visiones distintas
(que corresponden a la forma en la que ven que sus compañeros finalizaron o llegaron una vez que terminó
la ejecución o la carrera, según sea el caso). Al multiplicar las 2n visiones por el número de procesos o
caballos, obtenemos que hay 2n(n+ 1) vértices en total en χ(∆n).
Teorema 1. El complejo simplicial χ(∆n) consta de 2n(n+ 1) vértices en total.
Demostración. De acuerdo a la definición, para ver que los vértices de χ(∆n) son en total 2n(n + 1)
debemos demostrar que los pares de la forma (p, V) tales que V ⊆ [n] y p ∈ V son en total 2n(n + 1).
Esto equivale a demostrar que el conjunto
{(p, V) | p ∈ V y V ∈ P([n])}
tiene cardinalidad 2n(n+ 1).
35
Podemos notar que
{(p, V) | p ∈ V y V ∈ P([n])}
=
n+1⋃
k=0
{(p, V) | p ∈ V y V ∈ P([n]) y |V | = k} (3.1)
donde la última es una unión ajena.
Ahora, consideremos un k fijo para 0 ≤ k ≤ n + 1. El número de conjuntos de cardinalidad k en el
conjunto P([n]) es finito, digamosm, entonces podríamos a etiquetar a estos conjuntos como
V1, V2, . . . , Vm
donde |V1| = |V2| = · · · = |Vm| = k.
Así, podemos escribir
{(p, V) | p ∈ V y V ∈ P([n]) y |V | = k}
=
m⋃
i=1
{(p, Vi) | p ∈ Vi}
=
m⋃
i=1
(Vi × {Vi})
donde las dos últimas uniones también son ajenas, de manera que
| {(p, V) | p ∈ V y V ∈ P([n]) y |V | = k} |
=
m∑
i=1
| {(p, Vi) | p ∈ Vi} |
=
m∑
i=1
|Vi × {Vi}|
=
m∑
i=1
|Vi| · |{Vi}|
=
m∑
i=1
k · 1
= k
m∑
i=1
1
= k · m
Ahora, observemos que el número de conjuntos de cardinalidad k en el conjunto P([n]) está dado por(
n+1
k
)
, ya que las cardinalidades k de los subconjuntos V ⊆ [n] pueden tomar valores desde 0 hasta n+1.
36 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Entonces en realidad tenemosm =
(
n+1
k
)
y por lo anterior
| {(p, V) | p ∈ V y V ∈ P([n]) y |V | = k} | = k
(
n+ 1
k
)
. (3.2)
Como (3.2) es cierta para cada k con 0 ≤ k ≤ n+ 1, de la igualdad (3.1) se sigue que
|{(p, V) | p ∈ V y V ∈ P([n])}|
=
n+1∑
k=0
| {(p, V) | p ∈ V y V ∈ P([n]) y |V | = k} |
=
n+1∑
k=0
k
(
n+ 1
k
)
Por último, observemos que
n+1∑
k=0
k
(
n+ 1
k
)
= 2
n(n+ 1)
de acuerdo a lo siguiente
n+1∑
k=0
k
(
n+ 1
k
)
=
0∑
k=0
k
(
n+ 1
k
)
+
n+1∑
k=1
k
(
n+ 1
k
)
=
n+1∑
k=1
k
(
n+ 1
k
)
=
n+1∑
k=1
k
n+ 1
(n+ 1)
(
n+ 1
k
)
= (n+ 1)
n+1∑
k=1
k
n+ 1
(
n+ 1
k
)
= (n+ 1)
n+1∑
k=1
(
n
k− 1
)
= (n+ 1)
n∑
k=0
(
n
k+ 1− 1
)
= (n+ 1)
n∑
k=0
(
n
k
)
= (n+ 1) 2n
= 2
n(n+ 1).
37
Por lo tanto
| {(p, V) | p ∈ V y V ∈ P([n])} | = 2
n(n+ 1),
es decir, los vértices de χ(∆n) son en total 2n(n+ 1).

En seguida, incluimos una segunda prueba del mismo hecho, que resulta ser más breve y sencilla. 3
Demostración. Tomamos un vértice p0 en el conjunto V . Notemos que esto lo podemos hacer de n + 1
formas distintas.
A continuación, consideremos el conjuntoW definido comoW := V \ {p0}.
Observemos que
| {(p0,W) | W ∈ P([n] \ {p0})} |
= | P([n] \ {p0}) |
= | P([n− 1]) |
= 2
n,
ya que p0 no está en el conjuntoW.
Luego, tomemos en cuenta que para cadaW distinto en P([n] \ {p0}) se puede construir la unión con p0,
es decir, W ∪ {p0}, de manera que se obtenga un subconjunto V = W ∪ {p0} de [n] y así también un
elemento de la forma (p0, V).
Finalmente, si consideramos que hay n + 1 maneras distintas de elegir p0, podemos concluir que la
cardinalidad del conjunto
{(p, V) | p ∈ V y V ∈ P([n])}
es 2n(n+ 1).

Los simplejos n-dimensionales de χ(∆n) se pueden escribir de una manera alternativa que arroja más
luz sobre los posibles órdenes en que n+ 1 procesos que trabajan al mismo tiempo (o n+ 1 caballos que
corren en una carrera) pueden terminar sus ejecuciones (o pueden finalizar la carrera). Para indagar en
ello con mayor detalle damos las siguientes definiciones:
Definición 47. Consideremos el complejo χ(∆n).
3La idea central de esta prueba fue sugerida por el Dr. José Ángel Frías García.
38 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
• Sn es el conjunto de todos los conjuntos de (n+ 1)-vértices de la forma
{(0, V0), . . . , (n,Vn)}
que satisfacen las condiciones 2a y 2b de la Definición 46.
• Pn es el conjunto de todas las particiones ordenadas de [n], es decir,
Pn : =
{
E = (R1, . . . , Rt)
∣∣∣∣∣ para todo i, Ri 6= ∅; para i 6= j, Ri ∩ Rj = ∅ y
t⋃
i=1
Ri = [n]
}
.
Cada partición (R1, . . . , Rt) se puede denotar también como R1| · · · |Rt.
De acuerdo a como lo acabamos de definir, el conjunto Sn incluye a todos los simplejos de dimensión
máxima en el complejo simplicial χ(∆n). Por otro lado, cada elemento E ∈ Pn representa una forma
en que n + 1 procesos pueden terminar sus ejecuciones o un desenlace posible de una carrera en la que
participan n + 1 caballos. Más adelante, en la Proposición 6, mostraremos que hay una correspondencia
biunívoca entre los (n + 1)-simplejos y los elementos E de Pn. Pero antes, estudiemos un ejemplo que
nos ayude a visualizar la Definición 47.
Ejemplo 14. Sea n = 2. El conjunto S2 es el siguiente:
S2 ={{(0, {0}), (1, {0, 1}), (2, {0, 1, 2})},
{(0, {0}), (1, {0, 1, 2}), (2, {0, 2})},
{(0, {0, 1}), (1, {1}), (2, {0, 1, 2})},
{(0, {0, 1, 2}), (1, {1}), (2, {1, 2})},
{(0, {0, 2}), (1, {0, 1, 2}), (2, {2})},
{(0, {0, 1, 2}), (1, {1, 2}), (2, {2})},
{(0, {0, 1, 2}), (1, {1, 2}), (2, {1, 2})},
{(0, {0, 2}), (1, {0, 1, 2}), (2, {0, 2})},
{(0, {0, 1}), (1, {0, 1}), (2, {0, 1, 2})},
{(0, {0}), (1, {0, 1, 2}), (2, {0, 1, 2})},
{(0, {0, 1, 2}), (1, {1}), (2, {0, 1, 2})},
{(0, {0, 1, 2}), (1, {0, 1, 2}), (2, {2})},
{(0, {0, 1, 2}), (1, {0, 1, 2}), (2, {0, 1, 2})}}
Por otro lado, el conjunto P2 es:
39
P2 ={(R0 = {0}, R1 = {1}, R2 = {2}),
(R0 = {0}, R1 = {2}, R2 = {1}),
(R0 = {1}, R1 = {0}, R2 = {2}),
(R0 = {1}, R1 = {2}, R2 = {0}),
(R0 = {2}, R1 = {0}, R2 = {1}),
(R0 = {2}, R1 = {1}, R2 = {0}),
(R0 = {1, 2}, R1 = {0}),
(R0 = {0, 2}, R1 = {1}),
(R0 = {0, 1}, R1 = {2}),
(R0 = {0}, R1 = {1, 2}),
(R0 = {1}, R1 = {0, 2}),
(R0 = {2}, R1 = {0, 1}),
(R0 = {0, 1, 2})}
Obsérvese que P2 también se puede escribir como:
P2 = {0|1|2,0|2|1, 1|0|2, 1|2|0, 2|0|1, 2|1|0, 12|0,02|1,01|2,0|12, 1|02, 2|01,012}.
Una de las grandes ventajas de este ejemplo es que ¡se puede dibujar! y en el dibujo podemos identificar
cada uno de los 2-simplejos y, por ende, cada una de las particiones. ¡Procedamos a examinarlos!
(1, {0, 1})(0, {0})
(2, {0, 1, 2})
El 2-simplejo de la figura de la izquierda es el
{(0, {0}), (1, {0, 1}), (2, {0, 1, 2})}
y le corresponde la partición 0 | 1 | 2.
Si pensamos en 3 procesos que se están ejecutando
al mismo tiempo, este simplejo representa la situa-
ción en la que los procesos dan pasos de manera se-
cuencial, es decir, uno tras otro: primero el proceso
0, luego el 1 y finalmente el 2.
Por otra parte, en el caso de que tengamos tres ca-
ballos (digamos Rocinante con el número 0, Spirit
con el número 1 y Marengo con el número 2), este
simplejo nos indica que Rocinante ganó la carrera,
Spirit quedó en segundo lugar y Marengo terminó en
tercer lugar.
40 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
El 2-simplejo de la figura de la derecha es el
{(0, {0, 1}), (1, {1}), (2, {0, 1, 2})}
y le corresponde la partición 1 |0 | 2.
Si pensamos en 3 procesos que se están ejecutando
al mismo tiempo, este simplejo representa la situa-
ción en la que los procesos dan pasos de manera
secuencial, uno tras otro, pero ahora el primero en
dar un paso es el proceso 1, luego el 0 y finalmente
el 2.
Por otra parte, en el caso de que tengamos tres ca-
ballos (enumerados como antes), este simplejo nos
indica que Spirit quedó en primer lugar, en segundo
lugar quedó Rocinante y Marengo terminó en tercer
lugar nuevamente.
(0, {0, 1}) (1, {1})
(2, {0, 1, 2})
(2, {0, 2})
(0, {0, 2})
(1, {0, 1, 2})
El 2-simplejo de la figura de la izquierda es el
{(0, {0, 2}), (1, {0, 1, 2}), (2, {0, 2})}
y le corresponde la partición 0 2 | 1.
Para 3 procesos que se están ejecutando al mismo
tiempo, este simplejo representa el caso en que los
procesos 0 y 2 dan un paso al mismo tiempo, y antes
que el proceso 1.
Por otra parte, en el caso de que tengamos tres ca-
ballos (enumerados como antes), este simplejo nos
indica que Rocinante y Marengo empataron en pri-
mer lugar y finalmente llegó Spirit en segundo lugar.
El 2-simplejo de la figura de la derecha es el
{(0, {0, 1, 2}), (1, {0, 1, 2}), (2, {2})}
y le corresponde la partición 2 |0 1.
Si pensamos en 3 procesos que se están ejecutando
al mismo tiempo, este simplejo representa la situa-
ción en la que el proceso 2 fue el primero en dar
un paso, para que posteriormente los procesos 0 y 1
dieran un paso al mismo tiempo.
Por otra parte, en el caso de que tengamos tres ca-
ballos (enumerados como antes), este simplejo nos
indica que Marengo ganó la carrera y luego llega-
ron Rocinante y Spirit, quienes quedaron empatados
en segundo lugar.
(2, {2})
(1, {0, 1, 2}) (0, {0, 1, 2})
41
(1, {0, 1, 2}) (0, {0, 1, 2})
(2, {0, 1, 2})
El 2-simplejo de la figura de la izquierda es el
{(0, {0, 1, 2}), (1, {0, 1, 2}), (2, {0, 1, 2})}
y le corresponde la partición 0 1 2.
Si pensamos en 3 procesos que se están ejecutando
al mismo tiempo, este simplejo representa la situa-
ción en la que los procesos dan un paso de manera
completamente concurrente, es decir, los tres al mis-
mo tiempo. En este caso, tanto 0 como 1 y 2 acaba-
ron su ejecución al mismo tiempo.
Por otra parte, en el caso de que tengamos tres ca-
ballos (enumerados como antes) este simplejo nos
indica que Rocinante, Spirit y Marengo llegaron al
mismo tiempo a la meta, o sea, que los tres empa-
taron (y probablemente se necesitarán tres medallas
de oro, una para cada caballo).
Por último, nos gustaría hacer notar a la lectora o lector que los simplejos restantes del conjunto S2, así
como el resto de las particiones de P2, son muy similares a alguno o algunos de los cinco simplejos que
analizamos arriba, con sus correspondientes particiones.
Ahora demostraremos el siguiente lema, que nos será de gran ayuda en la prueba de la Proposición 6.
Lema. Consideremos el complejo χ(∆n) y sea σ un simplejo de dimensión n de χ(∆n). Para σ existe
una permutación π : [n] → [n] tal que Vπ(0) ⊆ Vπ(1) ⊆ · · · ⊆ Vπ(n) = [n].
Demostración. Sea σ = {(0, V0), . . . , (n,Vn)}. Recordemos que al ser σ un simplejo de dimensión n de
χ(∆n), cumple las propiedades 2a y 2b de la Definición 46.
Al considerar el conjunto A = {|Vj| | j ∈ [n]} observamos que n + 1 ≥ |A| ≥ 1, pues |A| = 1 en el
caso de que todos los Vj con j ∈ [n] tengan la misma cardinalidad y |A| = n+ 1 en el caso de que todos
tengan distinta cardinalidad.
Si |A| = 1 entonces se cumple que |V0| = · · · = |Vn| y en este caso cualquier permutación π : [n] → [n]
nos sirve, por ejemplo la permutación trivial π(a) = a.
En el caso |A| > 1 podemos proceder de la siguiente manera:
(I) Definimos k como el natural tal que k = mín{|Vj| | j ∈ [n]}, entonces al menos hay un i ∈ [n] tal
que |Vi| = k.
Observemos que para todo j ∈ [n] tal que |Vj| = k se cumple, por la propiedad 2a, que Vi ⊆ Vj
o Vi ⊆ Vj, lo cual implica que Vi = Vj ya que en este caso ambos conjuntos tienen la misma
cardinalidad.
(II) Ahora, mostramos que para todo j ∈ [n] tal que |Vj| > k se cumple que Vi ⊆ Vj.
Para llegar a una contradicción, supongamos que Vi * Vj, entonces por la propiedad 2a tiene que
ocurrir Vj ⊆ Vi, pero en este caso se tendría que |Vj| ≤ |Vi| = k, lo cual contradice la hipótesis de
que |Vj| > k.
42 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Por lo tanto, para todo j ∈ [n] tal que |Vj| > k se cumple que Vi ⊆ Vj.
(III) Así, concluimos que para todo j ∈ [n] tal que |Vj| ≥ k se tiene que Vi ⊆ Vj. Más aún, si |Vj| = k
entonces Vi = Vj.
Ahora, al seguir un procedimiento análogo para k ′ = mín{|Vj| | j ∈ [n] y |Vj| > k}. Tenemos que al
menos hay un i ′ ∈ [n] tal que |Vi ′ | = k ′. Observamos que para todo j ∈ [n] tal que |Vj| ≥ k ′ se tiene
que Vi ′ ⊆ Vj. Más aún, si |Vj| = k ′ entonces Vi ′ = Vj.
En el siguiente paso, definimos k ′′ = mín{|Vj| | j ∈ [n] y |Vj| > k ′}. Tenemos que al menos hay un
i ′′ ∈ [n] tal que |Vi ′′ | = k ′′. Observamos que para todo j ∈ [n] tal que |Vj| ≥ k ′′ se tiene que Vi ′′ ⊆ Vj.
Más aún, si |Vj| = k ′′ entonces Vi ′′ = Vj.
Así podemos seguir sucesivamente hasta que k(t) = mín{|Vj| | j ∈ [n] y |Vj| > k
(t−1)} = |[n]|.
De esta manera, podemos enumerar los conjuntos Vj para j ∈ [n] como
Vπ(0) = · · · = Vπ(i1) ( Vπ(i1+1) = · · · = Vπ(i2) ( · · · = Vπ(it−1) ( Vπ(it−1+1) = · · · = Vπ(n) (3.3)
donde
|Vπ(0)| = · · · = |Vπ(i1)| = k
|Vπ(i1+1)| = · · · = |Vπ(i2)| = k
′
|Vπ(i2+1)| = · · · = |Vπ(i3)| = k
′′
...
|Vπ(it−2+1)| = · · · = |Vπ(it−1)| = k
(t−2)
|Vπ(it−1+1)| = · · · = |Vπ(n)| = k
(t−1) = |[n]|.
Por lo tanto, la permutación π : [n] → [n] definida en 3.3 cumple las condiciones requeridas en el enun-
ciado del lema.

Proposición 6. Los simplejos n-dimensionales de χ(∆n) se pueden indexar por particiones ordenadas
de [n], es decir, existe una correspondencia biunívoca entre los conjuntos Sn y Pn.
Demostración. En primer lugar, demostramos que a cada simplejo σ ∈ Sn le corresponde una partición
ordenada E ∈ Pn, es decir, construimos una función ψ : Sn → Pn.
Sea σ = {(0, V0), . . . , (n,Vn)} ∈ Sn. Por el lema, sabemos que existe una permutación π : [n] → [n] tal
que Vπ(0) ⊆ Vπ(1) ⊆ · · · ⊆ Vπ(n) = [n]. Más específicamente, π determina un único conjunto de índices
{i1, i2, . . . , it−1}, con 1 ≤ t ≤ n+ 1 de manera que se cumple 0 ≤ i1 < i2 < · · · < it−1 < n y además
Vπ(0) = Vπ(1) = · · · = Vπ(i1) ( Vπ(i1+1) = Vπ(i1+2) = · · · = Vπ(i2) ( · · · = Vπ(it−1) ( Vπ(it−1+1) = · · · = Vπ(n)
43
(ver ejemplo 15), entonces podemos definir los conjuntos de la partición R1, . . . , Rt como sigue:
R1 : = {π(0), . . . , π(i1)}
R2 : = {π(i1 + 1), . . . , π(i2)}
...
Rt−1 : = {π(it−2 + 1), . . . , π(it−1)}
Rt : = {π(it−1 + 1), . . . , π(n)}
Así, establecemos la correspondencia ψ(σ) := (R1, . . . , Rt).
En segundo lugar, encontramos una función ϕ = ψ−1 : Pn → Sn.
Sea E = (R1, . . . , Rt) ∈ Pn. Observemos que, por ser E partición de [n], cada i ∈ [n] está exactamente
en un Rj para 1 ≤ j ≤ t. Entonces, definimos los vértices de un elemento de Sn como
(i, Vi) con Vi :=
j⋃
k=1
Rk
donde j es el índice que cumple la pertenencia i ∈ Rj.
De esta manera hemos construido un conjunto de n+ 1 vértices σ ∈ Sn tal que
σ = {(0, V0), . . . , (n,Vn)}.
Definimos ϕ como la función que lleva la partición E al conjunto σ construido de esta manera, es decir,
ϕ(E) = σ.
Ahora sólo nos resta demostrar que ψ ◦ϕ es la identidad en Pn y que ϕ ◦ψ es la identidad en Sn.
Para mostrar que ψ ◦ ϕ es la identidad en Pn, consideremos una partición E = (R1, . . . , Rt) donde
escribimos cada Rj, con 1 ≤ j ≤ t, como sigue
R1 := {a1
1
, . . . , a1
r1
}
R2 := {a2
1
, . . . , a2
r2
}
...
Rt−1 := {at−1
1
, . . . , at−1
rt−1
}
Rt := {at
1
, . . . , atrt}.
Por la construcción de ϕ dada más arriba, sabemos que ϕ(E) = σ donde σ = {(0, V0), . . . , (n,Vn)} y
para cada i ∈ [n], Vi :=
⋃j
k=1
Rk donde j es tal que i ∈ Rj.
Observemos que {a1
1
, . . . , a1
r1
, a2
1
, . . . , a2
r2
, . . . , at−1
1
, . . . , at−1
rt−1
, at
1
, . . . , atrt} = [n], lo que nos permite to-
mar la permutación π : [n] → [n] que manda cada i ∈ [n] al correspondiente elemento en
⋃t
j=1
Rj, es
decir,
44 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
para los primeros r1 elementos de [n] definimos π como
π(0) = a1
1
...
π(r1 − 1) = a1
r1
,
para los siguientes r2 elementos de [n] definimos π como
π(r1) = a
2
1
...
π(r1 + r2 − 1) = a2
r2
,
y así sucesivamente,
para los penúltimos rt−1 elementos de [n] definimos π como
π(r1 + r2 + · · · + rt−2) = a
t−1
1
...
π(r1 + · · · + rt−1 − 1) = at−1
rt−1
y para los últimos rt elementos de [n] definimos π como
π(r1 + · · · + rt−1) = a
t
1
...
π(r1 + · · · + rt − 1) = atrt.
Así definida, la permutación π de [n] permite que se cumpla:
Vπ(0) = Vπ(1) = · · · = Vπ(r1−1) ( Vπ(r1) = · · · = Vπ(r1+r2−1)
( · · ·
( Vπ(r1+r2+···+rt−2) = · · · = Vπ(r1+···+rt−1−1)
( Vπ(r1+···+rt−1) = · · · = Vπ(r1+···+rt−1).
Nótese que r1 + · · · + rt − 1 = n.
Ahora, definimos i1 := r1 − 1, i2 := r1 + r2 − 1, . . . , it−1 := r1 + · · · + rt−1 − 1.
Por lo tanto, llegamos a la conclusión deseada: ψ(ϕ(E)) = E.
Para mostrar que ϕ ◦ψ es la identidad en Sn consideremos σ = {(0, V0), . . . , (n,Vn)} en Sn.
Sea E = (R1, . . . , Rt) la partición tal que ψ(σ) = E.
45
Entonces hay índices únicos i1, . . . , it−1 y π : [n] → [n] una permutación tales que
Vπ(0) = Vπ(1) = · · · = Vπ(i1) ( Vπ(i1+1) = Vπ(i1+2) = · · · = Vπ(i2) ( · · · = Vπ(it−1) ( Vπ(it−1+1) = · · · = Vπ(n)
y que cumplen también
R1 : = {π(0), . . . , π(i1)}
R2 : = {π(i1 + 1), . . . , π(i2)}
...
Rt−1 : = {π(it−2 + 1), . . . , π(it−1)}
Rt : = {π(it−1 + 1), . . . , π(n)}.
Ahora, sea ϕ(E) = {(0,W0), . . . , (n,Wn)} el simplejo de dimensión n que es imagen de E bajo ϕ.
Entonces, basta demostrar que Vi =Wi para todo i ∈ [n] para llegar a la conclusión que queremos.
Para esto, nos valdremos de la siguiente afirmación:
Afirmación. Wj = {i | Vi ⊆ Vj} para todo j ∈ [n].
Demostración. (de la Afirmación.) Sea j ∈ [n]. Haremos la prueba por doble contención, pero antes
recordemos queWj está definido comoWj = R1 ∪ · · · ∪ Rq, donde q es el único índice tal que j ∈ Rq.
P.D.Wj ⊆ {i | Vi ⊆ Vj}.
Sea k ∈ Wj. Esta pertenencia implica que k ∈ Rm para algúnm tal que 1 ≤ m ≤ q.
Sabemos que k, j ∈ [n], entonces deben existir x, y ∈ [n] tales que π(x) = k y π(y) = j. Obsérvese que
π(x) = k ∈ Rm y π(y) = j ∈ Rq.
Analicemos los siguientes dos casos:
• Caso 1:m < q.
En este caso Rm 6= Rq y como π(x) = k ∈ Rm, π(y) = j ∈ Rq y m < q se debe cumplir que
Vπ(x) ( Vπ(y), es decir, Vk ( Vj.
• Caso 2:m = q.
En este caso Rm = Rq , entonces π(x), π(y) ∈ Rq, de manera que Vπ(x) = Vπ(y), es decir, Vk = Vj.
Observemos que en ambos casos se cumple Vk ⊆ Vj, entonces k ∈ {i | Vi ⊆ Vj}.
Por lo tantoWj ⊆ {i | Vi ⊆ Vj}.
P.D. {i | Vi ⊆ Vj} ⊆ Wj.
46 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Sea k ∈ {i | Vi ⊆ Vj}, entonces Vk ⊆ Vj.
Ahora, como π : [n] → [n] es una permutación tal que
Vπ(0) = Vπ(1) = · · · = Vπ(i1) ( Vπ(i1+1) = Vπ(i1+2) = · · · = Vπ(i2) ( · · · = Vπ(it−1) ( Vπ(it−1+1) = · · · = Vπ(n)
entonces hay x, y ∈ [n] tales que Vπ(x) ⊆ Vπ(y), donde π(x) = k y π(y) = j.
Por construcción de la partición, π(x) ∈ Rm para algún m, y tal m debe cumplir 1 ≤ m ≤ q porque
Vπ(x) ⊆ Vπ(y). Más aún, π(x) = k, entonces k ∈ Rm para algún 1 ≤ m ≤ q.
Como Rm ⊆ R1 ∪ · · · ∪ Rm ∪ · · · ∪ Rq =Wj, se tiene que k ∈ Wj.
Por lo tanto {i | Vi ⊆ Vj} ⊆ Wj.
Al haber demostrado ambas contenciones, concluimos queWj = {i | Vi ⊆ Vj} para todo j ∈ [n].
Fin de la demostración de la afirmación.

Ahora mostraremos que Vj = {i | Vi ⊆ Vj} para todo j ∈ [n]. Posteriormente, al hacer uso de la
afirmación anterior, llegaremos a la conclusión deseada.
Sea j ∈ [n]. Procedemos nuevamente por doble contención.
P.D. {i | Vi ⊆ Vj} ⊆ Vj.
Sea i ∈ {i | Vi ⊆ Vj}, entonces Vi ⊆ Vj. Por la parte 1 de la Definición 46, sabemos que i ∈ Vi y al
cumplirse Vi ⊆ Vj podemos concluir que i ∈ Vj. Así, tenemos la contención deseada.
P.D. Vj ⊆ {i | Vi ⊆ Vj}.
Sea i ∈ Vj. Por la Definición 46, propiedad 2b, tenemos que esto implica Vi ⊆ Vj. Por lo tanto i ∈
{i | Vi ⊆ Vj} y se cumple la contención que se quería mostrar.
Finalmente, como Vj = {i | Vi ⊆ Vj} y por nuestra afirmación anterior {i | Vi ⊆ Vj} = Wj, podemos
concluir que Vi =Wi para todo i ∈ [n].
Por lo tanto ϕ(ψ(σ)) = σ.
En conclusión, las funciones ψ y ϕ definen, en efecto, una correspondecia biunívoca entre los conjuntos
Sn y Pn.

Ejemplo 15. Consideremos n = 7. Sea
σ = {(0, {0, 1, 2, 3}), (1, {0, 1, 2, 3}),
(2, {2, 3}), (3, {2, 3}),
(4, {0, 1, 2, 3,4, 7}), (5, {0, 1, 2, 3,4, 5, 6, 7}),
(6, {0, 1, 2, 3,4, 5, 6, 7}), (7, {0, 1, 2, 3,4, 7})}
47
un elemento de S7.
Notemos que, en este caso,
V0 = {0, 1, 2, 3} = V1
V2 = {2, 3} = V3
V4 = {0, 1, 2, 3,4, 7} = V7
V5 = {0, 1, 2, 3,4, 5, 6, 7} = V6.
Dos permutaciones π, α : [7] → [7] que cumplen Vπ(0) ⊆ Vπ(1) ⊆ · · · ⊆ Vπ(7) = [7] y
Vα(0) ⊆ Vα(1) ⊆ · · · ⊆ Vα(7) = [7], son las siguientes:
π(0) = 3
π(1) = 2
π(2) = 0
π(3) = 1
π(4) = 4
π(5) = 7
π(6) = 6
π(7) = 5
α(0) = 2
α(1) = 3
α(2) = 0
α(3) = 1
α(4) = 7
α(5) = 4
α(6) = 5
α(7) = 6
puesto que
Vπ(0) = V3 = {2, 3}
Vπ(1) = V2 = {2, 3}
Vπ(2) = V0 = {0, 1, 2, 3}
Vπ(3) = V1 = {0, 1, 2, 3}
Vπ(4) = V4 = {0, 1, 2, 3,4, 7}
Vπ(5) = V7 = {0, 1, 2, 3,4, 7}
Vπ(6) = V6 = {0, 1, 2, 3,4, 5, 6, 7}
Vπ(7) = V5 = {0, 1, 2, 3,4, 5, 6, 7}
Vα(0) = V2 = {2, 3}
Vα(1) = V3 = {2, 3}
Vα(2) = V0 = {0, 1, 2, 3}
Vα(3) = V1 = {0, 1, 2, 3}
Vα(4) = V7 = {0, 1, 2, 3,4, 7}
Vα(5) = V4 = {0, 1, 2, 3,4, 7}
Vα(6) = V5 = {0, 1, 2, 3,4, 5, 6, 7}
Vα(7) = V6 = {0, 1, 2, 3,4, 5, 6, 7}
Si somos un poco más precisos, podemos observar que se tienen las contenciones
Vπ(0) ⊆ Vπ(1) ( Vπ(2) ⊆ Vπ(3) ( Vπ(4) ⊆ Vπ(5) ( Vπ(6) ⊆ Vπ(7) y
Vα(0) ⊆ Vα(1) ( Vα(2) ⊆ Vα(3) ( Vα(4) ⊆ Vα(5) ( Vα(6) ⊆ Vα(7).
Así, tenemos que i1 = 1, i2 = 3 e i3 = 5 donde 0 ≤ 1 < 3 < 5 < 7 y además
Vπ(0) ⊆ Vπ(i1) ( Vπ(i1+1) ⊆ Vπ(i2) ( Vπ(i2+1) ⊆ Vπ(i3) ( Vπ(i3+1) ⊆ Vπ(7)
48 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
o bien
Vα(0) ⊆ Vα(i1) ( Vα(i1+1) ⊆ Vα(i2) ( Vα(i2+1) ⊆ Vα(i3) ( Vα(i3+1) ⊆ Vα(7).
Entonces, como en la prueba de la Proposición 6, podemos definir
R1 := {π(0), π(i1)}
R2 := {π(i1 + 1), π(i2)}
R3 := {π(i2 + 1), π(i3)}
R4 := {π(i3 + 1), π(7)},
o, lo que es lo mismo,
R1 := {α(0), α(i1)}
R2 := {α(i1 + 1), α(i2)}
R3 := {α(i2 + 1), α(i3)}
R4 := {α(i3 + 1), α(7)}.
De esta manera
R1 := {3, 2} R2 := {0, 1} R3 := {4, 7} R4 := {6, 5},
por lo que la partición E tal que ψ(σ) = E es E = 32|01|47|65 o bien E = 23|01|74|56, que
también se puede escribir como E = 23|01|47|56.
A la inversa, si tenemos la partición E = 23|01|47|56 en P7 entonces
R1 = {2, 3} R2 = {0, 1} R3 = {4, 7} R4 = {5, 6}.
De acuerdo a la demostración de la Proposición 6, los conjuntos Vi para i ∈ [7] se construyen de la
siguiente manera:
0 ∈ R2 implica que V0 = R1 ∪ R2 = {2, 3} ∪ {0, 1} = {0, 1, 2, 3},
1 ∈ R2 implica que V1 = R1 ∪ R2 = {2, 3} ∪ {0, 1} = {0, 1, 2, 3},
2 ∈ R1 implica que V2 = R1 = {2, 3},
3 ∈ R1 implica que V3 = R1 = {2, 3},
4 ∈ R3 implica que V4 = R1 ∪ R2 ∪ R3 = {2, 3} ∪ {0, 1} ∪ {4, 7} = {0, 1, 2, 3,4, 7},
5 ∈ R4 implica que V5 = R1 ∪ R2 ∪ R3 ∪ R4 = {2, 3} ∪ {0, 1} ∪ {4, 7} ∪ {5, 6} = [7],
6 ∈ R4 implica que V6 = R1 ∪ R2 ∪ R3 ∪ R4 = {2, 3} ∪ {0, 1} ∪ {4, 7} ∪ {5, 6} = [7],
7 ∈ R3 implica que V7 = R1 ∪ R2 ∪ R3 = {2, 3} ∪ {0, 1} ∪ {4, 7} = {0, 1, 2, 3,4, 7}.
49
Así, el simplejo σ tal que ϕ(E) = σ es
σ = {(0, {0, 1, 2, 3}), (1, {0, 1, 2, 3}),
(2, {2, 3}), (3, {2, 3}),
(4, {0, 1, 2, 3,4, 7}), (5, {0, 1, 2, 3,4, 5, 6, 7}),
(6, {0, 1, 2, 3,4, 5, 6, 7}), (7, {0, 1, 2, 3,4, 7})}.
La igualdad ψ(ϕ(E)) = E en este ejemplo se ve de la siguiente manera:
Sea E = 23|01|47|56 como antes, donde t = 4 y sabemos que
R1 = {2, 3} R2 = {0, 1} R3 = {4, 7} R4 = {5, 6}.
Definimos
a1
1
= 2, a1
2
= a1
r1
= 3
a2
1
= 0, a2
2
= a2
r2
= 1
a3
1
= 4, a3
2
= a3
r3
= 7
a4
1
= 5, a4
2
= a4
r4
= 6.
Además, sabemos que el simplejo ϕ(E) = σ es
σ = {(0, V0), (1, V1), (2, V2), (3, V3), (4, V4), (5, V5), (6, V6), (7, V7)}
donde, para cada i, Vi =
⋃j
k=1
Rk con j el único índice tal que i ∈ Rj.
Podemos observar que
{a1
1
, a1
r1
, a2
1
, a2
r2
, a3
1
, a3
r3
, a4
1
, a4
r4
} = [7].
Definimos la permutación π : [7] → [7] como
π(0) = a1
1
= 2
π(r1 − 1) = π(2− 1) = π(1) = a1
2
= 3
π(r1) = π(2) = a
2
1
= 0
π(r1 + r2 − 1) = π(2+ 2− 1) = π(3) = a2
2
= 1
π(r1 + rt−2) = π(r1 + r2) = π(2+ 2) = π(4) = at−1
1
= a4−1
1
= a3
1
= 4
π(r1 + r2 + rt−1 − 1) = π(r1 + r2 + r3 − 1) = π(2+ 2+ 2− 1) = π(5) = at−1
rt−1
= a3
r3
= a3
2
= 7
π(r1 + r2 + rt−1) = π(r1 + r2 + r3) = π(2+ 2+ 2) = π(6) = at
1
= a4
1
= 5
π(r1 + r2 + r3 + rt − 1) = π(r1 + r2 + r3 + r4 − 1) = π(2+ 2+ 2+ 2− 1) = π(7) = atrt = a
4
r4
= a4
2
= 6.
50 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Dicha permutación permite que se cumpla
Vπ(0) = Vπ(1) ( Vπ(2) = Vπ(3) ( Vπ(4) = Vπ(5) ( Vπ(6) = Vπ(7),
es decir,
V2 = V3 ( V0 = V1 ( V4 = V7 ( V5 = V6.
Ahora simplemente definimos
i1 := r1 − 1 = 2− 1 = 1
i2 := r1 + r2 − 1 = 2+ 2− 1 = 3
i3 := r1 + r2 + r3 − 1 = 2+ 2+ 2− 1 = 5,
entonces
R1 = {π(0), π(i1)} = {π(0), π(1)} = {2, 3}
R2 = {π(i1 + 1), π(i2)} = {π(2), π(3)} = {0, 1}
R3 = {π(i2 + 1), π(i3)} = {π(4), π(5)} = {4, 7}
R4 = {π(i3 + 1), π(7)} = {π(6), π(7)} = {5, 6}.
Por lo tanto ψ(ϕ(E)) = R1|R2|R3|R4 = 23|01|47|56 = E.
Por otro lado, la igualdad ϕ(ψ(σ)) = σ en este ejemplo se explica como sigue:
Consideremos
σ = {(0, {0, 1, 2, 3}), (1, {0, 1, 2, 3}),
(2, {2, 3}), (3, {2, 3}),
(4, {0, 1, 2, 3,4, 7}), (5, {0, 1, 2, 3,4, 5, 6, 7}),
(6, {0, 1, 2, 3,4, 5, 6, 7}), (7, {0, 1, 2, 3,4, 7})}.
y observemos que, como se dijo antes, E = 23|01|47|56 es la partición tal que ψ(σ) = E. Nótese que, en
este caso, t = 4.
Sabemos que hay índices únicos i1, i2 e i3 y una permutación α : [7] → [7] tales que
Vα(0) = · · · = Vα(i1) ( Vα(i1+1) = · · · = Vα(i2) ( Vα(i2+1) = · · · = Vα(i3) ( Vα(i3+1) = · · · = Vα(7)
51
y que cumplen también
R1 = {α(0), . . . , α(i1)}
R2 = {α(i1 + 1), . . . , α(i2)}
R3 = {α(i2 + 1), . . . , α(i3)}
R4 = {α(i3 + 1), . . . , α(7)}.
Ahora, sea ϕ(E) = {(0,W0), . . . , (7,W7)} el simplejo de dimensión 7 que es imagen de E bajo ϕ. Basta
demostrar que Vi = Wi para todo i ∈ [7], como en la prueba de la Proposición 6, para poder concluir
que ϕ(ψ(σ)) = σ.
La igualdad Wj = {i |Vi ⊆ Vj} para j ∈ [7] ya se demostró en el caso general, sin embargo, escribimos
aquí algunos casos particulares para j y k sólo con fines ilustrativos.
Recordemos queWj está definido comoWj = R1 ∪ · · · ∪ Rq donde q es el único índice tal que j ∈ Rq.
• Wj ⊆ {i |Vi ⊆ Vj}
Si sucediera, en términos de el presente ejemplo, queWj = R1∪ R2∪ R3, entonces pasó que j ∈ R3,
de acuerdo a la definición de Wj. También, sabemos que k ∈ Wj tiene que ser un elemento del
conjunto R1 ∪ R2 ∪ R3, donde habíamos dicho que
R1 = {α(0), . . . , α(i1)}
R2 = {α(i1 + 1), . . . , α(i2)}
R3 = {α(i2 + 1), . . . , α(i3)}.
Cualquier elemento de estos conjuntos es la imagen de algún elemento en [7] bajo α, más especí-
ficamente, la imagen de algún elemento del conjunto {0, . . . , i1, i1 + 1, . . . , i2, i2 + 1, . . . , i3}.
Como j ∈ R3, el elemento y tal que α(y) = j está en el conjunto {i2 + 1, . . . , i3}.
Para k se tienen dos casos:
• Si m < q entonces el elemento x tal que α(x) = k está en el conjunto {0, . . . , i2}. En este
caso Vα(x) = Vk ( Vj. En nuestro ejemplo, sólo por ilustrar este caso, dos elementos que
cumplirían esta relación serían j = 4 y k = 0, pero hay muchos otros.
• Sim = q entonces el elemento x tal que α(x) = k también está en el conjunto {i2+1, . . . , i3},
al igual que y, entonces Vα(x) = Vα(y). Nuevamente, un caso particular sería por ejemplo
j = 4 y k = 7.
Esto ilustra la primera contención de la afirmación de la Proposición 6.
• {i |Vi ⊆ Vj} ⊆ Wj
Para la segunda contención, tomemos de nuevo el casoWj = R1 ∪ R2 ∪ R3.
Si k ∈ {i |Vi ⊆ Vj}, esto quiere decir que Vk ⊆ Vj. Como j ∈ R3, entonces de nuevo el elemento
y tal que α(y) = j está en el conjunto {i2 + 1, . . . , i3} y elemento x tal que α(x) = k está en el
52 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
conjunto {0, . . . , i3}. Así, se tiene que Vα(x) ⊆ Vα(y) y de esta forma, por como fue construida la
partición, se tiene que k ∈ Rm con 1 ≤ m ≤ 3. Entonces Rm puede ser R1, R2 o R3 y en cualquier
caso se tiene Rm ⊆ R1 ∪ R2 ∪ R3 =Wj. Por lo tanto k ∈ Wj.
Esto ilustra la segunda contención de la afirmación de la Proposición 6.
Recordemos que se propusieron casos particulares y de ninguna manera constituyen una demostración
en general, como la que ya se dio anteriormente.
Ilustremos ahora que se cumple la igualdad Vj = {i |Vi ⊆ Vj} para algún Vj en particular que tomare-
mos del simplejo σ inicial.
Pensemos, por ejemplo, en V4 = {0, 1, 2, 3,4, 7} ∈ σ. Los i tales que Vi ⊆ V4 serían los que correspon-
den a los siguientes conjuntos:
V0 = {0, 1, 2, 3},
V1 = {0, 1, 2, 3},
V2 = {2, 3},
V3 = {2, 3},
V4 = {0, 1, 2, 3,4, 7} y
V7 = {0, 1, 2, 3,4, 7}.
Es decir, para i ∈ {0, 1, 2, 3,4, 7} se tiene Vi ⊆ V4, pero {0, 1, 2, 3,4, 7} es precisamente V4.
Hasta aquí el ejemplo de Vj = {i |Vi ⊆ Vj}.
De acuerdo a la demostración de la Proposición 6, se tiene que
W0 = {0, 1, 2, 3} = V0
W1 = {0, 1, 2, 3} = V1
W2 = {2, 3} = V2
W3 = {2, 3}) = V3
W4 = {0, 1, 2, 3,4, 7} = V4
W5 = {0, 1, 2, 3,4, 5, 6, 7} = V5
W6 = {0, 1, 2, 3,4, 5, 6, 7} = V6
W7 = {0, 1, 2, 3,4, 7} = V7
y por lo tanto ϕ(ψ(σ)) = σ.
En relación con la interpretación que hemos explicado antes, donde los n-simplejos de χ(∆n) son las
distintas formas, en cuanto al orden, en que n + 1 procesos pueden terminar sus ejecuciones o n + 1
caballos pueden acabar la carrera, una pregunta que surge naturalmente es cuántas posibilidades distintas
53
hay para tales procesos (o caballos) de terminar. La proposición que a continuación presentamos responde
a esta pregunta.
Al formular tal proposición, nos hemos encontrado una bella sucesión que ha sido llamada la sucesión
de los números ordenados de Bell o los números de Fubini y va así:
1, 1, 3, 13, 75, 541,4683,47293, 545835, 7087261, 102247563, . . .
Exhortamos a la lectora o lector a notar que en las páginas anteriores se ha visto cómo el complejo
χ(∆1) tiene tres simplejos de dimensión máxima y el complejo χ(∆2) tiene trece simplejos de dimensión
máxima. Por si fuera poco, en el Apéndice A de este trabajo hemos incluido una lista exhaustiva y con
dibujos de los setenta y cinco simplejos de dimensión máxima del complejo χ(∆3) − no hemos podido
añadir dibujos de algunas de las siguientes subdivisiones cromáticas porque los objetos en dimensión
cuatro son harto más difíciles de dibujar −.
Proposición 7. El número de simplejos n-dimensionales de χ(∆n) está dado por la fórmula
an+1 =
n+1∑
k=1
(
n+ 1
k
)
a(n+1)−k,
con a0 = 1.
Demostración. Primero, observemos que como hay una correspondencia biunívoca entre los n-simplejos
de χ(∆n), que pertenecen al conjunto Sn, y las particiones ordenadas que pertenecen al conjunto Pn,
basta demostrar que el número de particiones ordenadas, es decir, la cardinalidad de Pn, está dada por la
fórmula
an+1 =
n+1∑
k=1
(
n+ 1
k
)
a(n+1)−k, (3.4)
con a0 = 1.
La prueba se hará por inducción fuerte.
Base de inducción:
• Consideremos n = 0. En tal caso [n] = {0} y P0 = { ({0}) }, por lo que |P0| = 1. Además
an+1 = a0+1 = a1 =
0+1∑
k=1
(
0+ 1
k
)
a(0+1)−k =
(
1
1
)
a1−1 = 1a0 = 1.
Por lo tanto, para n = 0 se cumple an+1 = |Pn|.
• Lo verificamos también para n = 1, que es un poquito menos trivial que el caso anterior.
El conjunto de las posibles particiones ordenadas de [1] = {0, 1} es
P1 = { ({0}, {1}), ({1}, {0}), ({0, 1}) },
entonces |P1| = 3.
54 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Por otro lado:
a1+1 = a2 =
1+1∑
k=1
(
1+ 1
k
)
a(1+1)−k
=
2∑
k=1
(
2
k
)
a2−k
=
(
2
1
)
a2−1 +
(
2
2
)
a2−2
= 2a1 + 1a0 = (2)(1) + (1)(1) = 3.
Por lo tanto, para n = 1 se cumple an+1 = |Pn|.
Hipótesis de inducción:
Supongamos que para todo i tal que i < n se cumple que el número de elementos de Pi está dado por
ai+1 =
i+1∑
ℓ=1
(
i+ 1
ℓ
)
a(i+1)−ℓ,
con a0 = 1.
Paso inductivo:
Demostraremos que para i = n, el número de elementos de Pn está dado por la fórmula 3.4.
Sea E un elemento de Pn, entonces
E = (R1, · · · , Rt)
con 1 ≤ t ≤ n+ 1; donde para todo j ∈ {1, · · · , t}, Rj 6= ∅; para i 6= j, Ri ∩ Rj = ∅ y
t⋃
j=1
Rj = [n].
Como Rj 6= ∅ para todo j ∈ {1, · · · , t}, en particular para R1 se cumple que |R1| = k para algún k ∈
{1, · · · , n+ 1} (pues recordemos que el conjunto [n] tiene n+ 1 elementos).
En esta parte, vamos a considerar por separado los casos |R1| = n+ 1 y |R1| = k para k ∈ {1, . . . , n}.
• Caso |R1| = n+ 1.
Observemos que las formas de elegir n + 1 elementos de R1 son
(
n+1
n+1
)
= 1. Esto corresponde con
que el conjunto Pn sólo puede tener a R1 como elemento, ya que no hay más de n+ 1 elementos en
[n]. Entonces podemos escribir la cardinalidad de Pn como:
|Pn| = 1 =
(
n+ 1
n+ 1
)
a(n−(n+1))+1 = 1a0. (3.5)
55
• Caso |R1| = k para k ∈ {1, . . . , n}.
Aquí, sabemos que las formas de elegir los elementos de R1 son
(
n+ 1
k
)
.
Ahora definamos una nueva partición E ′ a partir de E, para lo que quitaremos de E el conjunto R1,
entonces
E ′ = (R2, · · · , Rt)
donde ahora 2 ≤ t ≤ n + 1. En esta parte es importante notar que E ′ es una partición del
conjunto [n]\R1, cuya cardinalidad es |[n]\R1| = (n + 1) − k, mas E ′ no es una partición del
conjunto [n − k], cuya cardinalidad también es |[n − k]| = (n − k) + 1 = (n + 1) − k. Sin
embargo, por las últimas observaciones sabemos que si Ê ∈ Pn−k tal que Ê = (R̂1, · · · , R̂s),
entonces
∣∣∣∣∣
s⋃
i=1
R̂i
∣∣∣∣∣ = |[n − k]| =
∣∣∣∣∣
t⋃
i=2
Ri
∣∣∣∣∣, es decir, E ′ es una partición de un conjunto que tiene el
mismo número de elementos que el conjunto [n−k]. Entonces hay tantas particiones E ′ de [n]\R1
como particiones en el conjunto Pn−k.
Para averiguar el número de elementos de Pn−k, observemos que por hipótesis de inducción para
i = n− k < n el número de elementos de Pi está dado por a(n−k)+1.
Entonces, de acuerdo a lo dicho anteriormente, el número total de particiones E en χ(∆n) tales que
|R1| = k es (
n+ 1
k
)
a(n−k)+1.
Como queremos contar el número total de particiones, debemos considerar que k puede ser cual-
quier elemento del conjunto {1, . . . , n}, entonces, de acuerdo a nuestro razonamiento anterior, el
número total de particiones en Pn es
|Pn| =
n∑
k=1
(
n+ 1
k
)
a(n−k)+1. (3.6)
con a0 = 1.
Finalmente, para contar el número total de elementos de Pn debemos considerar |R1| = k con k ∈
{0, . . . , n+ 1}, es decir, hace falta considerar los dos casos anteriores. De acuerdo a las ecuaciones 3.5 y
3.6, el número total de elementos en Pn es
|Pn| =
n∑
k=1
(
n+ 1
k
)
a(n−k)+1 +
(
n+ 1
n+ 1
)
a(n−(n+1))+1 =
n+1∑
k=1
(
n+ 1
k
)
a(n−k)+1
con a0 = 1, pero
n+1∑
k=1
(
n+ 1
k
)
a(n−k)+1 =
n+1∑
k=1
(
n+ 1
k
)
a(n+1)−k = an+1.
56 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Por lo tanto, el número total de elementos en Pn es
an+1 =
n+1∑
k=1
(
n+ 1
k
)
a(n+1)−k.
con a0 = 1. 
3.1. Diagramas de Schlegel
A continuación explicaremos cómo se puede construir la subdivisión cromática χ(∆n) a partir de los
llamados diagramas de Schlegel. Antes que nada, procedemos a formular la definición de un diagrama
de Schlegel, para lo que necesitaremos algunos otros conceptos que tomamos de los libros Grünbaum
[2003] y Ziegler [1995].
Usamos Rd para referirnos al espacio euclideano d-dimensional.
Definición 48 (Segmento entre dos puntos). Sean p y q dos puntos en Rd. El segmento determinado por
p y q es el conjunto
S = { s | s = λp+ (1− λ)q, 0 ≤ λ ≤ 1}.
Definición 49 (Conjunto convexo). Un conjunto A ⊆ Rd es llamado convexo si para cualquier par de
puntos en él, el segmento que los une se encuentra también completamente contenido en él.
Definición 50 (Envolvente convexa). Para cualquier conjunto no vacío A ⊆ Rd, su envolvente convexa
es el conjunto convexo "más pequeño"que contiene a A y se puede construir como la intersección de
todos los subconjuntos convexos que contienen a A:
conv(A) :=
⋂
{A ′ ⊆ Rd |A ⊆ A ′ t.q. A ′es convexo}.
Equivalentemente4, podemos escribir la envolvente convexa de A de la siguiente manera:
conv(A) :=
{
k∑
i=1
λixi
∣∣∣∣∣∣
{x1, . . . , xk} ⊆ A, λi ≥ 0,
k∑
i=1
λi = 1
}
.
Definición 51 (Punto extremo y extA.). Sea A un conjunto convexo tal que A ⊂ Rd. Un punto x ∈ A
es un punto extremo de A si se cumple que para todo p, q ∈ A, si x = λp+ (1− λ)q, con 0 ≤ λ ≤ 1,
entonces x = p = q. En otras palabras, x es un punto extremo de A si x no pertenece al interior relativo
de ningún segmento contenido en A.
El conjunto de todos los puntos extremos de A se denota como extA.
Ejemplo 16. Consideremos un conjunto T de puntos en R2 que formen un triángulo con vértices A, B y
C. Sabemos que T es un conjunto convexo.
Un punto x en el interior de T no es un punto extremo de T , ya que hay al menos un segmento cuyo
interior tiene a x (de hecho, existen una infinidad de segmentos que cumplen esto). Ver Figura 3.5a.
4Si se quiere ver una demostración de esta equivalencia, puede dirigirse a [Ziegler, 1995, p. 4].
3.1. DIAGRAMAS DE SCHLEGEL 57
Un punto y en el interior de una arista de T , digamos en la arista que va del punto A al punto C,
tampoco es un punto extremo de T pues, por ejemplo, la misma arista es un segmento que tiene a y en
su interior y está contenida en T , entonces y tampoco cumple con la definición de ser un punto extremo.
Ver Figura 3.5b.
Ahora, si consideramos un vértice de T , por ejemplo el vértice C, podemos darnos cuenta de que C sí es
un punto extremo de T , ya que ningún segmento formado por puntos de T tiene a C en su interior. Lo
mismo ocurre para los vértices A y B. Ver Figura 3.5c.
x
p
q
A
B C
(a)
y
A
B C
(b)
A
B C
(c)
Figura 3.5
Por lo tanto, el conjunto de puntos extremos de T es ext T = {A,B,C}.
Definición 52 (Politopo). Sea Rd el espacio euclideano d-dimensional y consideremos A un conjunto
compacto y convexo tal que A ⊂ Rd. Decimos que A es un politopo si extA es un conjunto finito.
Ejemplo 17. Mencionaremos un ejemplo de politopo y otros dos conjuntos que no son politopos:
a) El triángulo T del ejemplo 16 es un conjunto compacto y convexo que sólo tiene tres puntos extremos
(sus vértices), por lo tanto, es un politopo.
b) Un círculo C , es decir, un disco cerrado contenido en R2, es un conjunto convexo que tiene un número
infinito de puntos extremos: sus puntos extremos son todos los puntos de la circunferencia, es decir,
todos los puntos en la frontera de C . Por lo tanto, C no es un politopo.
C extC
Figura 3.6: A la izquierda un círculo, a la derecha el conjunto de sus puntos extremos.
58 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
c) Un círculo abierto o disco abierto C o contenido en R2 es un conjunto convexo que no tiene puntos
extremos, es decir, extC o = ∅. Sabemos que el conjunto vacío es finito, empero, C o no es un politopo
ya que no es compacto.
Definición 53 (Hiperplano (afín y lineal), semiespacio abierto y semiespacio cerrado). Se define lo si-
guiente:
• Dados y ∈ Rd, y 6= 0 y α ∈ R, se define un hiperplano Hy,α como el conjunto
Hy,α = {x ∈ Rd | 〈 x, y〉 = α}.5
Diremos que Hy,α es un hiperplano afín y en el caso particular cuando α = 0 diremos que Hy,α
es un hiperplano lineal.6
• Un semiespacio abierto se define como
{x ∈ Rd | 〈 x, y〉 > α}
para algunos y ∈ Rd, y 6= 0 y α ∈ R.
• Un semiespacio cerrado se define como
{x ∈ Rd | 〈 x, y〉 ≥ α}
para algunos y ∈ Rd, y 6= 0 y α ∈ R.
Obsérvese que {x ∈ Rd | 〈 x, y〉 < α} es también un semiespacio abierto para y 6= 0 y, de igual manera,
{x ∈ Rd | 〈 x, y〉 ≤ α} es un semiespacio cerrado para y 6= 0.
Definición 54 (Hiperplano corta a un conjunto). Sean A ⊆ Rd y u ∈ Rd un vector unitario. Decimos
que un hiperplano
Hu,α = {x ∈ Rd | 〈 x, u〉 = α}
corta a A si ambos semiespacios determinados por Hu,α contienen puntos de A. En otras palabras, Hu,α
corta a A si existen x1, x2 ∈ A tales que 〈 x1, u〉 < α y 〈 x2, u〉 > α.
Definición 55 (Hiperplano soporta a un conjunto). Decimos que un hiperplano Hu,α soporta a A si
Hu,α no corta a A sino que la distancia entre A y Hu,α es cero. En otras palabras, Hu,α soporta a A si
sup {〈 x, u〉 | x ∈ A} = α o bien si inf {〈 x, u〉 | x ∈ A} = α.
Definición 56 (Cara y cara impropia de un conjunto convexo). Sea K ⊆ Rd tal que K es convexo.
• Un conjunto F ⊂ Rd es una cara de K si F = ∅, F = K o bien existe un hiperplano soporte H de K
tal que F = K ∩ H.
• Los conjuntos ∅ y K son llamados caras impropias de K.
• El conjunto de todas las caras de K se denota como F (K).
5〈·, ·〉 es el producto escalar en Rd definido como 〈a, b〉 =
∑d
i=1
αiβi donde a = (α0, . . . , αd) y b = (β0, . . . , βd).
6Obsérvese que y y α no están unívocamente determinados, ya que pueden existir y ′, α ′ ∈ Rd, con y ′ 6= 0, tales que
Hy,α = Hy ′,α ′ .
3.1. DIAGRAMAS DE SCHLEGEL 59
Ejemplo 18. Si consideramos el círculo C del ejemplo 17.b, que es un conjunto convexo, podemos notar
que este tiene una infinidad de caras, ya que para cada punto x en la circunferencia de C , la tangente
al círculo que pasa por x es un hiperplano soporte Hx de C , entonces C ∩ Hx = {x}. Por lo tanto,
el conjunto F (C ) tiene en particular a todos los conjuntos de la forma {x} donde x es un punto en la
circunferencia de C. Estos conjuntos son todas las caras de dimensión 0 de C .
C
x
Hx
Observemos que C no tiene caras de dimensión 1. Por lo tanto,
F (C ) = { {x} | x está en la circunferencia de C } ∪ {∅} ∪ {C }.
Definición 57 (Punto expuesto). Sea K ⊆ Rd tal que K es convexo.
• Un punto x ∈ K es un punto expuesto de K si el conjunto {x} es una cara de K.
• El conjunto de todos los puntos expuestos de K se denota como expK.
Para cualquier conjunto convexo K ⊆ Rd se tiene que expK ⊆ extK. Sin embargo, no para cualquier
conjunto se cumple que extK ⊆ expK, es decir, los conjuntos expK y extK no son iguales para cualquier
conjunto convexo. Veamos un ejemplo:
Ejemplo 19. Consideremos el conjunto K convexo formado por los puntos de un cuadrado, digamos
todos los puntos del conjunto [0, 1]× [0, 1], al que le unimos un semicírculo en uno de sus lados, digamos
el lado derecho. El semicírculo resulta de dividir en dos partes un círculo (cuyo diámetro mide lo mismo
que cualquiera de los lados del cuadrado), con una línea vertical que pasa por su centro; de las dos
partes resultantes, en este ejemplo tomamos la del lado derecho. Para nuestro ejemplo, nos servirá el
círculo con centro en el punto (1, 1
2
) y radio r = 1
2
. El conjunto que nos queda se muestra en la siguiente
figura.
K
A
B C
D
60 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
En la figura hemos etiquetado los vértices del cuadrado con las letrasA,B,C yD. Veamos ahora cuáles
son los puntos expuestos y extremos de nuestro conjunto K.
• Puntos expuestos:
Las caras de K que constan de un único punto son los vérticesA y B del cuadrado, junto con todos
los puntos en la circunferencia del semicírculo, a excepción de C y D. Entonces el conjunto expK
es como se muestra en la Figura 3.7a.
• Puntos extremos:
Los puntos de K que no están contenidos en el interior de ningún segmento contenido en K son los
vértices A,B,C y D del cuadrado, junto con todos los puntos en la circunferencia del semicírculo.
Conviene destacar que los puntos C y D sí son puntos extremos de K. El conjunto extK es el que
se muestra en la Figura 3.7b.
A
B C
D
(a) expK
A
B C
D
(b) extK
Figura 3.7
Notemos que expK ⊂ extK pero expK 6= extK, ya que C,D ∈ extK mas C,D 6∈ expK.
Una última observación es que el conjunto K no es un politopo.
En esta parte, es interesante observar que si K es un politopo entonces los conjuntos expK y extK
coinciden, o sea expK = extK. En otras palabras, cada punto de extK es una cara de K.
Definición 58 (Recta). El conjunto de todas las combinaciones afines de dos puntos distintos x, y ∈ Rd
es la recta
L(x, y) = {(1− λ)x+ λy | λ ∈ R}.
Definición 59 (Variedad afín y variedad lineal). Damos las siguientes definiciones:
• Un conjunto H ⊆ Rd es llamado una variedad afín si todos los hiperplanos que contiene H son
lineales. Obsérvese que H tiene la propiedad de que L(x, y) ⊂ H cuando x, y ∈ H, x 6= y.
3.1. DIAGRAMAS DE SCHLEGEL 61
• Diremos que un conjunto H ⊆ Rd es una variedad lineal si H es un subespacio vectorial de Rd.
Notemos que en este caso H incluye al vector cero 0̂ ∈ Rd.
La familia de todas las variedades afines en Rd contiene al conjunto ∅, a Rd, a todos los conjuntos con un
sólo punto, a todas las rectas y a todos los hiperplanos. Además, es interseccional, lo que significa que si
se tiene una familia de conjuntos {Hα} tal que cada Hα es una variedad afín, entonces
⋂
α
Hα es también
una variedad afín.
Definición 60 (Envolvente afín). La envolvente afín de A, denotada como affA, es el conjunto de todas
las combinaciones afines formadas a partir de todos los subconjuntos finitos de un conjunto dado A.
Obsérvese que el conjunto affA es una variedad afín.
La envolvente afín de A se puede definir alternativamente como la intersección de todas las variedades
afines que contienen a A.
Ejemplo 20. Veamos que la envolvente afín del 2-politopo en R3 que se muestra en la Figura 3.8 (en este
caso, el 2-politopo es un triángulo), que tiene como vértices a los puntos (0,−1, 5), (4,0, 2) y (2,4, 2),
es un plano, el cual se puede describir como el conjunto de los x ∈ R3 tales que a · x = d para a ∈ R3
(un vector normal al plano) y d ∈ R.
X
Z
Y
(4, 0, 2)
(2, 4, 2)
(0,−1, 5)
Figura 3.8: Un 2-politopo en R3.
Las combinaciones afínes de los puntos (0,−1, 5), (4,0, 2), (2,4, 2) son de la forma
λ1(0,−1, 5) + λ2(4,0, 2) + λ3(2,4, 2),
donde λi ∈ R para cada i ∈ {1, 2, 3} y
∑
3
i=1
λi = 1. Cualquier punto con dicha descripción se encuen-
tra en el plano definido por los vértices del 2-politopo y, de acuerdo a los signos de los λis, el punto
puede estar dentro del triángulo, en uno de los lados, fuera del triángulo o ser un vértice, pero siempre
pertenecerá al plano definido por los vértices del triángulo.
62 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Ahora, para escribir la ecuación del plano en la forma a· x = d nos conviene encontrar el vector normal
al plano, lo cual hacemos a continuación:
Primero, para facilitar los cálculos, llamaremos a los puntos de la siguiente manera:
P = (0,−1, 5), Q = (4,0, 2) y R = (2,4, 2).
Ahora, encontramos dos vectores u y v que sean paralelos al plano:
u = Q− P = (4,0, 2) − (0,−1, 5) = (4, 1,−3)
v = R− P = (2,4, 2) − (0,−1, 5) = (2, 5,−3).
Como el producto cruz (al que llamaremos a) de u y v es ortogonal tanto a u como a v, entonces será
normal al plano. Procedamos a calcularlo:
a = u× v =
∣∣∣∣∣∣∣
î ĵ k̂
4 1 −3
2 5 −3
∣∣∣∣∣∣∣
= 12 î + 6 ĵ + 18 k̂ = (12, 6, 18).
Así, la ecuación del plano se puede escribir como:
12(x− 0) + 6(y+ 1) + 18(z− 5) = 0,
es decir,
12x+ 6y+ 18z = 84,
o bien,
(12, 6, 18)


x
y
z

 = 84.
Si d = 84 entonces la expresión a · x = d es exactamente la ecuación del plano.
Definición 61 (Dimensión). Toda variedad afín H es una traslación H = x+V de alguna variedad lineal
V ⊆ Rd, por lo queH es isomorfa a un espacio euclideano (es decir, a un subespacio de Rd) de dimensión
r ≤ d. La dimensión de H (y de V) es entonces
r = dim H = dim V.
Una variedad afín de dimensión r será llamada una r-variedad y por convención dim ∅ = −1.
En general, en lugar de decir “un objeto de dimensión r” usaremos el término “un r-objeto”, que es más
corto.
3.1. DIAGRAMAS DE SCHLEGEL 63
Si A es cualquier subconjunto de Rd, la dimensión de A se define como
dim A = dim affA.
Definición 62 (Vértices, aristas, facetas, d-politopo y k-cara). Para un politopo K definimos lo siguiente:
• Se llama vértices a los puntos de extK y se denota a la totalidad de los vértices como vert K.
• A las 1-caras de K se les llama aristas.
• A las caras maximales propias de K se les llama facetas de K.
• A un politopo de dimensión d lo llamaremos un d-politopo y a una cara de dimensión k la llama-
remos una k-cara.
Definición 63 (Politopo simplicial). Un d-politopo es llamado politopo simplicial si todas sus facetas
son (d− 1)-simplejos.
Definición 64 (Politopo cruzado). Sea ei, con i = 1, . . . , d+1, el punto en Rd+1 cuya i-ésima coordenada
es uno y todas las coordenas restantes son cero. Entonces el conjunto
{e1, . . . , ed+1,−e1, . . . ,−ed+1}
tiene 2d+2 puntos en total. A la envolvente convexa de este conjunto le llamaremos el politopo cruzado
de dimensión d+ 1.
Ejemplo 21. A continuación, mostramos los tres ejemplos de politopos cruzados:
a. Supongamos que d = 0, entonces e1 = 1 ∈ R y obsérvese que i = 1.
El conjunto {e1,−e1} = {1,−1} tiene dos puntos en total y el politopo cruzado de dimensión uno
consiste de estos dos puntos y el segmento de recta que pasa entre ellos, como se muestra en la figura:
o
e1−e1
b. Supongamos que d = 1, entonces e1 = (1,0), e2 = (0, 1) ∈ R2 y obsérvese que i = 1, 2.
El conjunto {e1, e2,−e1,−e2} = {(1,0), (0, 1), (−1,0), (0,−1)} tiene cuatro puntos en total y el po-
litopo cruzado de dimensión dos es un cuadrado que tiene como vértices estos puntos, tal como se
muestra en la figura:
64 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
e1−e1
e2
−e2
X
Y
c. Supongamos que d = 2, entonces e1 = (1,0,0), e2 = (0, 1,0), e3 = (0,0, 1) ∈ R3 y obsérvese que
i = 1, 2, 3.
El conjunto {e1, e2, , e3,−e1,−e2,−e3} = {(1,0,0), (0, 1,0), (0,0, 1), (−1,0,0), (0,−1,0), (0,0,−1)}
tiene seis puntos en total y el politopo cruzado de dimensión tres es un octaedro que tiene como vér-
tices los puntos de dicho conjunto:
e1
−e2
−e1
−e3
e3
X
Z
Y
e2
Definición 65 (Politopos combinatoriamente equivalentes). Se dice que dos politopos P y P ′ son combi-
natoriamente equivalentes o isomorfos o del mismo tipo combinatorio si existe una correspondencia
ϕ biyectiva entre el conjunto {F} de todas la caras de P y el conjunto {F ′} de todas las caras de P ′, tal que
ϕ preserva la inclusión (es decir, tal que F1 ⊂ F2 si y sólo si ϕ(F1) ⊂ ϕ(F2)).
Si P y P ′ son combinatoriamente equivalentes escribimos P ≈ P ′.
En particular, todos los d-simplejos son del mismo tipo combinatorio.
3.1. DIAGRAMAS DE SCHLEGEL 65
Definición 66 (H -poliedro). Un H -poliedro P ⊆ Rd es la intersección de semiespacios cerrados en
algún Rd, es decir,
P = P(A, z) = {x ∈ Rd | Ax ≤ z} para algunos A ∈ Rm×d, z ∈ Rd.
Aquí observamos que “Ax ≤ z” es la abreviatura usual para un sistema de desigualdades
a1x ≤ z1, . . . , amx ≤ zm
donde a1, . . . , am son las filas de A y z1, . . . , zm son las componentes de z.
Definición 67 (Complejo poliedral). Un complejo poliedral C es una colección finita de H -poliedros
en Rd tales que:
I) El H -poliedro vacío está en C .
II) Si P ∈ C entonces todas las caras de P también están en C .
III) La intersección P ∩ Q de dos H -poliedros P,Q ∈ C es una cara tanto de P como de Q.
Definición 68 (Complejo de politopos). C es un complejo de politopos si todos los poliedros en C son
(politopos) acotados.
Si un politopo P es un miembro de un complejo C , llamaremos a P una cara de C y escribiremos P ∈ C .
El número de k-caras de C se denotará como fk(C ).
Se dice que un complejo C es k-dimensional o un k-complejo, si algún miembro de C es un k-politopo
pero ningún miembro de C tiene dimensión mayor que k.
Definición 69 (Espacio subyacente asociado a un complejo C ). A un complejo C en Rd está asociado un
subespacio de Rd, al que llamamos espacio subyacente asociado a C , que consiste de todos los puntos
de los miembros de C y al que denotaremos como suby C . Entonces suby C =
⋃
P∈C
(P).
Definición 70 (Complejo frontera y C (P)). Entre los complejos más simples mencionamos los siguientes
dos, que están asociados a un k-politopo P:
• El complejo frontera B(P) de P, que es el complejo que consiste de todas las caras de P que
tienen dimensión a lo más k− 1.
• El complejo C (P) = B(P) ∪ {P} que consiste de todas las caras de P.
Definición 71 (Copo de caras). Para un complejo de politopos C se define su copo7 de caras
L(C ) := (C ,⊆)
que es el conjunto finito de politopos en C , ordenados por la inclusión.
7En la Definición 36 se explica qué es un copo.
66 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Definición 72 (Diagrama de Schlegel). Sean P ⊆ Rd un d-politopo en Rd y sea F0 ∈ L(P) una faceta de
P, definida por la desigualdad válida ax ≤ z. Recordemos que
aff F0 = {x ∈ Rd | ax = z}
es la envolvente afín generada por F0.
Elíjase un punto x0 6∈ P tal que entre todas las envolventes afines de las facetas de P, sólo la envolvente
afín de F0 separa a x0 y a P.
Para x ∈ P definimos la proyección Π : P → aff F0 como
Π(x) := x0 +
z− ax0
ax− ax0
(x− x0).
El diagrama de Schlegel de P basado en F0, denotado comoD(C (P), F0), es la imagen bajo Π de todas
las caras propias de P distintas de F0, es decir, es el sistema de conjuntos:
D(C (P), F0) := {Π(G) | G ∈ L(C (P))\ {P, F0} } ,
contenido en el hiperplano aff F0.
Proposición 8 (Subdivisión politópica). Una subdivisión politópica de un politopo P es un complejo C
tal que suby C = P.
Proposición 9. El diagrama de Schlegel de P basado en F0 es una subdivisión politópica de F0 que es
combinatoriamente equivalente al complejo B(P)\ {F0} de todas las caras propias de P distintas de F0.
Ejemplo 22. En este ejemplo el politopo P es un cuadrado y tomamos su lado base como la faceta F0
(podríamos haber tomado cualquiera de sus lados).
En la figura de abajo, a la izquierda se muestra la proyección de P en aff F0 por rayos emitidos desde un
punto x0 que cumple con las características requeridas en la Definición 72, mientras que a la derecha
aparece el diagrama de Schlegel resultante.
3.1. DIAGRAMAS DE SCHLEGEL 67
x0
F0
aff F0
P
Ejemplo 23. Ahora nuestro politopo P es un tetraedro y tomamos uno de sus triángulos (que se muestra
en azul en la figura de abajo, del lado izquierdo) como la faceta F0. Del lado derecho en la figura, se
muestra el diagrama de Schlegel que obtenemos en este caso.
x0 aff F0
P
F0
Ejemplo 24. El caso de un octaedro es similar, pero obsérvese que el diagrama de Schlegel obtenido
68 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
ahora es distinto al del ejemplo anterior.
x0
aff F0
P
F0
Ejemplo 25. Para la siguiente pirámide, se elaboró un diagrama de Schlegel basado en una faceta
(Figura 3.9) y otro basado en una faceta distinta (Figura 3.10). Es interesante notar que estos diagramas
de Schlegel no son iguales a pesar de que se obtienen de la misma pirámide.
x0
Figura 3.9
3.1. DIAGRAMAS DE SCHLEGEL 69
x0
Figura 3.10
Ejemplo 26. Por último, mostramos el diagrama de Schlegel correspondiente a un politopo que resulta
de unir dos tetraedros por una de sus caras.
x0
70 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
A continuación haremos la construcción de una subdivisión iterada de un complejo simplicial K, que
denotaremos como ΣP(K), para lo que usaremos diagramas de Schlegel de un conjunto P de ciertos
politopos simpliciales. La subdivisión cromática χ(∆d) resultará al sustituir el complejo simplicial K por
∆d y el conjunto P por los politopos cruzados, como veremos más adelante.
Definición 73 (Subdivisión simplicial). Sean:
• d un número entero positivo
• K un complejo simplicial
• σ un simplejo de K de dimensión d
• P un politopo simplicial de dimensión d+ 1
• F una cara de P de dimensión d
• ϕσ un isomorfismo que identifica a F con σ
Al reemplazar σ con el diagrama de Schlegel SchF(P) y extender esto a todo K resulta una subdivisión
de K a la que llamamos subdivisión simplicial de K y la denotamos como Σ(K, σ, P,ϕσ).
Ejemplo 27. Sea K el complejo simplicial:
K = { ∅, {0}, {1}, {2}, {3}, {4}, {5},
{0, 1}, {0, 2}, {1, 2}, {0, 3}, {0, 5}, {1, 3}, {1,4}, {2,4}, {2, 5}, {3,4}, {3, 5}, {4, 5},
{0, 1, 3}, {0, 2, 5}, {0, 3, 5}, {1, 2,4}, {1, 3,4}, {2,4, 5}, {3,4, 5} }.
el cual representamos en la siguiente figura:
{0} {1}
{2}
{5} {4}
{3}
Con fines de simplicidad y para mayor claridad, denotaremos los vértices {3} y {5} como a y b respecti-
vamente.
Además, llamemos σ = {3, 5} y denotemos como σ = ab al simplejo de dimensión uno cuyos extremos
son a y b, como se muestra en la figura:
3.1. DIAGRAMAS DE SCHLEGEL 71
b
a
σ
Consideremos d = 1. El politopo simplicial P de dimensión d + 1 = 2 que consideraremos en este
caso será el cuadrado del ejemplo 21. b, cuyos vértices son los puntos {(1,0), (0, 1), (0,−1), (−1,0)}.
Renombramos a estos puntos como a ′ = (0,−1), b ′ = (−1,0), c ′ = (0, 1) y d ′ = (1,0), ya que hacerlo
nos ayudará a simplificar la notación.
La cara F del politopo P será el segmento de recta que une los puntos (−1,0) y (0,−1), que es una cara
de P de dimensión 1.
En la siguiente figura se ilustra el diagrama de Schlegel del politopo P.
X
Y
P
F
d ′b ′
c ′
a ′
SchF(P)
El isomorfismo ϕσ que tomaremos en este caso será un isomorfismo ϕσ : F→ σ que manda el punto a ′
en el vértice a de K y el punto b ′ en el vértice b de K, de manera que manda la arista a ′b ′ en el simplejo
ab = σ de K.
Ahora realizamos lo siguiente de acuerdo a la Definición 73:
Paso 1: Sustituimos σ con SchF(P) en K. El conjunto resultante, que no es un complejo simplicial, nos
queda de la siguiente manera:
72 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
b
a
σ
Paso 2: Extendemos la subdivisión para obtener un complejo simplicial. Este último complejo simplicial
es la subdivisión simplicial de K y lo denotamos como Σ(K, σ, P,ϕσ).
b
a
Ahora, si consideramos el mismo complejo simplicial K y también el mismo politopo cruzado P y su
diagrama de Schlegel, pero elegimos un simplejo τ de K distinto a σ tal que St(σ) ∩ St(τ) = ∅, es decir,
tal que las estrellas de σ y de τ son ajenas, podemos realizar la subdivisión simplicial para σ y para τ
al mismo tiempo. Veamos:
Con el fin de simplificar la notación, llamaremos e = {4}, f = {2}, g = {0} y h = {1} a los vérti-
ces del complejo simplicial K que nos faltaba renombrar. Para representar las aristas y los triángulos
simplemente escribiremos los nombres de sus vértices juntos, en una sola palabra.
Sea τ = ef.
b
a
e
f
g h
σ
τ
Entonces
3.1. DIAGRAMAS DE SCHLEGEL 73
St(σ) = {σ, abg, abe} y St(τ) = {τ, efb, efh}.
Obsérvese que St(σ) ∩ St(τ) = ∅.
Consideremos ahora ϕσ como fue definido arriba y ϕτ como el isomorfismo ϕτ : F → τ que manda el
punto a ′ en el vértice e de K y el punto b ′ en el vértice f de K.
Podemos ahora realizar los pasos que hicimos anteriormente pero tomando en cuenta los simplejos σ y
τ al mismo tiempo:
Paso 1: Sustituimos σ y τ con SchF(P).
Paso 2: Extendemos la subdivisión para obtener un complejo simplicial. Este último complejo simplicial
es la subdivisión simplicial de K.
Consideremos un conjunto F de d-simplejos de K (con d ∈ Z+) tales que para σ, τ ∈ F , St(σ)∩St(τ) =
∅, es decir, tal que no exista un simplejo en K que contenga dos simplejos de F , y definamos Φ como:
Φ := {ϕσ |σ ∈ F }.
Dado que para cada σ ∈ F sólo St(σ) se subdivide, podemos pasar del complejo simplicial K a su sub-
división simplicial Σ(K, σ, P,ϕσ) al hacer las sudivisiones correspondientes para cada σ ∈ F de manera
simultánea e independiente. A esta subdivisión simplicial total la denotamos como Σ(K,F , P,Φ).
Otra observación importante es que sí importa la manera en que definamos cada isomorfismoϕσ. Veamos
el siguiente ejemplo:
74 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
Ejemplo 28. Sea K el complejo simplicial:
K = { ∅, {0}, {1}, {2}, {3}, {4}
{0, 1}, {0, 2}, {0, 3}, {0,4}, {1, 2}, {1, 3}, {1,4}, {3,4},
{0, 2, 3}, {0, 1,4}, {0, 3,4}, {1, 2, 3}, {1, 3,4} }.
{0} {1}
{2}
{3}
{4}
a e
c
b
d
Para simplificar la notación, llamaremos a = {0}, b = {3}, c = {2}, d = {4} y e = {1}. También, de la
misma manera que en el ejemplo anterior, para representar las aristas y los triángulos, escribiremos los
nombres de sus vértices juntos.
Consideremos σ = abc, el triángulo formado por los vértices a, b y c, y también el politopo simplicial
P formado por la unión de dos tetraedros, como en el ejemplo 26.
Entonces el diagrama de Schlegel SchF(P) es el mismo que mostramos en el ejemplo 26. En la figura de
abajo se muestra SchF(P) con los vértices etiquetados.
SchF(P)
a ′ b ′
c ′
x
y
En esta ocasión, definiremos dos isomorfismos distintos ϕσ : F→ σ y ψσ : F→ σ.
3.1. DIAGRAMAS DE SCHLEGEL 75
El isomorfismo ϕσ manda el punto a ′ en el vértice a de K, el punto b ′ en el vértice b de K y el punto c ′
en el vértice c de K. Por otro lado, el isomorfismo ψσ manda el punto a ′ en el vértice c de K, el punto b ′
en el vértice a de K y el punto c ′ en el vértice b de K.
En este caso, al sustituir σ por el diagrama de Schlegel SchF(P) en el complejo simplicial K, los objetos
resultantes son también complejos simpliciales (como se observa en la figura de abajo), por lo que ya no
hace falta extender la subdivisión.
ϕσ : F→ σ
a ′ 7→ a
b ′ 7→ b
c ′ 7→ c
Σ(K, σ, P,ϕσ)
a e
c
b
d
ψσ : F→ σ
a ′ 7→ c
b ′ 7→ a
c ′ 7→ b
Σ(K, σ, P,ψσ)
a e
c
b
d
Como se puede observar en la figura, los complejos simpliciales Σ(K, σ, P,ϕσ) y Σ(K, σ, P,ψσ) no son
isomorfos (basta ver, por ejemplo, que en el vértice b de Σ(K, σ, P,ψσ) inciden cinco aristas, pero en
Σ(K, σ, P,ϕσ) no existe ningún vértice en el que incidan exactamente cinco aristas).
Con este ejemplo hemos demostrado que cualquier subdivisión simplicial Σ(K, σ, P,ϕσ) sí depende de
cómo está definido el isomorfismo ϕσ.
Si en la Definición 73 pedimos que P sea un politopo simplicial regular, entonces no depende del isomor-
fismo y podemos escribir Σ(K, σ, P).
Construcción de la subdivisión iterada:
Sea K un complejo simplicial de dimensión n y sea K(i) el conjunto de los simplejos i-dimensionales de
K.
También, sea P = {Pd}d≥1 una familia de politopos simpliciales regulares, tales que para cada dimensión
d especificamos un politopo simplicial regular de dimensión d+ 1.
Construimos la subdivisión iterada que usa los diagramas de Schlegel de P de la siguiente manera:
• Paso 1: Reemplazamos K con X1 = Σ(K,K
(n), Pn).
• Paso 2: Reemplazamos X1 con X2 = Σ(X1, K
(n−1), Pn−1).
...
76 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
• Paso i: Reemplazamos Xi−1 con Xi = Σ(Xi−1, K
(n−i+1), Pn−i+1).
...
• Paso n: Reemplazamos Xn−1 con Xn = Σ(Xn−1, K
(1), P1).
Finalmente definimos
ΣP(K) := Xn.
Ejemplo 29. A continuación, para los casos d = 2 y d = 3, construiremos la subdivisión iterada del
simplejo ∆d , donde la familia P = {Pd}d≥1 será la familia infinita de los politopos cruzados.
1. Sea d = 2. Comenzamos con el complejo simplicial K = ∆2 y recordemos que ∆2(i) denota el
conjunto de los simplejos de dimensión i de ∆2.
• Paso 1: Reemplazamos ∆2 con X1 = Σ(∆
2, ∆2(2), P2).
• Paso 2: Reemplazamos X1 con X2 = Σ(X1, ∆
2(1), P1).
Finalmente definimos
ΣP(∆
2) : = X2.
(g) ∆2
(h) X1 = Σ(∆
2, ∆2(2), P2) (i) X2 = Σ(X1, ∆
2(1), P1)
Figura 3.11
2. Sea d = 3. Comenzamos con el complejo simplicial K = ∆3 y recordemos que ∆3(i) denota el
conjunto de los simplejos de dimensión i de ∆3.
• Paso 1: Reemplazamos ∆3 con X1 = Σ(∆
3, ∆3(3), P3).
• Paso 2: Reemplazamos X1 con X2 = Σ(X1, ∆
3(2), P2).
• Paso 3: Reemplazamos X2 con X3 = Σ(X2, ∆
3(1), P1).
3.1. DIAGRAMAS DE SCHLEGEL 77
Finalmente definimos
ΣP(∆
3) : = X3.
(a) ∆3
(b) X1 = Σ(∆
3, ∆3(3), P3)
(c) X2 = Σ(X1, ∆
3(2), P2) (d) X3 = Σ(X2, ∆
3(1), P1)
Figura 3.12
Es interesante notar que para los casos d = 2 y d = 3, se tiene que la subdivisión iterada del simplejo ∆d
coincide con la subdivisión cromática χ(∆d). De hecho, esto se cumple en general cuando la subdivisión
iterada ΣP(∆
d) se construye con la familia P = {Pd}d≥1 de politopos cruzados.
Teorema 2. Sea P la familia infinita de los politopos cruzados. Entonces
ΣP(∆
d) = χ(∆d).
En particular, χ(∆d) es una subdivisión de ∆d.
La demostración de este teorema puede revisarse en el artículo [Kozlov, 2012] y hace uso de la siguiente
proposición:
Proposición 10. Para k = 0, . . . , d, el complejo simplicial Xk tiene la siguiente descripción combinato-
ria:
1. Los vértices de Xk están indexados por los pares (i, A) tales que A ⊆ [d], i ∈ A y, o bien |A| = 1,
o bien |A| ≥ d− k+ 2.
78 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
2. Los d-simplejos de Xk están indexados por todos los conjuntos de d+ 1 vértices correspondientes
a las tuplas σ = ((i1, A1), . . . , (id+1, Ad+1)), con {i1, . . . , id+1} = [d], que satisfacen las siguientes
condiciones:
a) |A1| ≤ · · · ≤ |Ad+1|,
b) Si α < β y |Aβ| 6= 1 entonces Aα ⊆ Aβ,
c) |Ad−k+2| ≥ 2.
La demostración de esta proposición rebasa los fines de presente trabajo, pero se puede consultar en el
artículo Kozlov [2012].
Ejemplo 30. Consideremos d = 2. Analizaremos los casos k = 0, k = 1 y k = 2 uno por uno.
• Para k = 0.
(0, {0}) (1, {1})
(2, {2})
σ
X0
1. Los conjuntos A ⊆ [2] = {0, 1, 2} que cumplen |A| = 1 son A1 = {0}, A2 = {1} y A3 = {2}.
En este caso no hay ningún conjunto A que cumpla |A| ≥ d− k+ 2 = 4.
Por lo tanto, los vértices son (0, {0}), (1, {1}) y (2, {2}), como se ilustra en la figura.
2. Los 2-simplejos de X0 están indexados por todos los conjuntos de d+ 1 = 2+ 1 = 3 vértices
que corresponden a las tuplas
σ = ((i1, A1), (i2, A2), (i3, A3))
con {i1, i2, i3} = {0, 1, 2} = [2] que satisfacen las tres condiciones de la Proposición 10.
En este caso proponemos i1 = 0, i2 = 1 e i3 = 2, así como A1 = {0}, A2 = {1} y A3 = {2}.
Veremos que se cumplen las condiciones mencionadas:
a) Se cumple ya que |A1| = |A2| = |A3|.
b) En este caso no hay algún Ai, con 1 ≤ i ≤ 3, que cumpla |Ai| 6= 1, por lo que la
condición se cumple.
3.1. DIAGRAMAS DE SCHLEGEL 79
c) En este caso no existe algún Ad−k+2 ya que d − k + 2 = 2 − 0 + 2 = 4, por lo que
también se cumple esta condición.
Por lo tanto,
σ = ((i1, A1), (i2, A2), (i3, A3)) = ((0, {0}), (1, {1}), (2, {2}))
es la tupla que indexa al único 2-simplejo de X0.
• Para k = 1.
(0, {0, 1, 2})(1, {0, 1, 2})
(2, {0, 1, 2})
X1
1. Los conjuntos A ⊆ [2] que cumplen |A| = 1 son nuevamente A = {0}, A = {1} y A = {2}. El
único conjunto A ⊆ [2] que cumple |A| ≥ d− k+ 2 = 3 es el conjunto A = {0, 1, 2}.
Por lo tanto, se conservan los vértices (0, {0}), (1, {1}), (2, {2}) y además se agregan los
vértices (0, {0, 1, 2}), (1, {0, 1, 2}) y (2, {0, 1, 2}), los cuales se muestran en la figura.
σ2 σ3
σ1
σ4 σ5
σ6
σ7
2. Los 2-simplejos de X1 están indexados por todos los conjuntos de d+ 1 = 2+ 1 = 3 vértices
que corresponden a las tuplas
σ = ((i1, A1), (i2, A2), (i3, A3))
con {i1, i2, i3} = {0, 1, 2} = [2] que satisfacen las tres condiciones de la Proposición 10.
80 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
En este caso proponemos las tuplas
σ1 = ((0, {0}), (1, {1}), (2, {0, 1, 2}))
σ2 = ((0, {0}), (2, {2}), (1, {0, 1, 2}))
σ3 = ((1, {1}), (2, {2}), (0, {0, 1, 2}))
σ4 = ((0, {0}), (1, {0, 1, 2}), (2, {0, 1, 2}))
σ5 = ((1, {1}), (0, {0, 1, 2}), (2, {0, 1, 2}))
σ6 = ((2, {2}), (0, {0, 1, 2}), (1, {0, 1, 2}))
σ7 = ((0, {0, 1, 2}), (1, {0, 1, 2}), (2, {0, 1, 2}))
(3.7)
Veamos que se cumplen las condiciones mencionadas:
a) (I) σ1, σ2 y σ3 cumplen ya que para estas tres tuplas |A1| = |A2| < |A3|.
(II) σ4, σ5 y σ6 cumplen ya que para estas tres tuplas |A1| < |A2| = |A3|.
(III) σ7 cumple ya que para esta tupla |A1| = |A2| = |A3|.
b) (I) Para σ1, σ2 y σ3 sólo el conjuntoA3 cumple |A3| 6= 1, por lo que β sólo puede tomar
el valor β = 3. Observamos que α puede tomar los valores 1 y 2. Como para las
tres tuplas se tiene A1 ⊆ A3 y A2 ⊆ A3, se cumple la condición.
(II) Para σ4, σ5 y σ6 los conjuntos A2 y A3 cumplen |A2| 6= 1 y |A3| 6= 1, entonces β
puede tomar los valores 2 y 3. En este caso, α sólo puede tomar el valor 1. Como
para las tres tuplas se tiene A1 ⊆ A2 y A1 ⊆ A3, se cumple la condición.
(III) σ7 cumple ya que para esta tupla A1 = A2 = A3.
c) Tenemos que Ad−k+2 = A3 ya que d− k+ 2 = 2− 1+ 2 = 3. Notemos que para σi con
1 ≤ i ≤ 7 se tiene que |A3| ≥ 2. Así, se cumple la tercera condición.
Por lo tanto, las siete tuplas propuestas en (3.7) indexan a los 2-simplejos de X1.
• Para k = 2.
(1, {0, 1}) (0, {0, 1})
(2, {0, 2}) (2, {1, 2})
(0, {0, 2}) (1, {1, 2})
X2
1. Los conjuntos A que cumplen |A| = 1 son nuevamente A = {0}, A = {1} y A = {2}. Además,
los conjuntos A que cumplen |A| ≥ d− k+ 2 = 2 son {0, 1}, {0, 2}, {1, 2} y {1, 2, 3}.
3.1. DIAGRAMAS DE SCHLEGEL 81
Por lo tanto, se conservan los vértices (0, {0}), (1, {1}), (2, {2}), (0, {0, 1, 2}), (1, {0, 1, 2})
y (2, {0, 1, 2}). Además, se agregan los vértices (0, {0, 1}), (1, {0, 1}), (0, {0, 2}), (2, {0, 2}),
(1, {1, 2}) y (2, {1, 2}), los cuales se muestran en la figura.
σ8 σ9
σ7
σ10 σ11
σ12
σ13
σ5 σ6
σ2 σ4
σ1 σ3
2. Los 2-simplejos de X2 están indexados por todos los conjuntos de d+ 1 = 2+ 1 = 3 vértices
que corresponden a las tuplas
σ = ((i1, A1), (i2, A2), (i3, A3))
con {i1, i2, i3} = {0, 1, 2} = [2] que satisfacen las tres condiciones de la Proposición 10.
En este caso proponemos las tuplas
σ1 = ((0, {0}), (1, {0, 1}), (2, {0, 1, 2}))
σ2 = ((0, {0}), (2, {0, 2}), (1, {0, 1, 2}))
σ3 = ((1, {1}), (0, {0, 1}), (2, {0, 1, 2}))
σ4 = ((1, {1}), (2, {1, 2}), (0, {0, 1, 2}))
σ5 = ((2, {2}), (0, {0, 2}), (1, {0, 1, 2}))
σ6 = ((2, {2}), (1, {1, 2}), (0, {0, 1, 2}))
σ7 = ((0, {0, 1}), (1, {0, 1}), (2, {0, 1, 2}))
σ8 = ((0, {0, 2}), (2, {0, 2}), (1, {0, 1, 2}))
σ9 = ((1, {1, 2}), (2, {1, 2}), (0, {0, 1, 2}))
σ10 = ((0, {0}), (1, {0, 1, 2}), (2, {0, 1, 2}))
σ11 = ((1, {1}), (0, {0, 1, 2}), (2, {0, 1, 2}))
σ12 = ((2, {2}), (0, {0, 1, 2}), (1, {0, 1, 2}))
σ13 = ((0, {0, 1, 2}), (1, {0, 1, 2}), (2, {0, 1, 2}))
(3.8)
Veamos que se cumplen las condiciones mencionadas:
a) (I) Para las tuplas σ1, . . . , σ6 la condición se cumple ya que |A1| < |A2| < |A3|.
(II) Para las tuplas σ7, . . . , σ9 la condición se cumple ya que |A1| = |A2| < |A3|.
(III) Para las tuplas σ10, . . . , σ12 la condición se cumple ya que |A1| < |A2| = |A3|.
(IV) Para la tupla σ13 la condición se cumple ya que |A1| = |A2| = |A3|.
82 CAPÍTULO 3. SUBDIVISIÓN CROMÁTICA DE UN SIMPLEJO
b) (I) Para las tuplas σ1, . . . , σ6 tenemos que β puede tomar los valores 2 o 3, pero tene-
mos que en las seis tuplasA1 ⊆ A2 ⊆ A3. En consecuencia, se cumple la condición.
(II) Para las tuplas σ7, . . . , σ9 tenemos que β puede tomar los valores 1, 2 o 3, pero
tenemos que en las tres tuplas A1 = A2 ⊆ A3. En consecuencia, se cumple la
condición.
(III) Para las tuplas σ10, . . . , σ12 tenemos que β puede tomar los valores 2 o 3 y en ambos
casos Aβ = A2 = A3. Observemos que se tiene A1 ⊆ A2 = A3 para las tres tuplas.
En consecuencia, se cumple la condición.
(IV) Para la tupla σ13 la condición se cumple ya que A1 = A2 = A3.
c) Tenemos que Ad−k+2 = A2 ya que d− k+ 2 = 2− 2+ 2 = 2. Notemos que para σi con
1 ≤ i ≤ 13 se tiene que |A2| ≥ 2. Así, se cumple la tercera condición.
Por lo tanto, las trece tuplas propuestas en (3.8) indexan a los 2-simplejos de X2.
3.2. Conclusión
En resumen, en este capítulo proporcionamos distintas maneras de describir la subdivisión cromática de
un simplejo: por un lado, abordamos el enfoque abstracto y, por otro lado, el geométrico. Para aproximar-
nos mediante el enfoque geométrico, hicimos uso de diagramas de Schlegel. También, vimos que ambos
enfoques resultan ser equivalentes.
En ambos casos, la subdivisión cromática de un complejo simplicial viene a ser la salida de un algoritmo
cuyo dato de entrada es el complejo simplicial original y termina después de cierto número de iteraciones.
Cabe mencionar que desde la Definición 73 comenzamos a abordar el tema de la subdivisión simplicial
de un complejo simplicial, lo cual es un caso particular de la subdivisión cromática de un complejo
simplicial abstracto.
Capítulo 4
Subdivisión cromática de un complejo
simplicial
Definición 74. Para un complejo simplicial K arbitrario definimos la categoría de incidencia de K, y la
denotamos como I(K), de la siguiente manera:
• La clase de objetos de I(K) consiste de los simplejos de K.
• Los morfismos M(σ, τ), o simplemente σ→ τ, corresponden a las inclusiones σ ⊆ τ.
Ejemplo 31. Consideremos el complejo simplicial K = {∅, {0}, {1}, {0, 1}}, que es un 1-simplejo.
{0} {1}
La categoría de incidencia de K es la siguiente (Figura 4.1):
∅
||

""
{0}
!!
{1}
}}
{0, 1}
Figura 4.1
Como podemos observar, I(K) consta de 4 objetos y 5 morfismos.
Definición 75. Definimos la categoría de los complejos simpliciales, que denotamos como SS, como
sigue:
83
84 CAPÍTULO 4. SUBDIVISIÓN CROMÁTICA DE UN COMPLEJO SIMPLICIAL
• La clase de objetos consiste de todos los complejos simpliciales.
• Los morfismos M(K, L) corresponden a las funciones simpliciales.
Definición 76. Definimos un funtor SK : I(K) → SS de la siguiente manera:
• SK(σ) es el subcomplejo de K correspondiente a σ ∈ K.
• SK(σ→ τ) es la correspondiente inclusión simplicial.
Ejemplo 32. De nuevo, consideremos el complejo simplicial K del ejemplo 31: K = {∅, {0}, {1}, {0, 1}}.
El funtor SK manda la categoría I(K), que se muestra en la Figura 4.2 −donde ahora también hemos
etiquetado los morfismos −, en los objetos y morfismos que se muestran a la derecha, en la Figura 4.3.
Observemos que SK asocia a cada simplejo σ ∈ K el complejo simplicial generado por σ.
∅
m0
||
m01

m1
""
{0}
n0 !!
{1}
n1}}
{0, 1}
Figura 4.2
SK(∅) = {∅}
SK(m0)
tt
SK(m01)

SK(m1)
**
SK({0}) = {∅, {0}}
SK(n0) **
SK({1}) = {∅, {1}}
SK(n1)tt
SK({0, 1}) = {∅, {0}, {1}, {0, 1}}
Figura 4.3
Ejemplo 33. Afirmamos que en el ejemplo 32, el objeto K = SK({0, 1}), junto con los morfismos SK(n0),
SK(m01) y SK(n1) es un sumidero del funtor SK : I(K) → SS (ver Definición 42).
Primero, simplificaremos un poco la notación de la Figura 4.3 y llamaremos λa a los morfismos tales
que λa : SK(a) → K, para cada uno de los a ∈ O(I(K)). Entonces se cumplirá que
λ{0} = SK(n0)
λ∅ = SK(m01)
λ{1} = SK(n1).
Además, obsérvese que λ{0,1} : SK({0, 1}) → K es la identidad 1K.
El diagrama quedaría como sigue:
85
SK(∅)
SK(m0)
ww
λ∅

SK(m1)
''
SK({0})
λ{0} ''
SK({1})
λ{1}ww
SK({0, 1}) = K
Figura 4.4
Así, de acuerdo al diagrama de la Figura 4.4, para cada par de objetos a1, a2 tales quem ∈ MI(K)(a1, a2)
se cumple que λa2 ◦ SK(m) = λa1 , como se observa en la siguiente tabla:
a1 a2 Morfismo a1
m
−→ a2. Igualdad que se cumple.
∅ {0} m0 λ{0} ◦ SK(m0) = λ∅
∅ {1} m1 λ{1} ◦ SK(m1) = λ∅
∅ {0, 1} m01 λ{0,1} ◦ SK(m01) = λ∅
{0} {0, 1} n0 λ{0,1} ◦ SK(n0) = λ{0}
{1} {0, 1} n1 λ{0,1} ◦ SK(n1) = λ{1}
Por lo tanto, K es un sumidero del funtor SK.
Ahora, veremos en este mismo ejemplo que el colímite de SK es K. Los argumentos que daremos no son
difíciles de generalizar para dar una prueba de la Proposición 11.
Como ya vimos que SK({0, 1}) = K, ahora dibujaremos el diagrama del sumidero K junto con los mor-
fismos λa para a ∈ O(I(K)), que ya fueron definidos antes, simplemente como sigue:
SK(∅)
λ∅

SK({0})
λ{0} %%
SK({1})
λ{1}yy
K
λ{0,1}
YY
Queremos demostrar que para cualquier otro sumidero (L̃, {λ̃a}a∈O(I(K))) existe un único morfismo ϕ tal
que K ϕ
−→ L̃ y para todo a ∈ O(I(K)), λ̃a = ϕ ◦ λa .
Sea (L̃, {λ̃a}a∈O(I(K))) un sumidero de SK distinto de (K, {λa}a∈O(I(K))).
Proponemos ϕ := λ̃{0,1}.
De acuerdo al diagrama de la Figura 4.5, se cumplen las igualdades:
86 CAPÍTULO 4. SUBDIVISIÓN CROMÁTICA DE UN COMPLEJO SIMPLICIAL
λ̃∅ = λ̃{0,1} ◦ λ∅
λ̃{0} = λ̃{0,1} ◦ λ{0}
λ̃{1} = λ̃{0,1} ◦ λ{1}
λ̃{0,1} = λ̃{0,1} ◦ λ{0,1}
SK(∅)
λ∅

λ̃∅

SK({0})
λ{0} ##
λ̃{0}
--
SK({1})
λ{1}
tt λ̃{1}vvK
λ{0,1}
YY
λ̃{0,1}=ϕ
22 L̃
Figura 4.5
Luego, sólo nos resta ver que el morfismo ϕ es único.
Supongamos que existe otro morfismo ψ : K→ L̃ tal que para todo a ∈ O(I(K)), λ̃a = ψ ◦ λa.
En este caso, para {0, 1} ∈ O(I(K)) se cumple por un lado que
λ̃{0,1} = ϕ ◦ λ{0,1} = ϕ ◦ 1K = ϕ
y por otro lado
λ̃{0,1} = ψ ◦ λ{0,1} = ψ ◦ 1K = ψ
Por lo tanto ϕ = ψ y concluimos que el morfismo ϕ es único.
Así, hemos demostrado que el colímite de SK es K.
Lo expuesto en el ejemplo 33 es parte de algo más general, que enunciamos en la siguiente proposición:
Proposición 11. El colímite de SK es K, es decir,
colimSK = K.
Definición 77. Sea K un complejo simplicial y consideremos la categoría I(K) como fue definida arriba.
Construimos un funtor ΣK : I(K) → SS de la siguiente manera:
• ΣK(σ) := χ(σ) para σ ∈ K.
87
• ΣK(σ→ τ) es la correspondiente inclusión simplicial.
Entonces definimos χ(K) como el colímite de ΣK.
Obsérvese que por construcción de χ, si σ ⊆ τ entonces χ(σ) ⊆ χ(τ).
Teorema 3. Para un complejo simplicial arbitrario K, el complejo χ(K) es una subdivisión simplicial de
K.
Demostración. El Teorema 2 dice que si P es una familia de politopos cruzados, ΣP(∆
d) = χ(∆d). Esto
quiere decir que la subdivisión cromática de un simplejo es una subdivisión simplicial.
Ahora bien, comparemos los funtores SK y ΣK.
1. Sk : I(K) →SS.
SK(σ) = σSS
Al simplejo σ se le asocia σSS el subcomplejo de K determinado por σ.
SK(σ→ τ) = σSS → τSS.
En el lado izquierdo σ es un subsimplejo de τ, mientras que en el lado derecho σSS es un subcom-
plejo simplicial de τSS.
El colímite de SK es K como complejo simplicial.
2. ΣK : I(K) →SS.
ΣK(σ) = χ(σ).
Al simplejo σ se le asocia el subcomplejo de K que es la subdivisión cromática de σ.
ΣK(σ→ τ) = χ(σ) → χ(τ)
Definimos χ(K) como el colímite de ΣK.
En ambos casos podemos aplicar después el funtor olv : SS→Top1 que a cada complejo simplicial le
asocia el espacio topológico correspondiente a su realización geométrica. Resulta que para cada simplejo
σ
|SK(σ)| = |ΣK(σ)|
son el mismo espacio topológico, más aún,
|SK(K)| = |ΣK(K)|.
Es decir, |SK(K)| y |ΣK(K)| son homeomorfos.
Queremos concluir que
1olv viene de la palabra “olvido”.
88 CAPÍTULO 4. SUBDIVISIÓN CROMÁTICA DE UN COMPLEJO SIMPLICIAL
χ(K) es subdivisión simplicial de K.
Sabemos que si tenemos dos simplejos de K, σ1 y σ2, la subdivisión cromática de cada uno χ(σi) es
subdivisión simplicial del σi correspondiente.
Por otra parte, sea τ la intersección de σ1 y σ2. Tenemos que en la categoría de incidencias
τ→ σ1
τ→ σ2,
mientras que en la categoría SS tenemos
χ(τ) ⊂ χ(σ1)
χ(τ) ⊂ χ(σ2).
Esto implica que la subdivisión cromática de σ1 ∪ σ2 es una subdivisión simplicial de σ1 ∪ σ2. Dado que
K se obtiene pegando simplejos, la subdivisión cromática de K resulta ser subdivisión simplicial de K.

Capítulo 5
Aplicación al problema de la isla de los
muertos
A lo largo de este último capítulo abordaremos un problema llamado “La isla de los muertos” que to-
mamos del libro [Neve y Rosales, 2017, p. 46] y lo haremos de dos formas distintas: primero, usaremos
lo que hemos estudiado en el desarrollo de este trabajo sobre complejos simpliciales; en segundo lugar,
analizaremos el problema con base en la solución propuesta en la Stanford Encyclopedia of Philosophy
(ver Apéndice B) al problema de las niñas enlodadas. 1 El enunciado del problema es el siguiente:
Un grupo de muchachos despierta un día en la isla de los muertos. Desconcertados,
descubren que sus ojos han cambiado de color, algunos a grises, otros a negros.
Todos quieren abandonar cuanto antes aquel inquietante lugar, pues en él pululan mu-
chos espíritus, que es en lo que se convertirán con el tiempo si no logran salir de ahí. La
regla para que alguien pueda dejar la isla es que logre deducir correctamente el color de
sus ojos. Cada uno de ellos puede ver el color de los ojos de los demás, pero no el propio. Si
alguno hace la más ligera mención sobre el color de los ojos de otro, perderá su oportunidad
de escape y se convertirá en un espectro. Cada día, a las siete de la tarde, vendrá el barquero
Caronte a llevarse a todos los que digan correctamente el color de sus ojos.
Procederemos a analizar una por una las preguntas que se nos plantean en el libro [Neve y Rosales, 2017,
p. 46].
5.1. Primera pregunta
1. Hades, al verlos, les da la bienvenida, diciendo: “Me alegra que al menos uno de
ustedes tenga ojos grises”. ¿Pueden deducir el color de sus ojos para abandonar la isla?
¿Pueden abandonar la isla todos, o sólo algunos?
1Cabe mencionar que el problema de las niñas enlodadas mencionado en la introducción de este trabajo (ver 1.1) se
enuncia en la Stanford Encyclopedia of Philosophy con una ligera variación: en el problema que hemos presentado en la
introducción, todas las niñas anuncian que su frente está sucia hasta que el maestro les pregunta un número de veces igual al
número de niñas. En contraste, en el problema descrito en la Stanford Encyclopedia of Philosophy, algunas niñas anuncian
que su frente está sucia antes de que el padre les pregunte por última vez.
89
90 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
Supongamos que hay en total "n" muchachos. Analicemos algunos posibles casos:
• n = 1, es decir, sólo un muchacho llegó a la isla.
En este caso, el único muchacho que llegó a la isla es quien tiene los ojos grises.
• n = 2, es decir, dos muchachos llegaron a la isla.
Tenemos las siguientes posibilidades:
• Sólo 1 muchacho tiene ojos grises.
◦ El primer día.
El chico de ojos grises se da cuenta de que el otro tiene ojos negros y a las siete de la
tarde le anuncia a Caronte que él tiene ojos grises.
◦ El segundo día.
Al llegar este día, el otro muchacho que está en la isla recibió información extra del día
anterior, a saber, que el muchacho de ojos grises sabía que sólo él tenía ojos grises. Así,
puede estar seguro de que tiene los ojos negros y a las siete de la tarde de ese día le
anuncia a Caronte su color de ojos.
Conclusión: en este caso todos pudieron abandonar la isla.
• Ambos muchachos tienen los ojos grises.
◦ El primer día.
Cada uno de los chicos de ojos grises ve a otro chico de ojos grises, así, no puede decidir
si tiene los ojos grises o no. Al dar las siete de la tarde, nadie le anuncia su color de ojos
a Caronte.
◦ El segundo día.
El segundo día ambos chicos han recibido información extra: nadie anunció su color de
ojos el día anterior. Esto significa que ninguno de los chicos de ojos grises estaba seguro
de su propio color de ojos, entonces cada uno de ellos podía ver que el otro tenía ojos
grises.
De esta manera, el segundo día ambos pueden decidir su color de ojos y se lo anuncian a
Caronte a las siete de la tarde.
Conclusión: en este caso también logran abandonar la isla la totalidad de los muchachos.
Ahora vamos a realizar el complejo simplicial que nos ayuda a entender gráficamente la
solución del problema para el caso n = 2.
• El primer día, antes de haber escuchado la frase que dijo Hades, la situación de los
dos muchachos es la que explicamos en seguida.
Para facilitar la comprensión del complejo simplicial de abajo, imaginemos que uno de
los muchachos trae puesta una chamarra azul y el otro trae una chamarra anaranjada,
colores que asignaremos a sus vértices correspondientes.
En nuestro simplejo, el vértice con la etiqueta n ⊥ representa que el chico de la cha-
marra anaranjada no está seguro de cuál es su color de ojos − lo que se indica con ⊥
en esta etiqueta− , pero sabe que el chico de la chamarra azul tiene ojos negros −lo que
5.1. PRIMERA PREGUNTA 91
se indica con n en la misma etiqueta− . Es decir, convenimos que la primera posición
de cada etiqueta corresponde al muchacho de la chamarra azul y la segunda posición,
al de la chamarra anaranjada.
n ⊥
⊥ g g ⊥
⊥ n
Este complejo simplicial representa que los dos chicos están indecisos acerca de su
propio color de ojos, pero no así del color de ojos de su compañero. Cada 1-simplejo del
presente complejo simplicial representa cada uno de los mundos posibles, los cuales
son cuatro en total, a saber:
1. Simplejo { n ⊥,⊥ n } : Ambos tienen ojos negros.
2. Simplejo { g ⊥,⊥ n } : El primero tiene ojos grises y el segundo, ojos negros.
3. Simplejo { ⊥ g, n ⊥ } : El primero tiene ojos negros y el segundo, ojos grises.
4. Simplejo { ⊥ g, g ⊥ } : Ambos tienen ojos grises.
Por otro lado, al seguir el desarrollo hecho en la Stanford Encyclopedia of Philosophy
(ver Apéndice B), podemos dibujar una gráfica que representa la misma situación:
nn
ng gn
gg
2 1
1 2
En esta gráfica, la etiqueta n se usa cuando el muchacho tiene ojos negros y la etiqueta
g, cuando tiene ojos grises. También hay cuatro mundos posibles, representados ahora
por los vértices, que son los siguientes:
1. Vértice nn : Ambos tienen ojos negros.
2. Vértice gn : El primero tiene ojos grises y el segundo, ojos negros.
3. Vértice ng : El primero tiene ojos negros y el segundo, ojos grises .
4. Vértice gg : Ambos tienen ojos grises.
92 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
Las etiquetas 1 y 2 en las flechas de la gráfica indican que el muchacho 1 está indeciso
acerca de su color de ojos y que el muchacho 2 está indeciso acerca de su color de
ojos, respectivamente.
• También el primer día, pero una vez que los muchachos han escuchado la frase de
Hades, saben que al menos uno de ellos tiene ojos grises, por lo que se descarta
un mundo: aquel en que ambos tienen ojos negros. En el complejo simplicial esto se
representa como la operación de quitar un 1-simplejo.
n ⊥
⊥ g g ⊥
⊥ n
De acuerdo a lo expresado por Hades (sin detenernos a reflexionar en si confiar en el
dios del inframundo es lo más sensato) sabemos que necesariamente hay un chico de
ojos grises. Por lo tanto, para el vértice n ⊥, el muchacho de la chamarra anaranjada
puede deducir que él tiene los ojos grises.
Una situación análoga ocurre con el vértice etiquetado con ⊥ n, donde ahora el chico
de la chamarra azul deduce que él tiene los ojos grises.
De esta manera, quedan abarcadas las situaciones de los mundos 2 y 3.
Paralelamente, al seguir el desarrollo propuesto en la Stanford Encyclopedia of Phi-
losophy podemos, de manera análoga, quitar un vértice junto con las dos flechas que
apuntan a él en la gráfica, con lo que esta quedaría de la siguiente manera:
nn
ng gn
gg
1 2
Del mismo modo, se observa que el muchacho de ojos negros en el mundo ng y el
muchacho de ojos grises en el mundo gn, pueden deducir su color de ojos y pedirle a
Caronte, el segundo día, que los saque de la isla.
• Si el segundo día nadie dejó la isla, entonces la información adicional que recibieron
los muchachos es que hay más de uno de ellos que tiene los ojos grises.
Pongamos nuestra atención en sólo uno de los muchachos que tiene los ojos grises: él
no sabe su color de ojos, pero si ve sólo a un muchacho de ojos grises, puede saber que
5.1. PRIMERA PREGUNTA 93
él mismo también tiene los ojos grises, pues como habíamos adivinado antes, hay más
de uno de ellos que tiene los ojos grises. Lo mismo pasa para el segundo muchacho de
ojos grises.
La información extra nos permite remover del simplejo anterior los dos vértices con
etiquetas n ⊥ y ⊥ n, junto con la única arista de cada uno. A continuación mostramos
el simplejo resultante:
⊥ g g ⊥
Podemos notar que ahora hay un sólo mundo posible: aquel en el cual tanto el mu-
chacho de la chamarra anaranjada como el de la chamarra azul tienen los ojos grises y
están seguros de ello.
Equivalentemente, la gráfica que resulta del estudio basado en la Stanford Encyclope-
dia of Philosophy es la siguiente:
gg
• n = 3, es decir, tres muchachos llegaron a la isla.
• Hay un muchacho con ojos grises.
◦ El primer día.
El chico de ojos grises se da cuenta de que todos los demás tienen ojos negros y a las
siete de la tarde le anuncia a Caronte que él tiene ojos grises.
◦ El segundo día.
Al llegar este día, todos los muchachos que quedaron en la isla recibieron información
extra del día anterior, a saber, que el chico de ojos grises veía que todos los demás tenían
ojos negros. Así, intuyen que ellos tienen ojos negros y a las siete de la tarde de ese día
le anuncian a Caronte su color de ojos.
• Hay dos muchachos con ojos grises.
◦ El primer día.
Cada uno de los chicos de ojos grises ve a un chico de ojos grises y a un chico de ojos
negros. Así, no pueden decidir si ellos tienen los ojos grises o no. Al dar las siete de la
tarde, nadie le anuncia su color de ojos a Caronte.
◦ El segundo día.
El segundo día todos los chicos han recibido información extra: nadie anunció su color
de ojos el día anterior. Esto significa que ninguno de los chicos de ojos grises estaba
seguro de su propio color de ojos, entonces cada uno de los chicos de ojos grises podía
ver a uno o más chicos de ojos grises.
Como cada uno de los chicos de ojos grises ve exactamente a un chico de ojos grises, el
segundo día ambos pueden decidir su color de ojos y se lo anuncian a Caronte a las siete
de la tarde.
94 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
◦ El tercer día.
Este día el muchacho restante deja la isla pues sabe, del día anterior, que los dos chicos
abandonaron la isla porque eran los únicos que tenían ojos grises.
• Hay 3 muchachos con ojos grises.
◦ El primer día. Cada uno de los chicos ve dos chicos de ojos grises y entonces ninguno
de ellos puede decidir su color de ojos.
◦ El segundo día. Este día todos los chicos ya tienen información extra: nadie se anunció
el día anterior. Este hecho, sin embargo, por el momento no ayuda a los muchachos a
decidir pues era de esperarse que ninguno pudiera adivinar su color de ojos, ya que al
menos había dos chicos de ojos grises.
◦ El tercer día. Este día todos los chicos recibieron, de nuevo, información extra: nadie
se anunció el día anterior. Ahora ese nuevo dato sí será fundamental para decidir, ya
que cada chico ve exactamente a otros dos chicos de ojos grises y, como ellos no se
anunciaron el día anterior, sabe que debe haber un chico más de ojos grises: él mismo.
A las siete de la tarde de este día todos los chicos abandonan la isla.
Conclusión: en este caso, como en los dos anteriores, también ocurrió que todos los mucha-
chos lograron abandonar la isla.
A continuación, mostramos los complejos simpliciales que representan el caso n = 3 y las
correspondientes gráficas elaboradas a partir de la descripción hecha en la Stanford Encyclo-
pedia of Philosophy.
Para el caso de tres chicos, imaginemos que el primero trae puesta una chamarra anaranjada,
el segundo una chamarra amarilla y el tercero una chamarra azul.
Notemos que ahora las etiquetas tienen tres posiciones: la primera posición representa el
estado del primer muchacho (el de la chamarra anaranjada); la segunda posición, el estado
del segundo muchacho (el de la chamarra amarilla); y la tercera posición, el estado del tercer
muchacho (el de la chamarra azul). Nuevamente utilizamos la letra n para indicar que el
muchacho correspondiente tiene ojos negros, la letra g para indicar que tiene ojos grises y el
símbolo ⊥ para indicar que el muchacho está indeciso acerca de su color de ojos.
• El primer día, antes de haber escuchado la frase que dijo Hades, el complejo simplicial
correspondiente se encuentra completo y la gráfica también.
Una observación importante es que en este caso el complejo simplicial ha aumentado
su dimensión en 1 respecto al caso n = 2 y ahora los mundos posibles están represen-
tados por simplejos de dimensión 2 en lugar de por simplejos de dimensión 1.
5.1. PRIMERA PREGUNTA 95
n⊥ g
gn⊥
ng⊥
g⊥n
⊥ng ⊥ gn
⊥nn
⊥ g g
g⊥ g g g⊥
n⊥nnn⊥
ggn
ggg
ngn
ngg
gnn
gng
nnn
nng
1
1
1
1
2 2
2 2
3 3
3 3
• También el primer día, pero una vez que los muchachos recibieron el anuncio de Hades y
saben que al menos uno de ellos tiene los ojos grises, podemos descartar el mundo en donde
los tres tienen los ojos negros, lo que se refleja en quitar un “triángulo” de nuestro complejo
simplicial, así como en quitar un vértice junto con sus aristas correspondientes en la gráfica.
n⊥ g
gn⊥
ng⊥
g⊥n
⊥ng ⊥ gn
⊥nn
⊥ g g
g⊥ g g g⊥
n⊥nnn⊥
ggn
ggg
ngn
ngg
gnn
gng nng
1
1
1
2
2 2
3 3
3
• El segundo día, cuando los muchachos ya se dieron cuenta de que el día anterior nadie
abandonó la isla, saben que hay más de uno de ellos que tiene los ojos grises. Para repre-
sentar sólo los mundos posibles en que más de un muchacho tiene los ojos grises, quitamos
otros tres simplejos de dimensión 2 de nuestro complejo simplicial o, equivalentemente, tres
vértices y sus aristas correspondientes en la gráfica.
96 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
n⊥ g
gn⊥
ng⊥
g⊥n
⊥ng ⊥ gn
⊥ g g
g⊥ g g g⊥
ggn
ggg ngg
gng
1
2
3
• El tercer día, si nadie anunció el día anterior su color de ojos, sólo queda la posibilidad de
que los tres muchachos tengan los ojos grises. Esto se representa simplemente con un trián-
gulo en el complejo simplicial, pues es el único mundo posible. En la gráfica, se representa
con un solo vértice.
⊥ g g
g⊥ g g g⊥
ggg
Podemos darnos cuenta de que por cada simplejo de la dimensión más alta en el complejo
simplicial, hay un vértice en la gráfica. Además, por cada dos simplejos que comparten un
vértice, hay una arista en la gráfica. Luego, se podría decir que la gráfica es el dual del
complejo simplicial o viceversa, que el complejo simplicial es el dual de la gráfica.
En este punto, nos gustaría hacer una observación relevante que quizá la lectora o lector ya habrá podido
adivinar: este problema es análogo al problema de las niñas enlodadas mencionado en la introducción del
presente trabajo. Para resolver este acertijo, nos da lo mismo hablar de niñas divirtiéndose en el lodo que
de muchachos angustiados en una isla tétrica: el razonamiento que ellos realizan para averiguar en qué
estado se encuentran es el mismo.
Recordemos que la cadena de argumentos que hemos dado para uno, dos y tres muchachos, se puede
generalizar inductivamente para cualquier número finito de muchachos que lleguen a la isla.
5.2. SEGUNDA PREGUNTA 97
5.2. Segunda pregunta
2. Suponiendo que son nueve los que tienen ojos negros (y el resto tiene ojos grises) y
suponiendo que la afirmación de Hades es: “Me alegra que al menos uno de ustedes tenga
ojos negros”, ¿cuántas personas pueden partir y en cuánto tiempo? En general, si hay n
chicos con ojos grises y m con ojos negros, ¿cuántos pueden partir y en cuánto tiempo?
5.2.1. Caso particular
Consideremos primero un caso en el que hay en total nueve muchachos en la isla. Al resolver el problema
para nueve muchachos en total, también se resuelve para los casos en que haya más de nueve, pues una
vez que los chicos de ojos negros saben su color de ojos y se van de la isla, los muchachos de ojos grises
también pueden intuir cuál es su color de ojos, sea cual sea el número de muchachos de ojos grises.
Comencemos entonces por considerarm+n = 9 el número total de muchachos en la isla. El análisis que
haremos a continuación es análogo al que se realizó en la pregunta anterior, empero, ahora no dibujaremos
los simplejos, porque son demasiado grandes. De la primera pregunta sabemos lo siguiente:
n dimensión del complejo simplicial mundos posibles
2 1 4
3 2 8
Ahora, para m + n = 9, un complejo simplicial de dimensión máxima se formará a partir de 9 puntos
que serán sus vértices, por lo que este tendrá dimensión 8. Como en la respuesta a la pregunta anterior, a
dicho complejo simplicial le corresponde una gráfica, la cual puede construirse de la siguiente manera:
Pensemos en el hipercubo [0, 1]9, donde [0, 1] ⊂ R. De dicho conjunto, sólo nos quedaremos con los
vértices y las aristas. El número de vértices de la gráfica, que es también el número total de mundos
posibles, estará dado por
2 · 2 · · · 2︸ ︷︷ ︸
9 veces
= 2
9 = 512 o bien O9
2
que es el número de ordenaciones posibles (con repetición) de 2 objetos en muestras de tamaño 9. Son
sólo 2 objetos porque únicamente consideramos dos posibles colores de ojos.
La frase con la que Hades recibió a los muchachos, fue:
“Me alegra que al menos uno de ustedes tenga ojos negros”
Con esto se descarta un mundo posible, donde ninguno de los muchachos tiene ojos negros. En la presente
sección, representaremos los mundos posibles con palabras como las que utilizamos en los vértices de
las gráficas de la pregunta anterior: cada posición de la palabra corresponde a uno de los niños, la letra
n significa que el niño en la posición actual tiene los ojos negros y la letra g significa que tiene los ojos
grises. Así, el primer mundo que se descarta es:
98 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
ggggggggg
y quedan solamente 511 mundos posibles. Descartar tal mundo en la gráfica es eliminar el vértice que tiene
la etiqueta ggggggggg junto con todas las aristas que inciden en él. Por lo tanto, en la gráfica resultante
de hacer la operación mencionada, quedan vértices en los que inciden menos de nueve aristas (al inicio,
en cada vértice incidían exactamente nueve aristas). Estos vértices con menor número de incidencias
representan los mundos en los que los muchachos ya pueden conocer su color de ojos. En tales mundos
hay un sólo muchacho de ojos negros y contamos esos mundos de la siguente manera:
(
9
1
)
= 9,
o bien, podemos enlistarlos fácilmente de esta forma:
ngggggggg
gnggggggg
ggngggggg
gggnggggg
ggggngggg
gggggnggg
ggggggngg
gggggggng
ggggggggn
En cada una de estas nueve posibilidades, el muchacho de ojos negros se va el primer día y los muchachos
que tienen ojos grises, parten al día siguiente. Tardan en total dos días en partir todos los muchachos.
Al continuar con el razonamiento anterior y eliminar estos nueve mundos junto con sus aristas incidentes
en la gráfica, podemos darnos cuenta de que el número de mundos en los que hay exactamente dos
muchachos que tienen ojos negros es:
(
9
2
)
= 36,
que se corresponden con 36 vértices en la gráfica en los que inciden menos de nueve aristas. En este caso,
los muchachos de ojos negros se irían de la isla hasta el segundo día, ya que se darían cuenta de que el
primer día nadie partió. Al tercer día dejarán la isla todos los muchachos de ojos grises. En consecuencia,
en estos 36 mundos tardan tres días la totalidad de los muchachos para lograr abandonar la isla.
En la siguiente tabla escribimos el número de mundos para cada cantidad posible de muchachos de ojos
negros, así como los días que tardan en dejar la isla.
5.2. SEGUNDA PREGUNTA 99
muchachos de ojos negros mundos posibles
día en que aban-
donan la isla los
muchachos de
ojos negros
días que tardan en
abandonar la isla
todos los mucha-
chos
0
(
9
0
)
= 1 no aplica no aplica
1
(
9
1
)
= 9 1 2
2
(
9
2
)
= 36 2 3
3
(
9
3
)
= 84 3 4
4
(
9
4
)
= 126 4 5
5
(
9
5
)
= 126 5 6
6
(
9
6
)
= 84 6 7
7
(
9
7
)
= 36 7 8
8
(
9
8
)
= 9 8 9
9
(
9
9
)
= 1 9 no aplica
Finalmente, aunque nuestro análisis fue para exactamente 9 muchachos, podermos deducir que si hubie-
ranmmuchachos con ojos negros y nmuchachos con ojos grises, entonces las combinaciones de la tabla
anterior no serían las mismas, sin embargo, el número de días en que los muchachos abandonan la isla
sería tal y como se muestra en la tabla, salvo que para m = 9 y algún n fijo, en el último renglón sí sa-
bríamos el número de días en que la totalidad de los muchachos abandonan la isla, que son precisamente
10 días. Esto responde a la primer interrogante.
100 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
5.2.2. Caso general
En seguida responderemos la pregunta en general, es decir,
“Si hay n chicos con ojos grises ym con ojos negros, ¿cuántos pueden partir y en
cuánto tiempo?”.
En vista de que la frase de Hades fue:
“Me alegra que al menos uno de ustedes tenga ojos negros”,
lo más importante para resolver la pregunta será la cantidad total de muchachos de ojos negros.
Como haym chicos con ojos negros y n con ojos grises, la cantidad total de muchachos esm+ n.
El número total de mundos posibles está dado por:
2 · 2 · · · 2︸ ︷︷ ︸
(m+n) veces
= 2
m+n o bien Om+n
2
.
es decir, la gráfica que corresponde a este problema tendrá en total 2m+n vértices.
En seguida, el primer mundo que podemos descartar es:
ggggg . . . g︸ ︷︷ ︸
(m+n) veces
ya que en tal mundo no hay ningún muchacho con ojos negros.
Los vértices que ahora tienen menos de m + n aristas incidentes son
(
m+n
1
)
= m + n y son los que
corresponden a los mundos en los que sólo hay un muchacho con ojos negros. En estos mundos, el
muchacho de ojos negros se va el primer día y los muchachos restantes se van el segundo día.
Los mundos posibles en caso de que haya dos muchachos con ojos negros y los demás tengan ojos grises
son
(
m+n
2
)
y corresponden a los vértices que inciden con menos dem+n aristas que quedan en la gráfica
después de quitar los
(
m+n
1
)
vértices del paso anterior. En este caso, los muchachos de ojos negros tardan
dos días en abandonar la isla, de forma que la totalidad de los muchachos abandona la isla en tres días.
Así sucesivamente, podemos inferir que cuando hay m muchachos de ojos negros en la isla y los n
restantes tienen ojos grises, los muchachos de ojos negros abandonarán la isla enm días y los muchachos
de ojos grises partirán al día siguiente. Por lo tanto, cuando hay m + n muchachos en total, m de ojos
negros y n de ojos grises, ellos tardan en marcharsem+ 1 días.
5.3. TERCERA PREGUNTA 101
5.3. Tercera pregunta
3. Supongamos que hay n con ojos grises, m con ojos negros y que la afirmación de
Hades es: “me alegra ver que hay más de un color de ojos” ¿Cuántos días tardan en dejar
todos la isla?
En caso de que sólo un muchacho llegara a la isla, no cabría la posibilidad de que lo dicho por Hades
fuera cierto. Consecuentemente, comenzaremos nuestro análisis a partir del casom+ n = 2.
Primer caso:m+ n = 2
Param+n = 2, la totalidad de los mundos posibles está formada por los cuatro mundos que se muestran
en la siguiente gráfica:
nn
ng gn
gg
2 1
1 2
Una vez dicha la frase
“Me alegra ver que hay más de un color de ojos”,
descartamos dos posibilidades, a saber, los mundos nn y gg, ya que en ellos hay un solo color de ojos.
Así, la gráfica se “recorta” y queda de la siguiente manera:
ng gn
En ambos mundos los muchachos ya pueden tomar una decisión. Ellos abandonan la isla desde el primer
día. ¡Enhorabuena!
Segundo caso:m+ n = 3
Para m+ n = 3 existen los siguientes mundos posibles (los que etiquetan los vértices de la gráfica) que
en total son ocho:
102 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
ggn
ggg
ngn
ngg
gnn
gng
nnn
nng
1
1
1
1
2 2
2 2
3 3
3 3
Cuando los muchachos han recibido la información de Hades de que hay más de un color de ojos, pueden
descartar dos mundos: nnn y ggg. Para nosotros esto equivale a eliminar los dos vértices correspon-
dientes en la gráfica, junto con las aristas que los conectan a otros vértices. La gráfica resultante es la
siguiente:
ggn ngn
ngg
gnn
gng nng
1
1
2
2
3
3
Como en el caso anterior, en estos seis mundos ya es posible para los muchachos tomar una decisión:
basta con que uno de ellos vea que hay dos con el mismo color de ojos, para que concluya que él mismo
debe tener un color de ojos distinto.
En este caso, el primer día únicamente se va un muchacho. Al día siguiente se van los dos muchachos
restantes. Por lo tanto, transcurren en total dos días para que todos hayan abandonado la isla.
Tercer caso:m+ n = 4
Para el casom+ n = 4, las posibilidades están representadas por la siguiente gráfica:
5.3. TERCERA PREGUNTA 103
nnnn
ngnn
nggn
nngn
gnnn
ggnn
gggn
gngn
nnng
ngng
nggg
nngg
gnng
ggng
gggg
gngg
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
¨
Al decir Hades la frase
“Me alegra ver que hay más de un color de ojos”
podemos descartar los mundos gggg y nnnn ya que en ellos hay sólo un color de ojos. La gráfica
quedaría entonces de la siguiente manera:
104 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
ngnn
nggn
nngn
gnnn
ggnn
gggn
gngn
nnng
ngng
nggg
nngg
gnng
ggng
gngg
1
1
1
1
1
1
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
¨
Los mundos en que la situación se resolvería más rápido, son los mundos en los cuales hay un chico de
ojos negros que ve a todos los demás de ojos grises, o viceversa, los mundos en los cuales hay un chico
de ojos grises que ve a todos los demás de ojos negros. Al descartar estos mundos, la gráfica queda como
se muestra a continuación:
5.3. TERCERA PREGUNTA 105
nggn
ggnn
gngn
ngng
nngg
gnng
¨
En estos últimos mundos, todos los muchachos sabrían su situación hasta el segundo día, pues cada chico
vería a tres chicos, dos de ellos con un color de ojos y el tercero con otro color de ojos. Al observar que
el tercero no abandonó la isla el primer día, sabrá que él tiene el mismo color de ojos que el tercero, y
podrá abandonar la isla al segundo día.
Podemos hacer un resumen de lo que hemos averiguado para los casos de 2, 3 y 4 muchachos en total
como se muestra en la siguiente tabla. De la misma manera, incluimos también los casos de 5, 6 y 7
muchachos en total (aunque para este último caso ya no consideramos necesario hacer explícita la lista
de palabras que representan los mundos posibles, pues se puede construir de manera análoga a como se
hace en los casos anteriores).
106 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
Número
total de
mucha-
chos
(m+n).
Número
de mun-
dos
posibles.
Número de
mundos que
se descartan
con la frase de
Hades.
Lista de mundos por día en
que se descartan (sin tomar
en cuenta los que ya se des-
cartaron con la afirmación
de Hades).
Día en
que una
parte de
los mu-
chachos
podría
saber su
color de
ojos.
Número de mun-
dos en los que
esos muchachos
podrían saber su
color de ojos.
2 4 = 22 2 =
(
2
0
)
+
(
2
2
)
ng gn Día 1 2 =
(
2
1
)
3 8 = 23 2 =
(
3
0
)
+
(
3
3
)
ngg gng ggn gnn ngn
nng
Día 1 6 =
(
3
1
)
+
(
3
2
)
4 16 = 24 2 =
(
4
0
)
+
(
4
4
) nggg gngg ggng gggn
gnnn ngnn nngn nnng
Día 1 8 =
(
4
1
)
+
(
4
3
)
ggnn nggn nngg ngng
gnng gngn
Día 2 6 =
(
4
2
)
5 32 = 25 2 =
(
5
0
)
+
(
5
5
) ngggg gnggg ggngg
gggng ggggn gnnnn
ngnnn nngnn nnngn
nnnng
Día 1 10 =
(
5
1
)
+
(
5
4
)
ggnnn nnggg gngnn
ngngg gnngn nggng
gnnng ngggn nggnn
gnngg ngngn gngng
ngnng gnggn nnggn
ggnng nngng ggngn
nnngg gggnn
Día 2 20 =
(
5
2
)
+
(
5
3
)
5.3. TERCERA PREGUNTA 107
6 64 = 26 2 =
(
6
0
)
+
(
6
6
) nggggg gnnnnn
gngggg ngnnnn
ggnggg nngnnn
gggngg nnngnn
ggggng nnnngn
gggggn nnnnng
Día 1 12 =
(
6
1
)
+
(
6
5
)
ggnnnn nngggg
ggggnn gngnnn
ngnggg nggggn
gnngnn nggngg
gngggn gnnngn
ngggng ggnggn
nggnnn gnnggg
gggngn ngngnn
gngngg gnnnng
ngnngn gnggng
ngnnng nnggnn
ggnngg nngnng
nngngn ggngng
nnngng nnnggn
gggnng nnnngg
Día 2 30 =
(
6
2
)
+
(
6
4
)
ggnnng nngggn
gngnng ngnggn
gnngng nggngn
gnnngg ngggnn
nggnng gnnggn
ngngng gngngn
ngnngg gnggnn
nnggng ggnngn
nngngg ggngnn
nnnggg gggnnn
Día 3 20 =
(
6
3
)
Lo que salta la vista al observar con detenimiento la tabla anterior, es que el número de días en que dejan
la isla la totalidad de los muchachos depende del número mínimo entre el número de muchachos de ojos
negros y el número de muchachos de ojos grises. Es decir, en general, si el número total de muchachos
de un mundo dado es m + n donde m es el número de muchachos de ojos negros y n es el número de
muchachos de ojos grises entonces el número de días en que se van de la isla todos los muchachos de ese
mundo es:
mín(m,n) + 1.
108 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
5.4. Cuarta pregunta
4. Supongamos que despiertan en la isla de los muertos y ahora sus ojos pueden ser
grises, negros o amarillos. La afirmación de Hades es: “Me alegra que al menos uno de
ustedes tenga ojos grises”. ¿Pueden partir todos los muchachos? ¿Cuántos pueden partir y
en cuánto tiempo?
Para comenzar, se plantea la pregunta de cómo representamos los mundos posibles y las visiones com-
patibles de cada uno de los muchachos, puesto que antes el problema se planteaba únicamente con dos
posibilidades para los colores de ojos mas ahora son tres colores de ojos distintos.
A continuación, analizaremos algunos casos sencillos:
Primer caso: Hay dos muchachos en total.
Antes que nada, se nos presentan dos alternativas: una es representar los mundos posibles con aristas
(como en el caso de los simplejos en la primera pregunta) y otra es hacerlo con vértices (como en las
gráficas de las preguntas segunda y tercera). Sin embargo, dadas las condiciones de esta cuarta pregunta,
ambas representaciones resultarán ser ahora complejos simpliciales.
Con el fin de construir nuestros complejos simpliciales, observemos que en el caso de dos muchachos hay
un total de O2
3
= 32 = 9 mundos posibles, que es el número de ordenaciones posibles (con repetición)
de 3 objetos en muestras de tamaño 2. Así, el complejo simplicial de la izquierda consta de nueve aristas;
el de la derecha, de nueve vértices.
⊥ g g ⊥
⊥ a
a ⊥⊥ n
n ⊥
an
a
a
g
a
gg
n
g
n
n
g
n a
g
na
ng
gn
gg
ag
an
ga
aann
na
Cada triángulo en el complejo simplicial de la derecha representa una visión compatible: los triángulos
amarillos representan los mundos compatibles con la visión del segundo muchacho y los verdes, los
mundos compatibles con la visión del primer muchacho. Por otra parte, en el complejo simplicial de la
izquierda, los mundos compatibles con la visión de los muchachos de un vértice dado son las aristas que
inciden en dicho vértice.
5.4. CUARTA PREGUNTA 109
Dado que la frase dicha por Hades fue:
“Me alegra que al menos uno de ustedes tenga ojos grises”,
los mundos en los cuales ningún muchacho tiene los ojos grises serán descartados:
⊥ g g ⊥
⊥ a
a ⊥⊥ n
n ⊥
g
a
gg
n
g
g
n a
g
(k)
ng
gn
gg
ag
ga
(l)
Figura 5.1
Así, nos quedamos con sólo cinco mundos restantes. En estos, encontramos dos escenarios posibles: que
se vaya un muchacho el primer día o que no se vaya nadie el primer día. Vamos a analizar cada una de
estas situaciones.
• Un muchacho dejó la isla el primer día.
Al ser dos muchachos en total, esto sólo pudo haber pasado en el caso de que el muchacho que
partió viera que su compañero no tenía los ojos grises. De esta manera, pudo haber concluido que
él mismo tenía los ojos grises y marcharse.
¿En cuáles mundos, de los cinco que quedaron al haber descartado los que no coincidían con la
sentencia de Hades, puede ocurrir que haya un muchacho de ojos grises y otro que no tenga ojos
grises?
Esto ocurre en los mundos ng, gn, ag y ga, por lo que descartaremos de nuestros simplejos el
mundo gg:
⊥ g g ⊥
⊥ a
a ⊥⊥ n
n ⊥
g
a
n
g
g
n a
g
ng
gn
ag
ga
110 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
Cabe mencionar que en los mundos ng y ag fue el segundo muchacho quien partió de la isla y en
los mundos gn y ga fue el primer muchacho quien abandonó la isla.
De esta manera, en el complejo simplicial de la izquierda, el vértice azul etiquetado con ⊥ g
representa la incertidumbre del primer muchacho, pues no sabe si está en el mundo ng o ag y
no tiene manera de descubrirlo aunque su compañero de ojos grises se haya marchado. Es decir, a
este pobre muchacho no le queda más que intentar adivinar si sus ojos son negros o amarillos y así
intentar marcharse con un golpe de suerte.
Análogamente, en el mismo complejo simplicial de la izquierda, el vértice anaranjado etiquetado
con g ⊥ representa la incertidumbre del segundo muchacho, que no sabe si está en el mundo gn o
en el ga y no podrá saberlo con certeza.
Por otro lado, el complejo simplicial de la derecha representa la misma situación, sólo que en el
caso de este complejo simplicial, cada vértice es un mundo posible. La arista (ng, ag) representa
la incertidumbre infranqueable del primer muchacho y la arista (gn, ga), la del segundo (en los
mundos correspondientes).
• Ningún muchacho dejó la isla el primer día.
En este caso, ambos muchachos saben que su compañero −de ojos grises− no pudo decidir si tenía
los ojos grises o no. Esto sólo pudo haber pasado porque el compañero vio que el primero tenía los
ojos grises. Es decir, ¡ambos tienen los ojos grises! Por lo tanto, se encuentran en el mundo gg, lo
cual es claro para los dos al segundo día, cuando pueden por fin marcharse.
Los siguientes simplejos, que corresponden a este caso, resultan de descartar las visiones n ⊥,a ⊥,
⊥ n y ⊥ a de la Figura 5.1k; y los mundos ng, ag, gn y ga de la Figura 5.1l, respectivamente.
⊥ g g ⊥
gg gg
Segundo caso: Hay tres muchachos en total.
Nuevamente, en este caso hay dos maneras distintas de representar los mundos posibles.
Tomemos en cuenta que el número total de mundos posibles en el caso de tres muchachos es O3
3
= 33 =
27, que es el número de ordenaciones posibles (con repetición) de 3 objetos en muestras de tamaño 3. Por
consiguiente, la representación gráfica se vuelve más complicada, pero vamos a dar un esbozo de cómo
se pueden construir los complejos simpliciales.
Comencemos por el complejo simplicial cuyos vértices son las visiones de cada tercia de muchachos y
donde los objetos que inciden en cada vértice son los mundos compatibles con tal vértice. Para el caso de
tres muchachos, los objetos que inciden en cada vértice son triángulos, a diferencia de lo que pasaba en
el caso de dos muchachos, donde eran aristas.
En la siguiente figura, representamos una versión “aplanada” del complejo simplicial que tiene como
vértices las visiones de los muchachos. En este caso, decidimos indicar con distintos colores las inciden-
cias de algunos de los triángulos, de manera que cada tres círculos del mismo color y la misma etiqueta
corresponden, en realidad, a un sólo vértice del complejo simplicial.
5.4. CUARTA PREGUNTA 111
Como se puede observar en la figura, para el vértice g ⊥ g, que representa la visión del segundo mucha-
cho cuando el primero y el tercero tienen los ojos grises, los mundos compatibles son: ggg, gng y gag.
Además, las visiones compatibles son: ⊥ gg, gg ⊥,ga ⊥, ⊥ ag, gn ⊥ y ⊥ ng.
Ahora describiremos el complejo simplicial cuyos vértices son los mundos posibles. En este complejo
simplicial cada triángulo está formado por tres vértices que son los mundos compatibles con la visión de
uno de los tres muchachos, como ocurría también en el caso de dos muchachos. Los triángulos etiquetados
con 1 se forman con tres mundos (vértices) compatibles con la visión del primer muchacho, los triángulos
etiquetados con 2 se forman con tres mundos (vértices) compatibles con la visión del segundo muchacho y
los triángulos etiquetados con 3 se forman con tres mundos (vértices) compatibles con la visión del tercer
muchacho. Observemos que en este caso la figura no es exhaustiva, ya que faltan algunos triángulos de
los que sólo se han dibujado sus aristas, para no volver complicada y difusa la imagen.
112 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
Después de que Hades diga su frase:
“Me alegra que al menos uno de ustedes tenga ojos grises”,
los complejos simpliciales quedan de la siguiente manera, pues se descartan los 8 mundos en los que
ningún muchacho tiene los ojos grises:
5.4. CUARTA PREGUNTA 113
En el primer complejo simplicial, hemos asignado el color anaranjado a los triángulos que corresponden
a los mundos donde sólo un muchacho tiene los ojos grises, el color rojo a los mundos donde dos mu-
chachos tienen los ojos grises y finalmente un color guinda o vino al triángulo que representa el mundo
donde los tres muchachos tienen los ojos grises.
• Lo que pasa el primer día.
La asignación de los colores mencionados anteriormente se hizo de esa manera porque los mundos
de los que se va uno de los muchachos el primer día son precisamente aquellos mundos en los que
sólo hay un muchacho de ojos grises, que son 12 en total. El muchacho que se va el primer día es
114 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
precisamente el que tiene los ojos grises, ya que observa que sus compañeros no tienen los ojos
grises y debe existir alguien que sí los tenga grises, por lo que puede saber que él los tiene grises.
La situación de los dos compañeros restantes no es tan afortunada, pues ninguno de ellos puede
saber si sus ojos son negros (n) o amarillos (a), por lo que sólo les queda intentar adivinarlo.
• Lo que pasa el segundo día.
En los mundos de donde ya partió un muchacho el primer día, los otros dos restantes no están
seguros de su color de ojos.
Por otra parte, en los mundos donde hay exactamente dos muchachos que tienen los ojos grises,
que son 6 en total, ellos ya pueden adivinar que tienen los ojos grises, pues saben que uno de sus
compañeros tiene los ojos grises y el otro no. Además, saben que su compañero de ojos grises no
se fue el primer día. Estos dos muchachos dejan la isla el segundo día.
De nuevo, el muchacho que se queda en la isla no tiene manera de averiguar si sus ojos son negros
o amarillos, por lo que corre el riesgo de no adivinarlo y quedarse ahí para siempre.
• Lo que pasa el tercer día.
Hasta ahora, nadie se había ido del mundo donde los tres muchachos tienen los ojos grises. Sin
embargo, para el tercer día, en el mundo donde los tres muchachos tienen los ojos grises, ellos se
dan cuenta de que ninguno de sus dos compañeros se fue en los dos días anteriores. Por lo tanto,
los tres concluyen que tienen los ojos grises y, aliviados, dejan la isla juntos el tercer día.
Con los datos que hemos obtenido de los dos casos anteriores, podemos deducir que los muchachos que
siempre pueden abandonar la isla son quienes tienen los ojos grises, pero además ellos son los únicos que
pueden salir de ahí, pues los muchachos que tienen los ojos negros o amarillos nunca pueden averiguar
su color de ojos con la información que reciben.
5.5. Quinta pregunta
5. En el mismo supuesto de la pregunta anterior , si una vez que se marchan los mu-
chachos de ojos grises, Hades afirma que: “aún hay colores distintos”, ¿pueden marcharse
todos? ¿En cuánto tiempo?
En esta situación, al suponer que se marchan todos los muchachos de ojos grises, en la isla sólo quedan
muchachos con dos colores de ojos: amarillos y negros. Por lo tanto, esta pregunta se puede reducir al
caso de la tercera pregunta, en la que también hay sólo dos colores de ojos posibles y Hades afirma que
"hay más de un color de ojos".
Recordemos que en la situación de la tercera pregunta todos los muchachos logran partir de la isla.
El número de días en que lograrían irse de la isla los muchachos de ojos negros y los muchachos de ojos
amarillos es:
min(m,k) + 1
dondem es el número de muchachos de ojos negros y k es el número de muchachos de ojos amarillos.
5.6. SEXTA PREGUNTA 115
5.6. Sexta pregunta
6. En el mismo supuesto de tres posibles colores distintos, si la afirmación de Hades en
un comienzo es: “Me alegra tener en la isla tanto ojos grises como ojos amarillos”, ¿pueden
marcharse todos? ¿En cuánto tiempo?
En este caso comenzaremos por un ejemplo sencillo, para el caso de siete muchachos en total, pero ya
sin hacer los dibujos de los complejos simpliciales. El ejemplo que mostraremos ahora lo retomaremos
también en las preguntas séptima y octava.
Para comenzar, calculamos el total de mundos posibles cuando aún no sabemos lo que dijo Hades. Recor-
demos que hay siete muchachos en la isla con tres posibles colores de ojos. El total de mundos posibles
será el número de ordenaciones posibles (con repetición) de 3 objetos en muestras de tamaño 7, es decir:
O7
3
= 3
7 = 2, 187.
A continuación, para facilitar el análisis, hacemos una tabla con las distintas particiones posibles de
acuerdo al color de ojos de los muchachos. Las particiones están escritas de la siguiente manera: cuando
hay un sólo número y este es 7, significa que los siete muchachos tienen el mismo color de ojos; en
caso de que haya dos números separados con una barra |, significa que hay en total dos colores de ojos
distintos en la isla (por ejemplo, en la partición 3|4 hay tres muchachos con un color de ojos y cuatro con
otro color de ojos); para el caso en que hay tres números separados con dos barras, significa que hay en
total tres colores de ojos distintos en la isla (en la partición 1|3|3, verbi gratia, hay un muchacho con un
color de ojos, tres muchachos con un segundo color de ojos y otros tres muchachos con un tercer color
de ojos).
Particiones
posibles.
Posibles formas de colorear
las particiones.
Total de mun-
dos correspon-
dientes a esta
partición.
7
(
7
0
)
∗ 3 = 1 ∗ 3 3
1|6
(
7
1
)
∗ 6 = 7 ∗ 6 42
2|5
(
7
2
)
∗ 6 = 21 ∗ 6 126
3|4
(
7
3
)
∗ 6 = 35 ∗ 6 210
1|1|5
(
7
1,1,5
)
∗ 3 = 42 ∗ 3 126
1|2|4
(
7
1,2,4
)
∗ 6 = 105 ∗ 6 630
1|3|3
(
7
1,3,3
)
∗ 3 = 140 ∗ 3 420
2|2|3
(
7
2,2,3
)
∗ 3 = 210 ∗ 3 630
SUMA 2, 187
De estas particiones eliminaremos la primera, ya que Hades afirmó que hay ojos grises y amarillos, lo
116 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
que nos deja con al menos dos posibles colores de ojos distintos en la isla.
Ahora bien, aunque hay por lo menos dos colores posibles, también sabemos exactamente cuáles son
esos colores: grises y amarillos. Entonces para los mundos en los que sólo hay dos colores de ojos, estos
únicamente pueden ser grises o amarillos, lo que reduce las opciones de coloreado para las particiones:
1|6, 2|5 y 3|4.
Así, nuestros mundos posibles se reducen a los que enumeramos en la siguiente tabla:
Particiones
posibles.
Posibles formas de colorear
las particiones.
Total de mun-
dos correspon-
dientes a esta
partición.
1|6
(
7
1
)
∗ 2 = 7 ∗ 2 14
2|5
(
7
2
)
∗ 2 = 21 ∗ 2 42
3|4
(
7
3
)
∗ 2 = 35 ∗ 2 70
1|1|5
(
7
1,1,5
)
∗ 3 = 42 ∗ 3 126
1|2|4
(
7
1,2,4
)
∗ 6 = 105 ∗ 6 630
1|3|3
(
7
1,3,3
)
∗ 3 = 140 ∗ 3 420
2|2|3
(
7
2,2,3
)
∗ 3 = 210 ∗ 3 630
SUMA 1, 932
De esta manera, podemos reducir nuestro trabajo a estudiar los siguientes siete casos:
1|6 2|5 3|4 1|1|5 1|2|4 1|3|3 2|2|3
A continuación, los examinamos uno por uno:
• 1|6
Hay dos casos posibles que son análogos: que un muchacho tenga los ojos grises y los seis restantes
los tengan amarillos o viceversa.
Supongamos, sin pérdida de generalidad, que uno los tiene grises y los seis restantes, amarillos.
El primer día, el muchacho de ojos grises ve que todos sus compañeros tienen ojos amarillos. Ese
mismo día él puede decidir su color de ojos y marcharse.
Sus compañeros, los muchachos de ojos amarillos, se van al día siguiente.
• 2|5
5.6. SEXTA PREGUNTA 117
Supongamos, sin pérdida de generalidad, que dos muchachos tienen los ojos grises y los otros cinco
tienen los ojos amarillos.
El primer día, cada uno de los muchachos de ojos grises ve a otro muchacho de ojos grises y a
cinco de ojos amarillos, por lo que no puede decidir su color de ojos.
El segundo día, cada uno de los muchachos de ojos grises sabe que su compañero de ojos grises
no partió el día anterior, por lo que deduce que él también debe tener los ojos grises. Los dos
muchachos de ojos grises se van ese mismo día de la isla.
Sus compañeros, los muchachos de ojos amarillos, se van al día siguiente.
• 3|4
Supongamos, sin pérdida de generalidad, que tres muchachos tienen los ojos grises y los otros
cuatro tienen los ojos amarillos.
Ocurre algo análogo a lo que pasó en los dos casos anteriores:
El primer día, cada uno de los muchachos de ojos grises ve a dos muchachos de ojos grises y cuatro
muchachos de ojos amarillos, por lo que no puede decidir su color de ojos.
El segundo día, cada uno de los muchachos de ojos grises ve que sus dos compañeros de ojos grises
no abandonaron la isla el día anterior, por lo que sabe que no están seguros de su color de ojos.
El tercer día, cada uno de los muchachos de ojos grises ve que sus dos compañeros de ojos grises
no abandonaron la isla el día anterior, por lo que sabe que están viendo a alguien más con ojos
grises y deduce que debe ser él mismo. Este día los tres muchachos de ojos grises se van de la isla.
Sus compañeros, los muchachos de ojos amarillos, se van al día siguiente.
• 1|1|5
•
Analicemos primero el caso en que un muchacho tiene ojos grises, un segundo muchacho
tiene ojos amarillos y los cinco muchachos restantes tienen ojos negros.
El primer día, el muchacho de ojos grises ve a un muchacho de ojos amarillos y otros cinco
de ojos negros. Como sabe, por lo dicho por Hades, que debe haber tanto ojos grises como
ojos amarillos en la isla, puede decidir que él tiene los ojos grises y se va ese mismo día de la
isla.
El muchacho de ojos amarillos sigue un razonamiento similar y también se va el primer día
de la isla.
Los cinco muchachos restantes se van al segundo día, pues ya pueden saber que tienen los
ojos negros, al haber notado que sus compañeros pudieron decidirse el día anterior.
118 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
•
Ahora analicemos el caso en que un muchacho tiene ojos grises, otro muchacho tiene ojos
negros y los cinco restantes tienen ojos amarillos.
El primer día, el muchacho de ojos grises ve que los otros no tienen ojos grises. Como sabe
que debe haber al menos un muchacho de ojos grises en la isla, decide que dicho muchacho
es él y parte ese mismo día de la isla.
Su compañero de ojos negros, lamentablemente, no puede saber su color de ojos el primer
día, pues no está seguro de si hay o no muchachos de ojos negros en la isla y aún cabría la
posibilidad de que sus ojos fueran amarillos.
El segundo día, cada uno de los muchachos de ojos amarillos saben que su compañero de ojos
grises se fue de la isla. Sin embargo, no pueden decidir si sus ojos son negros o amarillos,
pues cada uno de ellos ve a otros cuatro muchachos de ojos amarillos.
El tercero y cuarto día transcurren sin novedad, pues nadie deja la isla.
El quinto día cada muchacho de ojos amarillos se da cuenta de que ninguno de sus cuatro
compañeros de ojos amarillos abandonó la isla los días anteriores y, por lo tanto, concluye que
él debe tener los ojos amarillos. Este día los cinco muchachos de ojos amarillos abandonan la
isla.
El sexto día, el muchacho de ojos negros puede decidir su color de ojos y se va de la isla.
• 1|2|4
•
Supongamos que hay un muchacho de ojos grises, dos de ojos amarillos y cuatro de ojos
negros.
El primer día el muchacho de ojos grises se da cuenta de que ninguno de los otros muchachos
tiene los ojos grises y puede decidir su color de ojos. Por lo tanto, se va de la isla ese mismo
día.
El segundo día cada uno de los muchachos de ojos amarillos ve a otro muchacho de ojos
amarillos que no se fue el día anterior. Así, ambos muchachos de ojos amarillos deciden su
color de ojos este día y se van de la isla.
El tercer día los muchachos de ojos negros, al saber que todos sus compañeros ya se fueron,
pueden decidir su color de ojos y también logran marcharse.
Observemos que el caso en el que hay un muchacho de ojos amarillos, dos de ojos grises y
cuatro de ojos negros es análogo (basta intercambiar el color amarillo por el gris y viceversa).
•
Supongamos que hay un muchacho de ojos grises, dos de ojos negros y cuatro de ojos amari-
llos.
El primer día el muchacho de ojos grises se da cuenta de su color de ojos y abandona la isla.
Los días segundo y tercero nadie abandona la isla.
El cuarto día, cada uno de los muchachos de ojos amarillos ve a otros tres muchachos de ojos
amarillos que no se han ido de la isla y concluye que él mismo debe tener los ojos amarillos.
Este día abandonan la isla los cuatro muchachos de ojos amarillos.
El quinto día, los dos muchachos de ojos negros abandonan la isla.
5.6. SEXTA PREGUNTA 119
Observemos que el caso en el que hay un muchacho de ojos amarillos, dos de ojos negros y
cuatro de ojos grises, es análogo.
•
Supongamos que hay un muchacho de ojos negros, dos muchachos de ojos grises y cuatro
muchachos de ojos amarillos.
El primer día nadie está seguro de su color de ojos y por lo tanto nadie abandona la isla.
El segundo día, cada uno de los muchachos de ojos grises ve exactamente a otro de ojos grises
que no se ha ido de la isla y por lo tanto decide que también él mismo tiene los ojos grises.
Ambos muchachos abandonan la isla este día.
El tercer día nadie abandona la isla.
El cuarto día, cada muchacho de ojos amarillos ve a otros tres muchachos de ojos amarillos
que no se han ido de la isla y decide que entonces él mismo debe tener los ojos amarillos. Los
cuatro muchachos de ojos amarillos se van de la isla este día.
El quinto día se va de la isla el muchacho restante, quien tiene los ojos negros.
• 1|3|3
•
Supongamos que uno de los muchachos tiene los ojos negros, tres los tienen grises y los tres
restantes los tienen amarillos.
Los días primero y segundo nadie abandona la isla, pues nadie logra adivinar su color de ojos.
El tercer día, cada uno de los muchachos de ojos grises ve a otros dos muchachos de ojos
grises que no se han ido en los días anteriores y concluye que él también debe tener los ojos
grises. Este día se van de la isla todos los muchachos de ojos grises y también todos los
muchachos de ojos amarillos, pues el razonamiento que ellos tienen es análogo.
El cuarto día se va de la isla el muchacho de ojos negros.
•
Supongamos, sin pérdida de generalidad, que un muchacho tiene los ojos grises, tres los tienen
negros y tres los tienen amarillos.
El primer día se va de la isla el muchacho de ojos grises, pues no ve a nadie más que tenga
los ojos grises.
El segundo día nadie deja la isla.
El tercer día, cada uno de los muchachos de ojos amarillos ve a otros dos muchachos de
ojos amarillos que no se han ido de la isla, por lo que concluye que él también tiene los ojos
amarillos. Los tres muchachos de ojos amarillos dejan la isla este día.
El cuarto día, los tres muchachos de ojos negros abandonan la isla también, pues ya se han
ido todos los demás y sólo les resta un posible color de ojos.
Observemos que este caso es análogo al caso en que un muchacho tiene los ojos amarillos,
tres los tienen negros y tres los tienen grises.
• 2|2|3
120 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
•
Supongamos que dos muchachos tienen los ojos negros, dos los tienen grises y tres los tienen
amarillos.
El primer día nadie adivina su color de ojos ni deja la isla.
El segundo día cada uno de los muchachos de ojos grises ve exactamente a otro de ojos grises
que no se fue el día anterior y, por lo tanto, puede decidir su color de ojos. Este día se van los
dos muchachos de ojos grises.
El tercer día cada uno de los muchachos de ojos amarillos ve exactamente a dos muchachos
de ojos amarillos que no se fueron el día anterior y decide que él mismo debe tener los ojos
amarillos. Este día se van los tres muchachos de ojos amarillos.
El cuarto día, los dos muchachos de ojos negros también deciden su color de ojos y dejan la
isla.
Observemos que este caso es análogo al caso en que dos muchachos tienen los ojos negros,
dos los tienen amarillos y tres los tienen grises.
•
Supongamos que dos muchachos tienen los ojos grises, dos los tienen amarillos y tres los
tienen negros.
El primer día ningún muchacho adivina su color de ojos ni deja la isla.
El segundo día, cada uno de los muchachos de ojos grises ve exactamente a otro muchacho de
ojos grises que no se fue el día anterior y, por lo tanto, decide que él mismo debe tener los ojos
grises. Ambos muchachos de ojos grises abandonan la isla este día y tambén lo hacen ambos
muchachos de ojos amarillos, pues siguen un razonamiento análogo al de los muchachos de
ojos grises.
El tercer día los tres muchachos de ojos negros también dejan la isla, al ver que sus compa-
ñeros de ojos grises y amarillos se marcharon el día anterior.
Resumimos lo que hemos descrito hasta ahora en la siguiente tabla:
Número de muchachos que se van de la isla por día en que se van.
Primer día. Segundo día. Tercer día. Cuarto día. Quinto día. Sexto día.
1|6
1 muchacho
de ojos grises.
6 mucha-
chos de ojos
amarillos.
2|5
2 muchachos
de ojos grises.
5 mucha-
chos de ojos
amarillos.
3|4
5.6. SEXTA PREGUNTA 121
3 muchachos
de ojos grises.
4 mucha-
chos de ojos
amarillos.
1|1|5
1 muchacho
de ojos grises
y 1 de ojos
amarillos.
5 muchachos
de ojos negros.
1 muchacho
de ojos grises.
5 mucha-
chos de ojos
amarillos.
1 muchacho
de ojos negros.
1|2|4
1 muchacho
de ojos grises.
2 mucha-
chos de ojos
amarillos.
4 muchachos
de ojos negros.
1 muchacho
de ojos grises.
4 mucha-
chos de ojos
amarillos.
2 muchachos
de ojos negros.
2 muchachos
de ojos grises.
4 mucha-
chos de ojos
amarillos.
1 muchacho
de ojos negros.
1|3|3
3 muchachos
de ojos grises
y 3 de ojos
amarillos.
1 muchacho
de ojos negros.
1 muchacho
de ojos grises.
3 mucha-
chos de ojos
amarillos.
3 muchachos
de ojos negros.
2|2|3
2 muchachos
de ojos grises.
3 mucha-
chos de ojos
amarillos.
2 muchachos
de ojos negros.
122 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
2 muchachos
de ojos grises
y 2 de ojos
amarillos.
3 muchachos
de ojos negros.
Lo primero que podemos notar del análisis anterior es que en todos los casos, los muchachos logran
abandonar la isla.
En segundo lugar, observamos que primero dejan la isla los muchachos de ojos amarillos o grises y por
último se van los muchachos de ojos negros.
Podemos apreciar que, en el caso de que existan tres colores de ojos, el número total de días en que todos
los muchachos dejan la isla es:
máx(n, k) + 1
donde n es el número de muchachos de ojos grises y k es el número de muchachos de ojos amarillos.
Por otro lado, en caso de que sólo haya dos colores de ojos, el número total de días en que los muchachos
se van de la isla es:
mín(n, k) + 1
donde n y k son como antes.
5.7. Séptima pregunta
7. Aún hay tres posibles colores distintos. Si la afirmación de Hades en un comienzo es:
“Me alegra ver que hay más de un color de ojos”, ¿pueden marcharse todos? ¿En cuánto
tiempo?
Retomaremos el ejemplo para siete muchachos de la pregunta anterior. La afirmación de Hades
“Me alegra ver que hay más de un color de ojos”,
es equivalente a decir que hay al menos dos colores de ojos distintos.
En este caso, del total de mundos sólo podremos eliminar tres al saber lo que dijo Hades: aquellos en que
todos tienen los ojos negros, todos los tienen grises o todos los tienen amarillos.
Ahora bien, en este caso no hace falta hacer el análisis para cada una de las particiones anteriores puesto
que, en el mejor de los casos, un muchacho tendrá los ojos de un color y los otros seis de otro, empero,
ni aún así habrá alguien que pueda adivinar su propio color de ojos.
5.8. OCTAVA PREGUNTA 123
Tomemos, por ejemplo, el caso en que un muchacho tiene los ojos grises y los seis restantes tienen
los ojos amarillos.
En este caso, el muchacho de ojos grises ve que todos los demás tienen los ojos amarillos y con la
información que recibió de Hades, sabe que él debe tener los ojos ya sea grises o negros. Sin em-
bargo, nunca podrá decidir entre estas dos opciones, pues no recibirá información extra de ningún
tipo que pueda ayudarlo a estar seguro de su color de ojos.
En caso de que hubiera al menos dos muchachos con un color de ojos y los restantes con otro color de
ojos, seguiría siendo imposible decidir. Veamos un ejemplo:
Digamos que en la isla hay dos muchachos con ojos grises y cinco muchachos con ojos negros.
Cada uno de los muchachos de ojos grises sabrá que hay al menos dos colores de ojos distintos en
la isla: gris y negro. Esto no constituye ninguna información extra para él, que pueda sumarse a lo
que aseveró Hades para llevarlo a tomar una resolución. En otras palabras, lo que dijo Hades es lo
mismo que él está observando y eso no le da ninguna información sobre su color de ojos. Como
sus compañeros están exactamente en la misma situación, nadie podrá partir de la isla, a menos que
atine a su color de ojos por azar.
5.8. Octava pregunta
8. En el mismo caso de tres posibles colores distintos, si la afirmación de Hades fuera:
“Me alegra tener en la isla ojos grises, negros y amarillos”, ¿podrían marcharse todos? ¿En
cuánto tiempo?
Al tomar nuevamente el caso de siete muchachos en total y dada la afirmación de Hades, nuestros mundos
posibles se reducen a los que enumeramos en la siguiente tabla:
Particiones
posibles.
Posibles formas de colorear
las particiones.
Total de mun-
dos correspon-
dientes a esta
partición.
1|1|5
(
7
1,1,5
)
∗ 3 = 42 ∗ 3 126
1|2|4
(
7
1,2,4
)
∗ 6 = 105 ∗ 6 630
1|3|3
(
7
1,3,3
)
∗ 3 = 140 ∗ 3 420
2|2|3
(
7
2,2,3
)
∗ 3 = 210 ∗ 3 630
SUMA 1, 806
124 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
Ahora sí, analizaremos cada una de las particiones posibles, que en este caso se pueden reducir a las
cuatro que enlistaremos a continuación. Cabe mencionar que elegiremos un caso particular para cada una
de ellas, pero los demás casos son análogos al hacer el cambio de colores pertinente.
• 1|1|5
Supongamos que el primer muchacho tiene los ojos amarillos, el segundo grises y los cinco restan-
tes, negros.
El primer día, el muchacho de ojos amarillos no ve a nadie con ojos amarillos, por lo que puede
decidir su color de ojos y marcharse ese mismo día. Una situación análoga ocurre con el muchacho
de ojos grises, que también se va el primer día.
El segundo día, los cinco muchachos de ojos negros observan que sus compañeros de ojos grises y
amarillos se han marchado, por lo que deciden que ellos tienen los ojos negros y también se van de
la isla.
• 1|2|4
Supongamos que el primer muchacho tiene los ojos amarillos, otros dos muchachos los tienen
grises y los cuatro restantes los tienen negros.
El primer día, el muchacho de ojos amarillos no ve a nadie con ojos amarillos, por lo que puede
decidir su color de ojos y marcharse ese mismo día. Este día nadie más podrá decidir su color de
ojos.
El segundo día, cada uno de los muchachos de ojos grises se da cuenta de que su compañero de
ojos grises no abandonó la isla el día anterior. Esto sólo pudo haber pasado si veía a alguien más
que tuviera los ojos grises. Por lo tanto, cada uno de los muchachos de ojos grises decide este día
su color de ojos y abandona la isla.
El tercer día los cuatro muchachos de ojos negros observan que sus compañeros de ojos grises y
amarillos se han marchado, por lo que deciden que ellos tienen los ojos negros y también se van de
la isla.
• 1|3|3
Supongamos que el primer muchacho tiene los ojos amarillos, otros tres muchachos los tienen
grises y los tres muchachos restantes los tienen negros.
El primer día, el muchacho de ojos amarillos no ve a nadie con ojos amarillos, por lo que puede
decidir su color de ojos y marcharse ese mismo día. Este día nadie más podrá decidir su color de
ojos.
El segundo día transcurre sin novedad.
El tercer día, cada uno de los tres muchachos de ojos grises sabe que sus dos compañeros de
ojos grises no han abandonado la isla, por lo que deduce que él mismo debe tener los ojos grises.
Un razonamiento análogo aplica para los tres muchachos de ojos negros. Por lo tanto, este día
abandonan la isla tanto los muchachos de ojos grises como los de ojos negros.
5.8. OCTAVA PREGUNTA 125
• 2|2|3
Supongamos que los dos primeros muchachos tienen los ojos amarillos, otros dos los tienen grises
y los tres muchachos restantes los tienen negros.
El primer día nadie se va de la isla, pues cada uno de ellos observa que en la isla hay muchachos
de ojos grises, negros y amarillos, tal como lo dijo Hades, y no obtienen información extra.
El segundo día, cada uno de los muchachos de ojos amarillos ya ha recibido información extra,
puesto que observó que su compañero de ojos amarillos no abandonó la isla. Por lo tanto, ambos
muchachos de ojos amarillos dejan la isla este día. Asimismo, los dos muchachos de ojos grises se
van de la isla este día, pues han seguido un razonamiento análogo.
El tercer día, los tres muchachos de ojos negros observan que sus compañeros de ojos grises y
amarillos se han marchado, por lo que deciden que ellos tienen los ojos negros y también se van de
la isla.
Nuevamente resumiremos en una tabla los resultados que tenemos hasta ahora:
Número de muchachos que se van de la isla por día en que se van.
Primer día. Segundo día. Tercer día. Cuarto día. Quinto día. Sexto día.
1|1|5
1 muchacho
de ojos ama-
rillos y 1 de
ojos grises.
5 muchachos
de ojos negros.
1|2|4
1 mucha-
cho de ojos
amarillos.
2 muchachos
de ojos grises.
4 muchachos
de ojos negros.
1|3|3
1 mucha-
cho de ojos
amarillos.
3 muchachos
de ojos grises
y 3 de ojos
negros.
2|2|3
2 mucha-
chos de ojos
amarillos y 2
muchachos de
ojos grises.
3 muchachos
de ojos negros.
126 CAPÍTULO 5. APLICACIÓN AL PROBLEMA DE LA ISLA DE LOS MUERTOS
Finalmente, observamos que para cualesquiera de los mundos posibles, todos los muchachos logran irse
de la isla.
Capítulo 6
Observaciones finales
El presente trabajo nos acerca a diversas investigaciones recientes en las áreas de computación distribui-
da, topología combinatoria y lógica epistémica; ya que para su desarrollo se hizo una recopilación de
conceptos incluidos en distintas fuentes, cuyo estudio podría servir como una introducción a los temas
mencionados.
Un primer ejemplo de esto es que el contenido de las pláticas llevadas a cabo en el seminario GEOTOP-
A durante varios semestres (verbigracia, las pláticas “La topología del conocimiento” por Alexandru
Baltag y “Conocimiento y topología: una aproximación simplicial” por Jérémy Ledent) se encuentra
ampliamente relacionado con algunos de los problemas expuestos en esta tesis.
Del mismo modo, en el Instituto de Matemáticas de la UNAM se ha organizado un seminario donde se
aborda el tema del “k-acuerdo” y para ello se estudian los sistemas distribuidos, la comunicación de los
procesos, entre otros temas en los que existen frescas y prometedoras investigaciones.
127
128 CAPÍTULO 6. OBSERVACIONES FINALES
Apéndice A
Lista exhaustiva de los simplejos
Triángulos
0|1|2 (0, {0}) (1, {0, 1}) (2, {0, 1, 2})
0|2|1 (0, {0}) (2, {0, 2}) (1, {0, 1, 2})
1|0|2 (1, {1}) (0, {0, 1}) (2, {0, 1, 2})
1|2|0 (1, {1}) (2, {1, 2}) (0, {0, 1, 2})
2|0|1 (2, {2}) (0, {0, 2}) (1, {0, 1, 2})
2|1|0 (2, {2}) (1, {1, 2}) (0, {0, 1, 2})
12|0 (1, {1, 2}) (2, {1, 2}) (0, {0, 1, 2})
02|1 (0, {0, 2}) (2, {0, 2}) (1, {0, 1, 2})
01|2 (0, {0, 1}) (1, {0, 1}) (2, {0, 1, 2})
0|12 (0, {0}) (1, {0, 1, 2}) (2, {0, 1, 2})
1|02 (1, {1}) (0, {0, 1, 2}) (2, {0, 1, 2})
2|01 (2, {2}) (0, {0, 1, 2}) (1, {0, 1, 2})
012 (0, {0, 1, 2}) (1, {0, 1, 2}) (2, {0, 1, 2})
Tetraedros
0|1|2|3 (0, {0}) (1, {0, 1}) (2, {0, 1, 2}) (3, {0, 1, 2, 3})
0|1|3|2 (0, {0}) (1, {0, 1}) (3, {0, 1, 3}) (2, {0, 1, 2, 3})
0|2|1|3 (0, {0}) (2, {0, 2}) (1, {0, 1, 2}) (3, {0, 1, 2, 3})
0|2|3|1 (0, {0}) (2, {0, 2}) (3, {0, 2, 3}) (1, {0, 1, 2, 3})
0|3|1|2 (0, {0}) (3, {0, 3}) (1, {0, 1, 3}) (2, {0, 1, 2, 3})
0|3|2|1 (0, {0}) (3, {0, 3}) (2, {0, 2, 3}) (1, {0, 1, 2, 3})
1|0|2|3 (1, {1}) (0, {0, 1}) (2, {0, 1, 2}) (3, {0, 1, 2, 3})
1|0|3|2 (1, {1}) (0, {0, 1}) (3, {0, 1, 3}) (2, {0, 1, 2, 3})
1|2|0|3 (1, {1}) (2, {1, 2}) (0, {0, 1, 2}) (3, {0, 1, 2, 3})
1|2|3|0 (1, {1}) (2, {1, 2}) (3, {1, 2, 3}) (0, {0, 1, 2, 3})
1|3|2|0 (1, {1}) (3, {1, 3}) (2, {1, 2, 3}) (0, {0, 1, 2, 3})
129
130 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
1|3|0|2 (1, {1}) (3, {1, 3}) (0, {0, 1, 3}) (2, {0, 1, 2, 3})
2|0|1|3 (2, {2}) (0, {0, 2}) (1, {0, 1, 2}) (3, {0, 1, 2, 3})
2|0|3|1 (2, {2}) (0, {0, 2}) (3, {0, 2, 3}) (1, {0, 1, 2, 3})
2|1|0|3 (2, {2}) (1, {1, 2}) (0, {0, 1, 2}) (3, {0, 1, 2, 3})
2|1|3|0 (2, {2}) (1, {1, 2}) (3, {1, 2, 3}) (0, {0, 1, 2, 3})
2|3|0|1 (2, {2}) (3, {2, 3}) (0, {0, 2, 3}) (1, {0, 1, 2, 3})
2|3|1|0 (2, {2}) (3, {2, 3}) (1, {1, 2, 3}) (0, {0, 1, 2, 3})
3|0|1|2 (3, {3}) (0, {0, 3}) (1, {0, 1, 3}) (2, {0, 1, 2, 3})
3|0|2|1 (3, {3}) (0, {0, 3}) (2, {0, 2, 3}) (1, {0, 1, 2, 3})
3|1|0|2 (3, {3}) (1, {1, 3}) (0, {0, 1, 3}) (2, {0, 1, 2, 3})
3|1|2|0 (3, {3}) (1, {1, 3}) (2, {1, 2, 3}) (0, {0, 1, 2, 3})
3|2|0|1 (3, {3}) (2, {2, 3}) (0, {0, 2, 3}) (1, {0, 1, 2, 3})
3|2|1|0 (3, {3}) (2, {2, 3}) (1, {1, 2, 3}) (0, {0, 1, 2, 3})
01|2|3 (0, {0, 1}) (1, {0, 1}) (2, {0, 1, 2}) (3, {0, 1, 2, 3})
01|3|2 (0, {0, 1}) (1, {0, 1}) (3, {0, 1, 3}) (2, {0, 1, 2, 3})
02|1|3 (0, {0, 2}) (2, {0, 2}) (1, {0, 1, 2}) (3, {0, 1, 2, 3})
02|3|1 (0, {0, 2}) (2, {0, 2}) (3, {0, 1, 3}) (1, {0, 1, 2, 3})
03|1|2 (0, {0, 3}) (3, {0, 3}) (1, {0, 1, 3}) (2, {0, 1, 2, 3})
03|2|1 (0, {0, 3}) (3, {0, 3}) (2, {0, 2, 3}) (1, {0, 1, 2, 3})
12|0|3 (1, {1, 2}) (2, {1, 2}) (0, {0, 1, 2}) (3, {0, 1, 2, 3})
12|3|0 (1, {1, 2}) (2, {1, 2}) (3, {1, 2, 3}) (0, {0, 1, 2, 3})
13|2|0 (1, {1, 3}) (3, {1, 3}) (2, {1, 2, 3}) (0, {0, 1, 2, 3})
13|0|2 (1, {1, 3}) (3, {1, 3}) (0, {0, 1, 3}) (2, {0, 1, 2, 3})
23|0|1 (2, {2, 3}) (3, {2, 3}) (0, {0, 2, 3}) (1, {0, 1, 2, 3})
23|1|0 (2, {2, 3}) (3, {2, 3}) (1, {1, 2, 3}) (0, {0, 1, 2, 3})
0|12|3 (0, {0}) (1, {0, 1, 2}) (2, {0, 1, 2}) (3, {0, 1, 2, 3})
0|13|2 (0, {0}) (1, {0, 1, 3}) (3, {0, 1, 3}) (2, {0, 1, 2, 3})
0|23|1 (0, {0}) (2, {0, 2, 3}) (3, {0, 2, 3}) (1, {0, 1, 2, 3})
1|02|3 (1, {1}) (0, {0, 1, 2}) (2, {0, 1, 2}) (3, {0, 1, 2, 3})
1|03|2 (1, {1}) (0, {0, 1, 3}) (3, {0, 1, 3}) (2, {0, 1, 2, 3})
1|23|0 (1, {1}) (2, {1, 2, 3}) (3, {1, 2, 3}) (0, {0, 1, 2, 3})
2|01|3 (2, {2}) (0, {0, 1, 2}) (1, {0, 1, 2}) (3, {0, 1, 2, 3})
2|03|1 (2, {2}) (0, {0, 2, 3}) (3, {0, 2, 3}) (1, {0, 1, 2, 3})
2|13|0 (2, {2}) (1, {1, 2, 3}) (3, {1, 2, 3}) (0, {0, 1, 2, 3})
3|01|2 (3, {3}) (0, {0, 1, 3}) (1, {0, 1, 3}) (2, {0, 1, 2, 3})
3|02|1 (3, {3}) (0, {0, 2, 3}) (2, {0, 2, 3}) (1, {0, 1, 2, 3})
3|12|0 (3, {3}) (1, {1, 2, 3}) (2, {1, 2, 3}) (0, {0, 1, 2, 3})
0|1|23 (0, {0}) (1, {0, 1}) (2, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
0|2|13 (0, {0}) (2, {0, 2}) (1, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
0|3|12 (0, {0}) (3, {0, 3}) (1, {0, 1, 2, 3}) (2, {0, 1, 2, 3})
1|0|23 (1, {1}) (0, {0, 1}) (2, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
1|2|03 (1, {1}) (2, {1, 2}) (0, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
1|3|02 (1, {1}) (3, {1, 3}) (0, {0, 1, 2, 3}) (2, {0, 1, 2, 3})
2|0|13 (2, {2}) (0, {0, 2}) (1, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
2|1|03 (2, {2}) (1, {1, 2}) (0, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
2|3|01 (2, {2}) (3, {2, 3}) (0, {0, 1, 2, 3}) (1, {0, 1, 2, 3})
3|0|12 (3, {3}) (0, {0, 3}) (1, {0, 1, 2, 3}) (2, {0, 1, 2, 3})
131
3|1|02 (3, {3}) (1, {1, 3}) (0, {0, 1, 2, 3}) (2, {0, 1, 2, 3})
3|2|01 (3, {3}) (2, {2, 3}) (0, {0, 1, 2, 3}) (1, {0, 1, 2, 3})
01|23 (0, {0, 1}) (1, {0, 1}) (2, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
02|13 (0, {0, 2}) (2, {0, 2}) (1, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
03|12 (0, {0, 3}) (3, {0, 3}) (1, {0, 1, 2, 3}) (2, {0, 1, 2, 3})
12|03 (1, {1, 2}) (2, {1, 2}) (0, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
13|02 (1, {1, 3}) (3, {1, 3}) (0, {0, 1, 2, 3}) (2, {0, 1, 2, 3})
23|01 (2, {2, 3}) (3, {2, 3}) (0, {0, 1, 2, 3}) (1, {0, 1, 2, 3})
012|3 (0, {0, 1, 2}) (1, {0, 1, 2}) (2, {0, 1, 2}) (3, {0, 1, 2, 3})
013|2 (0, {0, 1, 3}) (1, {0, 1, 3}) (3, {0, 1, 3}) (2, {0, 1, 2, 3})
023|1 (0, {0, 2, 3}) (2, {0, 2, 3}) (3, {0, 2, 3}) (1, {0, 1, 2, 3})
123|0 (1, {1, 2, 3}) (2, {1, 2, 3}) (3, {1, 2, 3}) (0, {0, 1, 2, 3})
0|123 (0, {0}) (1, {0, 1, 2, 3}) (2, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
1|023 (1, {1}) (0, {0, 1, 2, 3}) (2, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
2|013 (2, {2}) (0, {0, 1, 2, 3}) (1, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
3|012 (3, {3}) (0, {0, 1, 2, 3}) (1, {0, 1, 2, 3}) (2, {0, 1, 2, 3})
0123 (0, {0, 1, 2, 3}) (1, {0, 1, 2, 3}) (2, {0, 1, 2, 3}) (3, {0, 1, 2, 3})
Aristas de triángulos
((0, 1), (0, 1)) (0, {0}) (1, {0, 1}) 1
((0, 12), (0, 2)) (0, {0}) (2, {0, 1, 2}) 2
((1,02), (1, 2)) (1, {0, 1}) (2, {0, 1, 2}) 3
((0, 2), (0, 2)) (0, {0}) (2, {0, 2}) 4
((0, 12), (0, 1)) (0, {0}) (1, {0, 1, 2}) 5
((02, 1), (2, 1)) (2, {0, 2}) (1, {0, 1, 2}) 6
((1,0), (1,0)) (1, {1}) (0, {0, 1}) 7
((1,02), (1, 2)) (1, {1}) (2, {0, 1, 2}) 8
((01, 2), (0, 2)) (0, {0, 1}) (2, {0, 1, 2}) 9
((1, 2), (1, 2)) (1, {1}) (2, {1, 2}) 10
((1,02), (1,0)) (1, {1}) (0, {0, 1, 2}) 11
((12,0), (2,0)) (2, {1, 2}) (0, {0, 1, 2}) 12
((2,0), (2,0)) (2, {2}) (0, {0, 2}) 13
((2,01), (2, 1)) (2, {2}) (1, {0, 1, 2}) 14
((02, 1), (0, 1)) (0, {0, 2}) (1, {0, 1, 2}) 15
((2, 1), (2, 1)) (2, {2}) (1, {1, 2}) 16
((2,01), (2,0)) (2, {2}) (0, {0, 1, 2}) 17
((12,0), (1,0)) (1, {1, 2}) (0, {0, 1, 2}) 18
((12), (12)) (1, {1, 2}) (2, {1, 2}) 19
((02), (02)) (0, {0, 2}) (2, {0, 2}) 20
((01), (01)) (0, {0, 1}) (1, {0, 1}) 21
((012), (12)) (1, {0, 1, 2}) (2, {0, 1, 2}) 22
((012), (02)) (0, {0, 1, 2}) (2, {0, 1, 2}) 23
((012), (01)) (0, {0, 1, 2}) (1, {0, 1, 2}) 24
132 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
Aristas de tetraedros
Vértice Vértice Número
(0, {0}) (1, {0, 1}) 1
(0, {0}) (2, {0, 2}) 2
(0, {0}) (3, {0, 3}) 3
(1, {1}) (0, {0, 1}) 4
(1, {1}) (2, {1, 2}) 5
(1, {1}) (3, {1, 3}) 6
(2, {2}) (0, {0, 2}) 7
(2, {2}) (1, {1, 2}) 8
(2, {2}) (3, {2, 3}) 9
(3, {3}) (0, {0, 3}) 10
(3, {3}) (1, {1, 3}) 11
(3, {3}) (2, {2, 3}) 12
133
(0, {0, 1}) (1, {0, 1}) 13
(0, {0, 2}) (2, {0, 2}) 14
(0, {0, 3}) (3, {0, 3}) 15
(1, {1, 2}) (2, {1, 2}) 16
(1, {1, 3}) (3, {1, 3}) 17
(2, {2, 3}) (3, {2, 3}) 18
134 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
(0, {0}) (2, {0, 1, 2}) 19
(1, {0, 1}) (2, {0, 1, 2}) 20
(0, {0}) (1, {0, 1, 2}) 21
(2, {0, 2}) (1, {0, 1, 2}) 22
(1, {1}) (2, {0, 1, 2}) 23
(0, {0, 1}) (2, {0, 1, 2}) 24
(1, {1}) (0, {0, 1, 2}) 25
(2, {1, 2}) (0, {0, 1, 2}) 26
(2, {2}) (1, {0, 1, 2}) 27
(0, {0, 2}) (1, {0, 1, 2}) 28
(2, {2}) (0, {0, 1, 2}) 29
(1, {1, 2}) (0, {0, 1, 2}) 30
135
(0, {0}) (3, {0, 1, 3}) 31
(1, {0, 1}) (3, {0, 1, 3}) 32
(0, {0}) (1, {0, 1, 3}) 33
(3, {0, 3}) (1, {0, 1, 3}) 34
(1, {1}) (3, {0, 1, 3}) 35
(0, {0, 1}) (3, {0, 1, 3}) 36
(1, {1}) (0, {0, 1, 3}) 37
(3, {1, 3}) (0, {0, 1, 3}) 38
(3, {3}) (1, {0, 1, 3}) 39
(0, {0, 3}) (1, {0, 1, 3}) 40
(3, {3}) (0, {0, 1, 3}) 41
(1, {1, 3}) (0, {0, 1, 3}) 42
136 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
(1, {1}) (3, {1, 2, 3}) 43
(2, {1, 2}) (3, {1, 2, 3}) 44
(1, {1}) (2, {1, 2, 3}) 45
(3, {1, 3}) (2, {1, 2, 3}) 46
(2, {2}) (3, {1, 2, 3}) 47
(1, {1, 2}) (3, {1, 2, 3}) 48
(2, {2}) (1, {1, 2, 3}) 49
(3, {2, 3}) (1, {1, 2, 3}) 50
(3, {3}) (2, {1, 2, 3}) 51
(1, {1, 3}) (2, {1, 2, 3}) 52
(3, {3}) (1, {1, 2, 3}) 53
(2, {2, 3}) (1, {1, 2, 3}) 54
137
(0, {0}) (3, {0, 2, 3}) 55
(2, {0, 2}) (3, {0, 2, 3}) 56
(0, {0}) (2, {0, 2, 3}) 57
(3, {0, 3}) (2, {0, 2, 3}) 58
(2, {2}) (3, {0, 2, 3}) 59
(0, {0, 2}) (3, {0, 2, 3}) 60
(2, {2}) (0, {0, 2, 3}) 61
(3, {2, 3}) (0, {0, 2, 3}) 62
(3, {3}) (2, {0, 2, 3}) 63
(0, {0, 3}) (2, {0, 2, 3}) 64
(3, {3}) (0, {0, 2, 3}) 65
(2, {2, 3}) (0, {0, 2, 3}) 66
138 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
(1, {1}) (0, {0, 1, 2, 3}) 67
(2, {1, 2}) (0, {0, 1, 2, 3}) 68
(3, {1, 2, 3}) (0, {0, 1, 2, 3}) 69
(3, {1, 3}) (0, {0, 1, 2, 3}) 70
(2, {1, 2, 3}) (0, {0, 1, 2, 3}) 71
(2, {2}) (0, {0, 1, 2, 3}) 72
(1, {1, 2}) (0, {0, 1, 2, 3}) 73
(3, {2, 3}) (0, {0, 1, 2, 3}) 74
(1, {1, 2, 3}) (0, {0, 1, 2, 3}) 75
(3, {3}) (0, {0, 1, 2, 3}) 76
(1, {1, 3}) (0, {0, 1, 2, 3}) 77
(2, {2, 3}) (0, {0, 1, 2, 3}) 78
139
(0, {0}) (1, {0, 1, 2, 3}) 79
(2, {0, 2}) (1, {0, 1, 2, 3}) 80
(3, {0, 2, 3}) (1, {0, 1, 2, 3}) 81
(3, {0, 3}) (1, {0, 1, 2, 3}) 82
(2, {0, 2, 3}) (1, {0, 1, 2, 3}) 83
(2, {2}) (1, {0, 1, 2, 3}) 84
(0, {0, 2}) (1, {0, 1, 2, 3}) 85
(3, {2, 3}) (1, {0, 1, 2, 3}) 86
(0, {0, 2, 3}) (1, {0, 1, 2, 3}) 87
(3, {3}) (1, {0, 1, 2, 3}) 88
(0, {0, 3}) (1, {0, 1, 2, 3}) 89
(2, {2, 3}) (1, {0, 1, 2, 3}) 90
140 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
(0, {0}) (2, {0, 1, 2, 3}) 91
(1, {0, 1}) (2, {0, 1, 2, 3}) 92
(3, {0, 1, 3}) (2, {0, 1, 2, 3}) 93
(3, {0, 3}) (2, {0, 1, 2, 3}) 94
(1, {0, 1, 3}) (2, {0, 1, 2, 3}) 95
(1, {1}) (2, {0, 1, 2, 3}) 96
(0, {0, 1}) (2, {0, 1, 2, 3}) 97
(3, {1, 3}) (2, {0, 1, 2, 3}) 98
(0, {0, 1, 3}) (2, {0, 1, 2, 3}) 99
(3, {3}) (2, {0, 1, 2, 3}) 100
(0, {0, 3}) (2, {0, 1, 2, 3}) 101
(1, {1, 3}) (2, {0, 1, 2, 3}) 102
141
(0, {0}) (3, {0, 1, 2, 3}) 1033
(1, {0, 1}) (3, {0, 1, 2, 3}) 104
(2, {0, 1, 2}) (3, {0, 1, 2, 3}) 105
(2, {0, 2}) (3, {0, 1, 2, 3}) 106
(1, {0, 1, 2}) (3, {0, 1, 2, 3}) 107
(1, {1}) (3, {0, 1, 2, 3}) 108
(0, {0, 1}) (3, {0, 1, 2, 3}) 109
(2, {1, 2}) (3, {0, 1, 2, 3}) 110
(0, {0, 1, 2}) (3, {0, 1, 2, 3}) 111
(2, {2}) (3, {0, 1, 2, 3}) 112
(0, {0, 2}) (3, {0, 1, 2, 3}) 113
(1, {1, 2}) (3, {0, 1, 2, 3}) 114
142 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
(1, {0, 1, 2}) (2, {0, 1, 2}) 115
(0, {0, 1, 2}) (2, {0, 1, 2}) 116
(0, {0, 1, 2}) (1, {0, 1, 2}) 117
(1, {0, 1, 3}) (3, {0, 1, 3}) 118
(0, {0, 1, 3}) (3, {0, 1, 3}) 119
(0, {0, 1, 3}) (1, {0, 1, 3}) 120
(2, {0, 2, 3}) (3, {0, 2, 3}) 121
(0, {0, 2, 3}) (3, {0, 2, 3}) 122
(0, {0, 2, 3}) (2, {0, 2, 3}) 123
(2, {1, 2, 3}) (3, {1, 2, 3}) 124
(1, {1, 2, 3}) (3, {1, 2, 3}) 125
(1, {1, 2, 3}) (2, {1, 2, 3}) 126
143
(2, {0, 1, 2, 3}) (3, {0, 1, 2, 3}) 127
(1, {0, 1, 2, 3}) (3, {0, 1, 2, 3}) 128
(1, {0, 1, 2, 3}) (2, {0, 1, 2, 3}) 129
(0, {0, 1, 2, 3}) (3, {0, 1, 2, 3}) 130
(0, {0, 1, 2, 3}) (2, {0, 1, 2, 3}) 131
(0, {0, 1, 2, 3}) (1, {0, 1, 2, 3}) 132
144 APÉNDICE A. LISTA EXHAUSTIVA DE LOS SIMPLEJOS
Apéndice B
El problema de las niñas enlodadas
En este apéndice presentamos la solución, que hemos traducido al español, del problema de las niñas
enlodadas, que aparece en la Stanford Encyclopedia of Philosophy.
B.1. Planteamiento del problema
El problema de las niñas enlodadas. Tres niñas juegan en el lodo. Su padre las llama para
que acudan a casa y las dispone en un semicírculo de manera que cada niña pueda ver
claramente a las otras.
− Al menos una de ustedes tiene lodo en la frente− les indica el padre.
Las niñas miran a su alrededor y cada una examina la frente de las otras niñas. Por supuesto,
ninguna niña puede examinar su propia frente. El padre continúa:
− Si alguna de ustedes sabe si su frente está sucia, dé un paso al frente ahora mismo.
Ninguna de las niñas da el paso. El padre repite lo que dijo antes:
− Si alguna de ustedes sabe si su frente está sucia, dé un paso al frente ahora mismo.
Algunas niñas dan un paso al frente, pero no todas. El padre repite una tercera vez lo que
dijo antes:
− Si alguna de ustedes sabe si su frente está sucia, dé un paso al frente ahora mismo. Esta
vez, todas las niñas restantes dan un paso al frente.
¿Cuántas niñas tienen lodo en la frente?
B.2. Solución
Cada una de las tres niñas tiene la frente limpia o sucia. Si usamos la letra l para “limpia” y la letra s para
“sucia”, podemos usar una sucesión de tres letras para indicar la situación actual. Por ejemplo, lsl indica
que la primera niña tiene la frente limpia, la segunda niña tiene la frente sucia y la tercera niña tiene la
145
146 APÉNDICE B. EL PROBLEMA DE LAS NIÑAS ENLODADAS
frente limpia. En consecuencia, hay 8 posibilidades en total. Esto nos lleva al modeloMmc que se ilustra
en la Figura B.1.
lls
lll
sls
sll
lss
lsl
sss
ssl
1
1
1
1
2 2
2 2
3 3
3 3
Mmc
Figura B.1: Configuración inicial para el problema de las niñas enlodadas. Las flechas anaranjadas, eti-
quetadas con 1, indican la incertidumbre de la primera niña; las flechas azules, etiquetadas con 2, indican
la incertidumbre de la segunda niña; las flechas moradas, etiquetadas con 3, indican la incertidumbre de
la tercera niña. Por simplicidad, en la figura se omiten las flechas reflexivas (i.e., para completar la figura,
se deberían añadir para cada niña y cada mundo, una flecha para esa niña en forma de lazo que apuntara
desde ese mundo justo de vuelta a ese mismo mundo).
En el modelo Mmc de la Figura B.1, vemos que cada niña conoce el estado de las frentes de las otras
niñas pero no su propio estado: en cada mundo, los únicos mundos que una niña considera posibles son
aquellos en los que el estado de las frentes de las otras niñas es el mismo pero el estado de su propia
frente podría ser diferente. Por ejemplo, en el mundo ssl, las únicas posibilidades que la primera niña
considera son la misma ssl (por medio de la flecha reflexiva etiquetada con 1 no dibujada) y el mundo
lsl. Dado que el estado de las frentes de las otras niñas es el mismo en los mundos ssl y lsl (es decir, la
frente de la niña 2 está sucia y la de la niña 3 está limpia) pero el estado de la frente de la primera niña
no es el mismo (es decir, la frente de la niña 1 está sucia en ssl pero limpia en lsl), podemos decir lo
siguiente: en el mundo ssl, la primera niña sabe si las frentes de las otras niñas están sucias o no, pero no
sabe si su propia frente está sucia. Podemos mostrar que ocurre lo mismo para cada mundo y para cada
niña. Por lo tanto,Mmc efectivamente modela la situación inicial del problema de las niñas enlodadas.
Ahora consideremos el efecto del primer anuncio del padre, que etiquetaremos con la letra F:
(F) “Al menos una de ustedes tiene lodo en la frente.”
El efecto de este anuncio público es que elimina todos aquellos mundos en los que F es falsa, estos son
los mundos en los cuales ninguna niña tiene la frente sucia. Hay únicamente uno de estos mundos: lll.
Por lo tanto, el anuncio público de F modifica la situación inicial Mmc y produce el modelo Mmc[F]
representado en la Figura B.2.
B.2. SOLUCIÓN 147
lls
lll
sls
sll
lss
lsl
sss
ssl
1
1
1
1
2 2
2 2
3 3
3 3
Mmc[F]
Figura B.2: El modelo Mmc[F] obtenido de Mmc (Figura B.1) por medio del anuncio público de F. Los
mundos y las flechas de Mmc que fueron borradas han sido dibujadas de manera tenue, pero en realidad,
estas no forman parte del modeloMmc[F]. También, la figura omite las flechas reflexivas para cada agente
en cada mundo.
Luego el padre dice: “Si alguna de ustedes sabe si su frente está sucia, dé un paso al frente ahora mismo”.
Esta es la primera vez que él dice esto y ninguna niña da un paso al frente. Consideramos que la decla-
ración del padre seguida de que ninguna niña dé un paso al frente, es equivalente al siguiente anuncio
público, al que denotaremos con la letra N:
(N) “Ninguna niña sabe si su frente está sucia.”
El efecto del anuncio de N es eliminar aquellos mundos en los que N es falsa; estos son los mundos en
que alguna niña sabe si su frente está sucia. Para que un agente sepa si su propia frente está sucia en un
mundo dado, debe saber en ese mundo que su frente está sucia o debe saber en ese mundo que su frente
está limpia. Tenemos que “el agente a sabe F enw” si y sólo si F es verdadera en cada mundow ′ tal que
existe una flecha etiquetada con la letra a que apunta de w a w ′ (tomando en cuenta, por supuesto, las
flechas reflexivas no dibujadas). Así que, tomadas estas afirmaciones en conjunto, el agente a sabe si su
frente está sucia sólo en el caso de que todas las flechas etiquetadas con a que salen, apunten solamente
a mundos que tienen el mismo estado limpio/sucio para el agente a. Por lo tanto, el efecto del anuncio
público de N es que elimina los mundos que satisfagan esta propiedad para una de las niñas. Haciendo
referencia a la Figura B.2, vemos que los mundos a eliminar son:
• lsl, ya que este mundo no tiene una flecha etiquetada con 2 que apunte a un mundo con un estado
limpia/sucia diferente para la segunda niña,
• lls, ya que este mundo no tiene una flecha etiquetada con 3 que apunte a un mundo con un estado
limpia/sucia diferente para la tercera niña, y
• sll, ya que este mundo no tiene una flecha etiquetada con 1 que apunte a un mundo con un estado
limpia/sucia diferente para la primera niña.
El resultado del anuncio de N es el modeloMmc[F][N] representado en la Figura B.3.
148 APÉNDICE B. EL PROBLEMA DE LAS NIÑAS ENLODADAS
lls
lll
sls
sll
lss
lsl
sss
ssl
1
1
1
1
2 2
2 2
3 3
3 3
Mmc[F][N]
Figura B.3: El modelo Mmc[F][N] obtenido de Mmc[F] (Figura B.2) después del anuncio público de N.
Los mundos y las flechas deMmc y deMmc[F] que fueron borradas han sido dibujadas de manera tenue,
mas no forman parte del modelo Mmc[F][N]. También, la figura omite las flechas reflexivas para cada
agente en cada mundo.
El padre ahora hace su anuncio por segunda vez (“Si alguna de ustedes sabe si su frente está sucia, dé
un paso al frente ahora mismo”). Pero esta vez algunas niñas dan un paso al frente, expresando de este
modo que ellas saben si sus frentes están sucias. Entonces interpretamos la declaración del padre seguida
de las acciones de las niñas como un único anuncio de la negación ¬N de nuestra afirmaciónN anterior.
Es decir, tomamos el resultado neto como equivalente al siguiente anuncio público:
(¬N) “Alguna niña sabe si su frente está sucia.”
El efecto de este anuncio es borrar todos aquellos mundos en los que la declaración ¬N es falsa: estos
son los mundos en los que ninguna niña sabe si su frente está sucia. Es decir, debemos eliminar los
mundos en los que cada agente tiene una flecha que apunta a un mundo en el que su frente está limpia y
otra flecha que apunta a otro mundo en el que su frente está sucia (por supuesto, teniendo en cuenta las
flechas reflexivas no dibujadas). Al examinar la Figura B.3, vemos que el único mundo que cumple esto
es sss: en este mundo, cada agente considera una posibilidad en la que su propia frente está limpia junto
con una posibilidad en la que su propia frente está sucia. Por lo tanto, el resultado del anuncio público
de ¬N es borrar este mundo, dando lugar de este modo al modelo Mmc[F][N][¬N] representado en la
Figura B.4.
B.2. SOLUCIÓN 149
lls
lll
sls
sll
lss
lsl
sss
ssl
1
1
1
1
2 2
2 2
3 3
3 3
Mmc[F][N][¬N]
Figura B.4: El modeloMmc[F][N][¬N] obtenido deMmc[F][N] (Figura B.3) después del anuncio público
de ¬N. Los mundos y las flechas deMmc, Mmc[F] y Mmc[F][N] que fueron borradas han sido dibujadas
de manera tenue, mas no forman parte del modelo Mmc[F][N][¬N]. También, la figura omite las flechas
reflexivas para cada agente en cada mundo.
El padre ahora hace su anuncio por tercera vez (“Si alguna de ustedes sabe si su frente está sucia, dé un
paso al frente ahora mismo”). Ahora, se nos dice, las niñas restantes dan un paso al frente. Nuevamente
consideramos que esto es equivalente al anuncio de ¬N (“Alguna niña sabe si su frente está sucia”).
Como antes, el efecto de este anuncio es borrar cualquier mundo en que el anuncio sea falso: estos son
los mundos en los que ninguna niña sabe si su frente está sucia, los cuales son los mundos en los que
cada niña considera una posibilidad en la que su frente está sucia y una posibilidad en la que su frente
está limpia. Al examinar la Figura B.4, vemos que ninguno de los mundos satisface estos requerimentos:
en cada mundo, cada niña sólo considera ese mismo mundo y por lo tanto cada niña sabe si su frente
está sucia. Así que el resultado del segundo anuncio público de ¬N es el modelo Mmc[F][N][¬N][¬N],
representado en la Figura B.5.
150 APÉNDICE B. EL PROBLEMA DE LAS NIÑAS ENLODADAS
lls
lll
sls
sll
lss
lsl
sss
ssl
1
1
1
1
2 2
2 2
3 3
3 3
Mmc[F][N][¬N][¬N]
Figura B.5: El modeloMmc[F][N][¬N][¬N] obtenido deMmc[F][N][¬N] (Figura B.4) después del anun-
cio público de ¬N. Los mundos y las flechas deMmc,Mmc[F] yMmc[F][N] que fueron borradas han sido
dibujadas de manera tenue, mas no forman parte del modelo Mmc[F][N][¬N][¬N]. También, la figura
omite las flechas reflexivas para cada agente en cada mundo.
Obviamente, dado que el segundo anuncio de ¬N no eliminó ningún mundo, los modelos de las Figuras
B.4 yB.5 son los mismos:
Mmc[F][N][¬N] =Mmc[F][N][¬N][¬N].
Al observar ahora este modelo, obtenemos la solución: dos niñas están sucias y una está limpia.
Referencias
ATTIYA, Hagit ; WELCH, Jennifer: Distributed Computing: Fundamentals, Simulations and Advanced
Topics. Hoboken, NJ, USA : John Wiley & Sons, Inc., 2004. – ISBN 0471453242
GIBLIN, Peter: Graphs, Surfaces and Homology. 3. Cambridge University Press, 2010 http://
dx.doi.org/10.1017/CBO9780511779534. – ISBN 978–0–521–15405–5
GRÜNBAUM, Branko: Convex Polytopes. 2. New York : Springer New York, 2003. – ISBN 0–387–
00424–6
KOZLOV, Dmitry: Combinatorial Algebraic Topology. Berlin, Heidelberg : Springer Berlin Heidel-
berg, 2008 http://dx.doi.org/10.1007/978-3-540-71962-5_4. – ISBN 978–3–540–
71962–5
KOZLOV, Dmitry: “Chromatic subdivision of a simplicial complex”. In: Homology, Homotopy and
Applications 14 (2012), Nr. 2, 197 – 209. https://projecteuclid.org/journals/
homology-homotopy-and-applications/volume-14/issue-2/Chromatic-
subdivision-of-a-simplicial-complex/hha/1355321488.full
NEVE, Cecilia ; ROSALES, Laura: Por la senda de los círculos. Papirhos, Instituto de Matemáticas,
UNAM, 2017. – ISBN 978–607–02–9828–8
RAJSBAUM, Sergio ; KOZLOV, Dmitry ; HERLIHY, Maurice: Distributed Computing Through Combi-
natorial Topology. Boston : Morgan Kaufmann, 2014 https://doi.org/10.1016/B978-0-
12-404578-1.00024-3. – ISBN 978–0–12–404578–1
STANFORD Encyclopedia of Philosophy: Appendix B: Solutions to Cheryl’s Birthday, Muddy Chil-
dren, and Sum and Least Common Multiple. https://plato.stanford.edu/entries/
dynamic-epistemic/appendix-B-solutions.html, . – Accessed: 2021-07-26
VELÁZQUEZ CERVANTES, Diego A.: Una relación entre las lógicas modales y el enfoque topológico
del cómputo distribuido. Ciudad de México : Universidad Nacional Autónoma de México, 2019. –
Tesis de Maestría.
ZIEGLER, Günter M.: Lectures on polytopes. New York : Springer-Verlag, 1995. – ISBN 978–1–4613–
8431–1
151