# Generalized digraph homomorphisms and graph cores

Given any digraphs $$G$$ and $$H$$ we say a surjection $$f:V(G)\to V(H)$$ reduces $$G$$ to $$H$$ if and only if it satisfies $$(u,v)\in E(G)\iff (f(u),f(v))\in E(H)$$. Where if there exists at least one surjection that reduces $$G$$ to $$H$$ then we refer to $$H$$ as a reduction of $$G$$ and write $$H\preceq G$$. Thus by this definition we see $$\preceq$$ forms a pre-order and in fact a partial order with respect to isomorphism classes of digraphs as $$\small(G\preceq H)\land (H\preceq G)\implies G\cong H$$. Lastly we call any digraph $$D$$ irreducible if and only if every reduction of $$D$$ is isomorphic to $$D$$.

With that said does every finite digraph have a unique (up to isomorphism) irreducible reduction?

• Say two vertices are equivalent iff their out-edges go to the same set of vertices, the same for in-edges. The equivalence classes are the vertices of the unique maximal reduction. – Ilya Bogdanov Dec 30 '18 at 10:55
• Can you elaborate a bit more? I'd really appreciate it. – Ethan Dec 30 '18 at 11:10

First I claim any reduction of $$G$$ is isomorphic to an induced subgraph. Indeed if $$G$$ maps onto $$H$$ by $$f$$ choose a minimal size induced subgraph $$G'$$ of $$G$$. If $$f$$ identifies $$v,w$$ then they have the same edges going into both $$v$$ and $$w$$ by your definition of reduction. So we can drop one of these vertices from $$G'$$ contradicting minimality. Thus we need to show that $$G$$ has a unique up to isomorphism minimal sized retract. (We can use every map has an idempotent power to reduce to retracts).
Let $$M$$ be the endomorphism monoid of your digraph. Then being a finite monoid it has a unique minimal ideal $$K$$ consisting of the endomorphisms with minimal size image. This ideal contains idempotents. If $$e\in K$$ is an idempotent, the $$e(G)$$ is an irreducible reduction (since a reduction of $$e(G)$$ would by the first paragraph give a smaller sized quotient subgraph of $$G$$) and any irreducible reduction is of this form for some idempotent in $$K$$. By basic theory of finite transformation monoids if $$e,f\in K$$ are idempotents, then $$e(G)$$ and $$f(G)$$ are isomorphic. More precisely there are $$a\in eMf$$ and $$b\in fMe$$ with $$ab= e$$ and $$be=f$$ and $$b$$ and $$a$$ give the inverse isomorphisms.