Generalized digraph homomorphisms and graph cores

Question

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?

Answer 1

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

The rest is basic semigroup theory.

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.

This is equivalent @IlyaBogdanov's answer.