Infinite core graphs

Solution 1:

This example is based on the related example of a presheaf whose endomorphisms are epic which you provided on the Category Theory Zulip channel.

Consider the graph with vertices indexed by $\mathbb{Z} \sqcup \mathbb{N}_{>0}$, with the former labelled as $(m,0)$ and the latter as $(n,1)$. Let there be edges $(m,0) \to (m+1,0)$ and $(n,1) \to (n+1,1)$ for every $m,n$, plus an edge $(0,0) \to (1,1)$, and no other edges. In other words, we have an infinite forked path.

As is, there are some non-epimorphic endomorphisms, namely those which map one of the branches onto the other. To fix this, we add edges $(m,0) \to (m+2,0)$ for all even $m$, $(m,0) \to (m+3,0)$ for all $m$ which are negative multiples of $3$, $(n,1) \to (n+3,1)$ for $n$ which are multiples of $3$, and one more edge $(0,0) \to (3,1)$. Near the fork, the resulting graph looks something like this... Now any endomorphism must pull the paths down by a multiple of $6$, and branches cannot be translated onto one another, because the graph structure is very rigid: with no directed loops available, any endomorphism must preserve the triangles and squares of edges.

I think the real trick here was taking advantage of the fact that the endomorphisms are required to be just surjective and not locally surjective.

I might as well note down a couple of observations about "core" graphs which I found on the way to this example.

Any such graph which has more than one vertex can have no self-edges, since if there is an edge $v \to v$ in $G$, there is an endomorphism of $G$ sending every vertex to $v$ and every edge to this loop which is thus not surjective. Thus whenever there is an edge $x \to y$, we must have $f(x) \neq f(y)$, which was certainly an obstacle to constructing examples with non-injective endomorphisms.

Now consider the connected subgraphs of $G$. There can be no graph homomorphism between any pair of these, since we could extend any such by the identity to obtain an endomorphism of $G$ which is not surjective. As such, every endomorphism of $G$ restricts to endomorphisms of the connected components, which means that each component is itself core.