3
$\begingroup$

It is fun to recognize that the $n$-colorable graphs are exactly those graphs $X$ in the category of simple graphs with an homomorphism to the complete graph $K_n$.

Question 1: Are there other families of objects $Y$ in other categories - comparable with the complete graphs - such that the objects $X$ with a morphism to some $Y$ in this family are interesting enough to have a proper name (like "$n$-colorable graphs")? For example in the category of groups?

It seems natural to generalize the concept of colorability (in the first instance for graphs): Let a graph $G$ be $H$-colorable when there is a homomorphism from $G$ to $H$. The - arbitrary - graph $H$ defines which "colors" are allowed to be neighbours in a $H$-colored graph, and thus plays the role of a sort of a "grammar".

Question 2: Under which name has this generalization of colorability been investigated?


Question 3: Are there other categories - inhabited by a family of objects as in Question 1 - such that any target $Y$ can be understood as some kind of a "grammar" (as for graphs)?

$\endgroup$
2
$\begingroup$

Oh, yes! Basically you ask if the objects of comma categories $\mathcal{C} / S$ have a special name. They are called the objects "over $S$" and often can be thought of "objects parametrized by $S$". Namely, if $X \to S$, one may think (if there are enough "points" and pullbacks exist) that $X$ is approximated by the fibers $X_s$ for points $s$ of $S$. In the case of $\mathcal{C}=\mathsf{Grph}$ and $S=K_n$, the fiber of a color $s$ is the subgraph with that color. If $\mathcal{C} = \mathsf{Sch}$ is the category of schemes, a scheme over $S$ is also called an $S$-scheme or relative scheme over $S$. The relative point of view on algebraic geometry has been developed and exploited by Alexander Grothendieck and his students. It is also important in other contexts, for example Grothendieck fibrations and (fiber, vector, principal, ...) bundles.

$\endgroup$
1
$\begingroup$

There is a very large literature, including at least one book (Hell and Nesetril), on the subject of graph homomorphisms. This topic has always been viewed in part as an extension of the idea of graph colouring. The categorical view has not proved especially fruitful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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