5
$\begingroup$

I was fooling around with some concept and was wondering if this viewpoint is explored at all. Let INJ-GRAPH be the subcategory of graphs (with morphisms as homomorphisms) whose morphisms consist only of the graph homomorphisms which are injective as sets. Then clearly for such a homomorphism $f : G \to H$ of graphs, the chromatic number of $H$ is at least as large as the chromatic number of $G$. Thus one gets a covariant functor from INJ-GRAPH to the order category of $\mathbb{N}$ (i.e. the category whose objects are natural numbers and there is a unique arrow $a \to b$ if and only if $a \leq b$)

What's more is that this functor preserves coproducts. Indeed the coproduct of two graphs is given by the disjoint union of the graphs, and the chromatic number of this graph is the maximum of the chromatic number of the two graphs. I'm unsure if it preserves more general colimits, but I think at least if they are small then it should be ok.

Anyway, the question is, has this kind of category-theoretic reasoning been investigated in the literature? It currently seems like abstract nonsense, but perhaps it is indicative of something deeper.

$\endgroup$
4
$\begingroup$

Sure, category theorists know such things, but I think for the difficult results that graph theorists care about, the generalities of category theory may at best help as an organizing principle. This is a bit similar to the theory of combinatorial species, which is a way of doing combinatorics inspired by category theory.

Here are some other basic observations, you can read more about such things in Lawvere's Qualitative distinctions between some toposes of generalized graphs, Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemporary Mathematics, 261–299. American Mathematical Society.

The category of directed graphs is a presheaf topos on the site consisting of two parallel arrows (so that a presheaf is given by two sets $E$ and $V$ and maps $t : E \to V$ and $s : E \to V$), see A Guided Tour in the Topos of Graphs by Sebastiano Vigna.

For any given $n$, the category of $n$-colored graphs is a topos, because it is just the slice of the topos of graphs over the complete graph on $n$ vertices (an $n$-coloring of $G$ is just a morphism $G \to K_n$).

As Lawvere explains, several other categories of graphs are toposes because they are (equivalent to) toposes of monoid actions for a suitably chosen $M$. Let's just do one. Consider the monoid $M$ of endomaps on $2 = \{0,1\}$. There are four maps $2 \to 2$, we give them names: the identity map $i$, the constant map $0$, the constant map $1$, and the twist map $t$.

An object in the topos of $M$-sets is a set $S$ with a right $M$ action, which is a map $s : S \times M \to S$ satisfying $s(x, i) = x$ and $s(x, f \circ g) = s(s(x, f), g)$. Since there are only four elements in $M$, we might as well figure out what this means. Let $S_0 = \{x \in S \mid \exists y \in S \,.\, x = s(y, 0)\}$ be the set of those elements of $S$ that arise as actions of~$0$. We define $S_1$ similarly. Because $0 \circ g = 0$, it follows for every $g \in M$ and $x \in S_0$ that $$s(x, g) = s(s(y,0), g) = s(y, 0 \circ g) = s(y, 0) = x.$$ So, the elements of $S_0$ are fixed by the action. Similarly, the elements of $S_1$ are fixed by the action.

To every $M$-set $(S,s)$ we associate a graph $G_S$ as follows. The vertices of $G_S$ are the elements of $S_0 \cup S_1$. The half-edges of $G_S$ are the elements of $S$. Given a half-edge $e \in S$, its source is the vertex $s(e, 0)$. The opposite half-edge of $e$ is $S(e, t)$, and because $t \circ t = 1$, tit follows that the opposite of the opposite is the original half-edge. An edge is a half-edge together with its opposite. The target of a half-edge is the source of its opposite half-edge, i.e., the target of $e$ is $s(s(e,t),0) = s(e,1)$. (There is an anomaly which we allow: a half-edge may be its own opposite.)

What sort of graphs did we get? They are symmetric graphs in which each edge consists of two half-edges. An edge may be degenerate when it is composed of two copies of the same half-edge. In addition, the graphs are reflexive in the sense that each vertex has a distinguished degenerate loop starting and ending at the vertex (this is because $S_0 \cup S_1 \subseteq S$).

Exercise: figure out what the morphisms are, and then show that the description in terms of reflexive symmetric graphs gives a category that it equivalent to the topos of $M$-sets.

Is this the sort of thing you were asking about?

$\endgroup$
  • $\begingroup$ Yes, I was just interested broadly in whether the principles one can apply from category theory have been formalized to the study of graphs in some way. I wasn't sure what to expect, and this was definitely interesting! $\endgroup$ – MCT May 12 '18 at 15:31
  • $\begingroup$ Here's another observation which I worked out once: the directed graphs that satisfy the principle of choice are precisely those whose in -and out-degrees are bounded by 1 (so every vertex has at most one edge coming in, and at most one edge coming out). Therefore, such graphs must be disjoint sums of cycles and paths. $\endgroup$ – Andrej Bauer May 12 '18 at 19:40
  • $\begingroup$ What do you mean by the principle of choice? $\endgroup$ – MCT May 13 '18 at 19:43
  • 1
    $\begingroup$ An object $X$ satisfies choice if for all $Y$ and $R$, $(\forall x \in X \exists y \in Y . R(x,y)) \Rightarrow \exists f \in Y^X \forall x \in X . R(x, f(x))$ in the internal language of the topos. This is equivalent to $X$ being internally projective, and is equivalent to the functor ${-}^X$ preserving epis. $\endgroup$ – Andrej Bauer May 14 '18 at 9:56
  • 1
    $\begingroup$ I forgot to say that this is the topos-theoretic way of saying that an objects $X$ satisfies choice when every $X$-indexed family of inhabited sets has a choice function. For instance, countable choice is the same thing as $\mathbb{N}$ satisfying choice. $\endgroup$ – Andrej Bauer May 14 '18 at 10:50
4
$\begingroup$

I'm not sure about your connection to the natural number category, but there has definitely been some investigation of using the category of graph homomorphisms to describe colorings. See in particular this wikipedia page which describes colorings as homomorphisms to the complete graph, and formulates the GHRV theorem as a statement in the category of homomorphisms of directed graphs: a directed graph has a homomorphism to a $k$-vertex transitive tournament if and only it does not have a homomorphism from a $(k+1)$-vertex path.

$\endgroup$
  • $\begingroup$ See also this post by Tom Leinster at the n-Category Café. $\endgroup$ – Tobias Fritz May 12 '18 at 11:58
  • $\begingroup$ It's also fascinating that the categorical dual gives the clique number: the homomorphisms $K_n\to G$ are exactly the $n$-cliques in $G$. $\endgroup$ – Tobias Fritz May 12 '18 at 12:00
  • 2
    $\begingroup$ But has anyone actually sovled an interesting graph theoretic problems using this stuff? $\endgroup$ – Andrej Bauer May 12 '18 at 19:38

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.