Let me define undirected graphs - slightly deviating from common usage - not to be a symmetric binary relation on an arbitrary finite set, but on a finite subset of $\,\mathbb{N}$. Anyway I write $G = (V(G), E(G))$ where $V(G)\subset \mathbb{N}$ is the underlying set of vertices of the graph $G$ and $E(G)$ is its set of unordered pairs of vertices called edges.

There are - among others - two notions of morphisms for a category of undirected graphs: graph homomorphisms (the weaker notion, giving rise to the category $\mathcal{G}_1$) and elementary embeddings (the stronger notion, giving rise to the category $\mathcal{G}_2$, which is a subcategory of $\mathcal{G}_1$).

For each permutation $\pi: \mathbb{N} \rightarrow \mathbb{N}$ there are (endo-)functors $F_\pi$ both from $\mathcal{G}_1$ to itself and from $\mathcal{G}_2$ to itself which are definable in an obvious way:

$$V(F_\pi(G)) = \pi(V(G))$$ $$\lbrace x,y\rbrace \in E(F_\pi(G))\quad \text{iff}\quad \lbrace \pi^{-1}(x),\pi^{-1}(y) \rbrace \in E(G)$$ $$F_\pi(f) = F_{\pi} \circ f \circ F_{\pi^{-1}}$$

[Intermediate questions]
1. Is it OK to write the definition of $F_\pi(f)$ like this?
2. Can $F_\pi$ - thus defined - be also a (somehow forgetful) functor from $\mathcal{G}_2$ to $\mathcal{G}_1$, but eventually not the other way around?

Only for $\mathcal{G}_2$ - i.e. for elementary embeddings as morphisms - there is (as I do believe) another "uniform" family of (endo-)functors from $\mathcal{G}_2$ to itself. Consider formulas $\phi(x,y)$ of the first-order language with signature $\sigma = \lbrace E\,\rbrace$ with the binary relation symbol $E(x,y)$ indicating that $\lbrace x,y\rbrace \in E(G)$. For each such formula $\phi$ there is a "definition functor" $F_\phi$ definable like this:

$$V(F_\phi(G)) = V(G)$$ $$\lbrace x,y\rbrace \in E(F_\phi(G))\quad \text{iff}\quad G \models \phi(x,y)$$ $$F_\phi(f) = f$$

$f$ has to be seen as a map on the vertex set only, otherwise the functor condition $\operatorname{src}(F(f)) = F(\operatorname{src}(f))$ would not be fulfilled, because $F_\phi(G)$ is another graph than $G$ (having the same vertex set only).

[Intermediate question] Are these "definition functors" $F_\phi$ really functors?

Assuming the latter, I have a bunch of questions (some more trivial than others, but I'd like to ask them all, because they belong together):

  1. Given a "permutation functor" $F_\pi$: for which functors $F$ are there natural transformations $\eta$ from $F_\pi$ to $F$ (and vice versa)? Do these functors $F$ have to be permutation functors themselves? If so: for which permutations $\pi'$ are there natural transformations $\eta$ from $F_\pi$ to $F_{\pi'}$ (and vice versa)?

  2. The same for "definition functors": Given a definition functor $F_\phi$: for which functors $F$ are there natural transformations $\eta$ from $F_\phi$ to $F$ (and vice versa)? Do these functors $F$ have to be definition functors themselves? If so: for which formulas $\phi'$ are there natural transformations $\eta$ from $F_\phi$ to $F_{\phi'}$ (and vice versa)?

  3. What are examples of endo-functors of $\mathcal{G}_2$ that are not finite combinations of permutation and definition functors?

  • $\begingroup$ Could you give some additional explanationat about the first order language, formula $\phi$ and signature? $\endgroup$ Jul 31 '13 at 10:57
  • 1
    $\begingroup$ There is also a cartesian closed category of undirected graphs: for a discussion see R. Brown, I. Morris, J. Shrimpton and C.D. Wensley, `Graphs of Morphisms of Graphs', Electronic Journal of Combinatorics, A1 of Volume 15(1), 2008. 1-28. Does this category help your question? $\endgroup$ Jul 31 '13 at 14:06
  • $\begingroup$ @Garlef: What I mean is the first order language of signature $\sigma=\lbrace E \rbrace$ with one binary relation symbol $E$ and formulas $\phi(x,y)$ with two free variables. (Symmetry has to required appropriately.) $\endgroup$ Jul 31 '13 at 21:34

I have to think about this a bit.

Some first remarks: Why do you need to consider propper subsets? From a category theoretic view it is easier to work with the comma-category $$\mathrm{FinGrph}/\mathsf{blob}(\mathbb N)$$ a.k.a. finite graphs together with a graph morphism $s:G\to \mathsf{blob}(\mathbb N):=(\mathbb N,\mathbb N\times \mathbb N)$ a.k.a. finite graphs $G$ together with a map $s:V(G)\to\mathbb N$. This category is not equivalent to your $\mathcal G_1$ but contains it as a full reflective subcategory:

Given a Graph $G$ and a map $s:V(G)\to X$ you can push forward the graph structure on $V(G)$ to a graph structure $s_*G$ on $X$ by defining $$(x,x')\in E(s_*G):\Leftrightarrow \exists(v,v')\in E(G):sv=x,sv'=x'.$$ Now do this for the maps $\overline{s}:V(G)\to\mathrm{im}(s)\subset \mathbb N$. This defines a functor $\mathrm{FinGrph}/\mathsf{blob}(\mathbb N)\to \mathcal G_1$ left-adjoint to the obvious inclusion functor. (This is due to $s_*G$ being the final graph structure on $X$ for the map $s$.)

The permutation functor $F_\pi$ then appears by postcomposition with $\pi$ by mapping $s:G\to\mathsf{blob}(\mathbb N)$ to $\mathsf{blob}(\pi)\circ s$.

  • $\begingroup$ What does blob stand for? $\endgroup$ Aug 1 '13 at 21:51
  • $\begingroup$ Given a set $X$ we define the graph $\mathsf{blob}(X):=(X,X\times X)$. It has the universal property $$\mathrm{Set}(V(G),X)=\mathrm{Graph}(G,\mathsf{blob}(X)).$$ $\endgroup$ Aug 2 '13 at 18:10
  • $\begingroup$ Thanks. But why did you (or who else?) choose the name "blob"? $\endgroup$ Aug 4 '13 at 7:50
  • $\begingroup$ I guess this is only my notation: I think of graphs as special (quasi-)ordered Sets (Sets with a reflective, transitive but not necessairily antisymmetric relation). In quasiordered sets there might be 'thick points': Clusters of order-equivalent points/vertices. I call $(X,X\times X)$ a blob because it is just a thick point. $\endgroup$ Aug 4 '13 at 11:24

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.