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

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?

-
Well, posets and groups are both special cases of categories, but graphs aren't, so I'm not sure what category you'd be applying Yoneda to. – Qiaochu Yuan Feb 7 '12 at 18:23
Note that if Erdös Lemma isn't a special case of Yoneda's Lemma (which I suspect it isn't, for reasons that Qiaochu mentions), this will be very hard to prove - it will require some Gödel-like effort on a meta-level. – Dominic van der Zypen Sep 2 '14 at 10:22
Note you could think of a graph as a category $G$ together with a functor $L : G \to \mathbb{N}$. The objects of $G$ are the vertices, the morphisms from $v$ to $w$ are the walks from $v$ to $w$, composition of morphisms is concatenation of walks. The functor $L$ tells you the length of a walk (which lets you recover the edges as the walks of length $1$). – Mike F Jun 28 '15 at 23:15
This is not really Erdös' Lemma. The lemma was proven by Szpilrajn-Marczewski (see matwbn.icm.edu.pl/ksiazki/fm/fm33/fm33131.pdf). Erdös, Goodman and Posa have given a bound for $\# S$. – Martin Brandenburg Jun 28 '15 at 23:35

## 1 Answer

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 $T$ is an $\mathcal{A}\subseteq\mathcal{P}(T)$ such that $X\in\mathcal{A}$ implies $X$ is finite, and such that $Y\subseteq X\in\mathcal A$ implies $Y\in A$. (Contrary to wikipedia I will say that we do have $\emptyset\in\mathcal A$.) Therefore for any abstract simplicial complex we have a poset given by $\mathcal A$ ordered under inclusion. This allows us to view abstract simplicial complexes as categories by viewing this poset as a category in the usual way.

So we view a graph $G$ as the poset category $\mathcal G$ which has an object for the empty set, each vertex, and each edge. The morphisms are the inclusion of the empty set into everything, and the inclusion of each vertex into the edges that it lies on. Note that $G$ may be recovered from $\mathcal G$, up to isomorphism.

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 $\emptyset$ to the set $S_\emptyset=\{\emptyset\}\cup V\cup E$, 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. But I would like to prove this using the properties of the Yoneda embedding rather than just seeing that it works.

The Yoneda embedding is full, faithful and preserves all limits. The functor $P$ is faithful and preserves connected limits. Therefore $S$ will also be faithful and preserve connected limits.

Since each morphism in a poset is monic (and because the property of being monic can be expressed in terms of pullbacks) each morphism in $\mathcal G^{\mathrm{op}}$ gives an inclusion in $\mathbf{Set}$. So the $S_v$s and $S_e$s are indeed subsets of $S_\emptyset$. If two vertices $v$ and $v'$ are joined by an edge $e$ then

$$\require{AMScd} \begin{CD} \emptyset @>>> v\\ @VVV @VVV\\ v' @>>> e \end{CD}$$

is a pushout in $\mathcal G$, so

$$\require{AMScd} \begin{CD} S_\emptyset @<<< S_v\\ @AAA @AAA\\ S_{v'} @<<< S_e \end{CD}$$

is a pullback, and so $S_v\cap S_{v'}=S_e$ which is non-empty since $e\in S$.

Sadly, I don't see how to prove that $S_v\cap S_{v'}=\emptyset$ when $v$ and $v'$ are not joined by an edge. Perhaps someone else knows the solution?

The set family we've constructed above is essentially 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.

-