¿Es el lema de Erdős sobre los grafos de intersección un caso especial del lema de Yoneda?

Question

Bajo qué nombre se presenta realmente la siguiente proposición:

Cada poset $P$ se integra plenamente y con fidelidad en el conjunto de poderes de $P$ , ordenados por inclusión de subconjuntos.

Permítanme llamarlo El lema de Dedekind . Al lado de Teorema de Cayley :

Cada grupo $G$ es isomorfo a un subgrupo del grupo simétrico que actúa sobre $G$ .

es un caso especial destacado de El lema de Yoneda .

Todas las pruebas son constructivas, y así es la prueba de El lema de Erdos en los gráficos de intersección:

Cada gráfico $G$ es isomorfo a una familia de subconjuntos $S_i$ de un conjunto S tal que $v_i$ y $v_j$ están unidos por una arista si $S_i \cap S_j \neq \emptyset$

Lo que me pregunto es:

¿Es el lema de Erdos sobre los grafos de intersección un caso especial del lema de Yoneda?

Answer 1

Como menciona Qiaochu en los comentarios, la cuestión principal es cómo ver un gráfico como una especie de categoría.

La respuesta es pensar en un gráfico como un complejo simplicial abstracto que tiene vértices y aristas pero resulta que no tiene triángulos ni nada de dimensión superior.

Un complejo simplicial abstracto sobre un conjunto $V$ es un conjunto $\Delta$ de subconjuntos finitos no vacíos de $V$ de manera que si $v\in V$ entonces $\{v\}\in\Delta$ y si $\emptyset\neq A\subseteq B\in\Delta$ entonces $A\in\Delta$ . Por lo tanto, para cualquier complejo simplicial abstracto tenemos un poset dado por $\Delta$ ordenado bajo inclusión. Esto nos permite ver los complejos simpliciales abstractos como categorías al considerar este poset como una categoría de la manera habitual.

En particular, un gráfico $G$ se convierte en la categoría poset $\mathcal G$ que tiene un objeto para cada vértice y cada arista. Los morfismos son las identidades y un morfismo de cada vértice a cada una de las aristas en las que se encuentra. Nótese que $G$ puede ser recuperado de $\mathcal G$ .

Vamos a tomar la incrustación de Yoneda de $\mathcal G^{\mathrm{op}}$ . Pero en este caso y en los otros dos ejemplos citados en la pregunta, cuando la gente dice "incrustación de Yoneda" se refiere realmente al mapa $S:\mathcal C\rightarrow \mathbf{Set}$ dada por la composición de la incrustación real de Yoneda $y:\mathcal C\rightarrow \mathbf{Set}^{\mathcal C^{\mathrm{op}}}$ con el mapa $P:\mathbf{Set}^{\mathcal C^{\mathrm{op}}}\rightarrow \mathbf{Set}$ que toma el coproducto sobre los objetos de $\mathcal C$ .

Aplicado a un poset, $S$ da el mapa que lleva un elemento al conjunto de cosas menores que él. Así que aplicado a $\mathcal G^{\mathrm{op}}$ el functor $S$ mapea cada vértice $v$ al conjunto $S_v=\{v\}\cup\{e\in E|v\in e\}$ y asigna cada arista al singleton $S_e=\{e\}$ .

Por inspección, la familia de conjuntos $\{S_v|v\in V\}$ sí tiene $G$ como su gráfico de intersección, y de hecho esta construcción es exactamente la dada por Szpilrajn-Marczewski en la prueba original de este teorema.

---

También podemos decir algo sobre la prueba de Erdős de este teorema. La construcción de Erdős toma el vértice $v$ al conjunto $C_v$ de subgrafos completos de $G$ que contienen $v$ .

Antes hemos estado viendo un gráfico como un complejo simplicial; esto da un functor $F:\mathbf{Graph}\rightarrow\mathbf{A.S.C.}$ . Se trata de la unión izquierda-derecha-inversa de la " $1$ -functor "esqueleto". $U:\mathbf{A.S.C.}\rightarrow\mathbf{Graph}$ que lleva un complejo simplicial abstracto al gráfico formado por su $0$ -simples y $1$ -simples. Pero $U$ también tiene una unión derecha-inversa: el functor que lleva un gráfico a su complejo simplicial de subgrafos completos .

La construcción de Erdős viene dada por la incrustación de Yoneda aplicada al poset que surge de este complejo simplicial.