Endofunctors of graph categories

Question

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?

Answer 1

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