3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ilya Bogdanov Dec 30 '18 at 10:55
  • $\begingroup$ Can you elaborate a bit more? I'd really appreciate it. $\endgroup$ – Ethan Dec 30 '18 at 11:10
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.