30
$\begingroup$

Under which name is the following proposition filed actually:

Every poset $P$ embeds fully and faithfully in the powerset of $P$, ordered by subset inclusion.

Let me call it Dedekind's lemma. Next to Cayley's theorem:

Every group $G$ is isomorphic to a subgroup of the symmetric group acting on $G$.

it is a prominent special case of Yoneda's lemma.

All proofs are constructive, and so is the proof of Erdős' lemma on intersection graphs:

Every graph $G$ is isomorphic to a family of subsets $S_i$ of a set S such that $v_i$ and $v_j$ are joined by an edge iff $S_i \cap S_j \neq \emptyset$

What I wonder about is:

Is Erdős' lemma on intersection graphs a special case of Yoneda's lemma?

  • 1
    This is not really Erdös' Lemma. The lemma was proven by Szpilrajn-Marczewski (see http://matwbn.icm.edu.pl/ksiazki/fm/fm33/fm33131.pdf). Erdös, Goodman and Posa have given a bound for $\# S$.2015-06-28

1 Answers 1

4

As Qiaochu mentions in the comments, the main question is how to view a graph as some sort of category.

The answer is to think of a graph as an abstract simplicial complex which has vertices and edges but happens to have no triangles or anything of higher dimension.

An abstract simplicial complex on a set $V$ is a set $\Delta$ of nonempty finite subsets of $V$ such that if $v\in V$ then $\{v\}\in\Delta$ and if $\emptyset\neq A\subseteq B\in\Delta$ then $A\in\Delta$. Therefore for any abstract simplicial complex we have a poset given by $\Delta$ ordered under inclusion. This allows us to view abstract simplicial complexes as categories by viewing this poset as a category in the usual way.

In particular, a graph $G$ becomes the poset category $\mathcal G$ which has an object for each vertex and each edge. The morphisms are the identities and a morphism from each vertex to each of the edges that it lies on. Note that $G$ may be recovered from $\mathcal G$.

We're going to take the Yoneda embedding of $\mathcal G^{\mathrm{op}}$. But in this case and in the two other examples given in the question, when people say "Yoneda embedding" they really mean the map $S:\mathcal C\rightarrow \mathbf{Set}$ given by composing the actual Yoneda embedding $y:\mathcal C\rightarrow \mathbf{Set}^{\mathcal C^{\mathrm{op}}}$ with the map $P:\mathbf{Set}^{\mathcal C^{\mathrm{op}}}\rightarrow \mathbf{Set}$ that takes the coproduct over the objects of $\mathcal C$.

Applied to a poset, $S$ gives the map that takes an element to the set of things less than it. So applied to $\mathcal G^{\mathrm{op}}$ the functor $S$ maps each vertex $v$ to the set $S_v=\{v\}\cup\{e\in E|v\in e\}$ and maps each edge to the singleton $S_e=\{e\}$.

By inspection, the family of sets $\{S_v|v\in V\}$ does indeed have $G$ as its intersection graph, and indeed this construction is exactly the one given by Szpilrajn-Marczewski in the original proof of this theorem.


We can also say something about Erdős' proof of this theorem. Erdős' construction takes the vertex $v$ to the set $C_v$ of complete subgraphs of $G$ that contain $v$.

Above we've been viewing a graph as a simplicial complex; this gives a functor $F:\mathbf{Graph}\rightarrow\mathbf{A.S.C.}$. This is the left-adjoint-right-inverse to the "$1$-skeleton" functor $U:\mathbf{A.S.C.}\rightarrow\mathbf{Graph}$ that takes an abstract simplicial complex to the graph formed by its $0$-simplices and $1$-simplices. But $U$ also has a right-adjoint-right-inverse: the functor that takes a graph to its simplicial complex of complete subgraphs.

Erdős' construction is given by the Yoneda embedding applied to the poset arising from this simplicial complex.

  • 0
    @HansStricker No worries, it was a good question and fun to answer. Also, I mentioned this as an example of the Yoneda lemma [here](https://math.stackexchange.com/a/2218047/1149).2017-04-13