Sea \(G\) una gráfica (simple, finita). Una completa de \(G\) es \(C\subseteq V(G)\) tal que si \(x_{1},x_{2}\in C\), entonces \(x_{1}\sim x_{2}\). Observemos que si \(C_{1}\) es completa de \(G\) y \(C_{2}\subseteq C_{1}\), entonces \(C_{2}\) es completa.

El complejo \(\Delta(G)\) se define como el complejo simplicial sobre \(V(G)\) cuyos simplejos son las completas de \(G\).

Si tenemos un complejo simplicial \(\Delta\) y existe una gráfica \(G\) tal que \(\Delta=\Delta(G)\), decimos que \(\Delta\) es un complejo simplicial de completas. (En inglés, \(\Delta\) se llama flag complex o clique complex).

Ejemplos. Sea \(G\) la gráfica donde el conjunto de vértices es \(V(G)=\{a,b,c,d,e,f\}\) , y el conjunto de aristas es: \(E(G)=\{ab,ac,ad,ae,af,bf,cf,de,ef\}\). Entonces se tiene que \(\mathcal{F}(\Delta(G))=\{abf,acf,ade,aef\}\).

Tarea. Muestra que existe un complejo simplicial \(\Delta\) tal que no existe gráfica \(G\) con \(\Delta(G)=\Delta\).

Tarea. Determina un criterio para que un complejo simplicial \(\Delta\) sea un complejo simplicial de completas. [Por ejemplo, ya vimos que una condición necesaria para que \(\Delta\) sea un complejo de completas, es que si \(ab,ac,bc\in\Delta\), entonces \(abc\in\Delta\). ¿Es una condición suficiente?]

Una gráfica dirigida \(D\) (o digráfica) consta de un conjunto de vértices y un conjunto de flechas, las cuales son parejas ordenadas de vértices.

Por ejemplo, consideremos la gráfica dirigida con vértices \(\{1,2,3,4\}\) y cuyas flechas sean \(\{(1,2), (2, 3), (3, 1), (2, 4)\}\).

Sea \(D\) una gráfica dirigida (cada arista tiene exactamente una dirección). Vamos a formar un complejo simplicial \(\Delta^{\to}(D)\) sobre \(V(D)\), donde \(\sigma\subseteq V(D)\) es un simplejo si la subdigráfica dirigida de \(D\) inducida por \(\sigma\) es completa y sea acíclica (es decir, que no tenga ciclos dirigidos).

Tarea. Muestra que una digráfica completa y acíclica tiene un sumidero y una fuente. (Un sumidero es un vértice a donde todas sus flechas llegan, una fuente es un vértice de donde todas sus aristas salen)

Sea \(\mathcal{C}\) una colección de subconjuntos de un conjunto \(X\). (Es decir \(\mathcal{C}\subseteq \mathcal{P}(X)\)). Sea \(G\) la gráfica con vértices \(\mathcal{C}\), donde declaramos \(C_{1}\sim C_{2}\) si \(C_{1}\ne C_{2}\) y \(C_{1}\cap C_{2}\ne\emptyset\) (la gráfica \(G\) se llama la gráfica de intersección de la colección \(\mathcal{C}\)). A partir de la gráfica \(G\) formamos \(\Delta(G)\), la cual podríamos denotar como \(\Delta(\mathcal{C})\).

Ejemplo: Sea \(X=\{1,2,3,4,5\}\). Sea \(\mathcal{C}=\{\{2,3,5\}, \{2,3,4,5\}, \{2,4\},\{1\},\{2\}\}\).

Sea \(\mathcal{C}\) una colección de subconjuntos de un conjunto \(X\). Definimos un complejo simplicial \(\mathcal{N}(\mathcal{C})\) con vértices \(\mathcal{C}\), donde \(\sigma\subseteq \mathcal{C}\) es un simplejo si \(\cap\sigma\ne\emptyset\).

Ejemplo Sea \(X=\{1,2,3,4,5\}\) y sea \(\mathcal{C}=\{\{1,2\},\{2,3\},\{1,3\},\{3,4,5\}\}\).