7
$\begingroup$

Let $G$ be a graph. A graph $C$ is a core of $G$ if:

  1. There is a homomorphism $G \to C$.
  2. There is a homomorphism $C \to G$.
  3. $C$ is smallest possible with these properties.

A core graph is well-defined up to isomorphism for any finite graph $G$. One can see that under these restrictions $C$ is a subgraph of $G$ (since otherwise the image of $C \to G$ must be a smaller graph with all these properties), and is its own core. Further, we may equivalently replace 3 with:

3'. All endomorphisms of $C$ are isomorphisms.

3' is one of the main reasons why core graphs are a useful notion (see references in the article above), so it is interesting to seek for similar objects in other categories. Let us define a core of an object $G$ as any $C$ satisfying 1, 2 and 3'.

In any category with an object $X$ both initial and terminal, $X$ is trivially a core of any object (as in $\mathbf{Grp}$, $\mathbf{Mon}$, or $\mathbf{Vect}_K$). In $\mathbf{Field}$ any object is a core of itself since any homomorphism is injective. In both of this situations the cores are kinda trivial. We could say that in the first case objects have too 'admissive' internal structure, while in the latter case objects have too 'restrictive' internal structure.

$\mathbf{Graph}$ is an example of a category with "meaningful" cores, that is, different graphs may have different cores, and there are graphs that are not cores of themselves. In $\mathbf{Ring}$ cores may be meaningful too: for example, the core of $\mathbb{Z}_n \times \mathbb{Z}_m$ is $\mathbb{Z}_{\mathrm{lcm}(n, m)}$.

Questions: In which (concrete) categories cores are meaningful? In which categories cores are defined up to isomorphism?

Late edit: Another aspect of how graph cores are interesting is that they are hard to compute (see above reference). Naturally, if cores of a category are computationally hard, then they must be meaningful in the above sense, and it feels like a good way to encapsulate their 'interestingness'. Can we say something about categories with computationally hard cores?

$\endgroup$
4
  • $\begingroup$ I feel like the definition is missing something essential -- you seem to have some idea of a canonical choice of ordering, or at least expecting the ordering to have some properties, and maybe even want a restriction on $C$. $\endgroup$
    – user13113
    Commented Oct 31, 2017 at 9:17
  • $\begingroup$ As an example of the oversight, in your example of a category with a zero object $X$, the cores (of everything) are precisely the minimal objects with respect to your chosen ordering, and the zero objects need not be minimal. $\endgroup$
    – user13113
    Commented Oct 31, 2017 at 9:18
  • $\begingroup$ I sort of feel like asking for a minimal $C$ is a red herring; that what you really care about is the equivalence class, and asking for a representative is maybe done out of habit rather than because it's a good idea. This even has a nice categorical interpretation of truncating your category to become a preorder by identifying parallel arrows, and then extracting the subcategory of invertible arrows, which gives a setoid. (the subcategory of invertible arrows is what category theorists usually call the core of a category) $\endgroup$
    – user13113
    Commented Oct 31, 2017 at 9:22
  • $\begingroup$ @Hurkyl You are right in pointing out that "minimalness" is rather incosistent. I guess the key property of a core graph is that all of its endomorphisms are invertible (in graphs this is equivalent to being smallest in its homeomorphic equivalence class). $\endgroup$ Commented Oct 31, 2017 at 9:38

1 Answer 1

3
$\begingroup$

I think of the core phenomenon as a special case of a basic fact about finite transformation monoids. Suppose we have a concrete category of finite structures such that bijective endomorphisms are isomorphisms and the image of each endomorphism is a substructure. Then for each object $X$ there is a subject $Y$ which is a retract of $X$, any endomorphism of $Y$ is an isomorphism and $Y$ is unique up to isomorphism. Moreover, $Y$ is of minimal cardinality among images of a morphism from $X$ to itself.

Why? Let $M$ be the endomorphism monoid of $X$. Define the rank of an element of $M$ to be the cardinality of its image. Let $m\in M$ have minimal rank $r$. Then all powers of $m$ have the same rank and hence there is an idempotent $e$ achieving the rank $r$. Let $Y=eX$. Then $Y$ is a retract of $X$. If $f$ is an endomorphism of $Y$, then $ife$ (where $i$ is the inclusion) is an endomorphism of $X$ and so by minimality of the rank of $e$, we have that $|eX|=|Y|\leq |fY|=|feX|\leq |eX|=|Y|$ and thus $f$ is an automorphism of $Y$ by our hypotheses.

Suppose $Z$ is another retract of $X$, say by an idempotent $e'$, such that every endomorphism of $Z$ is an isomorphism. Then $e'|_Y\colon Y\to Z$ and $e|_Z\colon Z\to Y$ are morphisms by restriction and hence $e|_Ze'|_Y$ is an automorphism of $Y$ and $e'|_Ye|_Z$ is an automorphism of $Z$. It easily follows that $e'_Y$ is an isomorphism from $Y$ to $Z$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .