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?

$\endgroup$
  • 11
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Feb 7 '12 at 18:23
  • 4
    $\begingroup$ 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. $\endgroup$ – Dominic van der Zypen Sep 2 '14 at 10:22
  • $\begingroup$ 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$). $\endgroup$ – Mike F Jun 28 '15 at 23:15
  • 1
    $\begingroup$ 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$. $\endgroup$ – Martin Brandenburg Jun 28 '15 at 23:35
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.