# 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$

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

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.

• Sorry for getting aware of your answer only today! – Hans-Peter Stricker Apr 13 '17 at 17:25
• @HansStricker No worries, it was a good question and fun to answer. Also, I mentioned this as an example of the Yoneda lemma here. – Oscar Cunningham Apr 13 '17 at 17:30