Colouring a Graph

April 12, 2013

Posted by Tom Leinster

$MathML-enabled post (click for more details).$

It had always seemed to me that category theory provided no useful perspective on graph theory. But yesterday I learned a small fact that caused me to slightly revise that opinion. It’s that colourings of graphs — which seem to be a major source of questions in graph theory — are simply homomorphisms into a complete graph.

I’ll explain this, and I’ll describe a conjecture that Tom Hirschowitz told me about yesterday: for graphs $G$ and $H$ ,

The chromatic number of $G \times H$ is the minimum of the chromatic numbers of $G$ and $H$ .

It’s amazing that something so basic is unknown!

$MathML-enabled post (click for more details).$

For this post, a graph is a finite set equipped with a symmetric, irreflexive binary relation. The elements of the finite set $V$ are called the “vertices”, the relation is usually called $E$ , and rather than saying that two vertices are related, we say that there is an “edge” between them. Concretely, then, “graph” means a finite undirected graph without loops (that being the “irreflexive” part) or multiple edges.

For instance, for each natural number $n$ , the complete graph $K_n$ has vertex-set $\{1, \ldots, n\}$ and an edge between $i$ and $j$ whenever $i \neq j$ .

A homomorphism of graphs is what you’d imagine. That is, given graphs $G = (V, E)$ and $G' = (V', E')$ , a homomorphism $G \to G'$ is a map of sets $f\colon V \to V'$ such that for $x, y \in V$ ,

$(x, y) \in E \implies (f(x), f(y)) \in E'.$

This gives us a category of graphs.

Graph theorists know a lot about colourings. By definition, a colouring of a graph $G$ by $n$ colours, or an $n$ -colouring of $G$ for short, is a way of painting each vertex one of $n$ colours in such a way that no two vertices of the same colour have an edge between them.

Here’s the small fact I learned yesterday (from Wikipedia):

A $n$ -colouring of a graph $G$ is the same thing as a homomorphism $G \to K_n$ .

Why? Well, writing $G = (V, E)$ , a homomorphism $G \to K_n$ is a map of sets $f\colon V \to \{1, \ldots n\}$ such that if $x, y \in V$ have an edge between them then the vertices $f(x)$ and $f(y)$ of $K_n$ have an edge between them. But every pair $(i, j)$ of vertices of $K_n$ is joined by an edge except when $i = j$ . So a homomorphism $G \to K_n$ is a map of sets $f\colon V \to \{1, \ldots, n\}$ such that if $x$ and $y$ are joined by an edge then $f(x) \neq f(y)$ . That’s exactly an $n$ -colouring.

This fact makes it obvious that colouring is functorial: given a homomorphism $f\colon G \to H$ , every $n$ -colouring of $H$ gives rise to an $n$ -colouring of $G$ . (Simply compose the maps $G \to H \to K_n$ .) Concretely, we paint each vertex $x$ of $G$ the same colour as $f(x)$ .

Every graph can be $n$ -coloured for sufficiently large $n$ : just paint all the vertices different colours. The chromatic number $\chi(G)$ of $G$ is the smallest $n$ for which there exists an $n$ -colouring of $G$ .

The functoriality of colouring means that $\chi(G) \leq \chi(H)$ whenever there is a homomorphism $G \to H$ . Categorically put, $\chi$ is a functor $\chi \colon Graph \to (\mathbb{N}, \leq).$

Here $(\mathbb{N}, \leq)$ is the poset $\mathbb{N}$ regarded as a category: it has one object for each natural number, there is one map $m \to n$ when $m \leq n$ , and there are no maps $m \to n$ when $m \gt n$ .

The very famous four-colour theorem states that the chromatic number of a planar graph is at most four. For a long time it was only a conjecture. But there’s another fundamental conjecture about chromatic numbers — perhaps even more fundamental, as it doesn’t refer to the geometric notion of planarity. Tom Hirschowitz mentioned it to me by email yesterday; he’d just heard it from Stéphan Thomassé. Here goes.

The category of graphs has binary products, defined in the expected way: given graphs $G = (V, E)$ and $H = (W, F)$ , the vertex-set of $G \times H$ is $V \times W$ , and there’s an edge between $(v, w)$ and $(v', w')$ if and only if there are an edge between $v$ and $v'$ and an edge between $w$ and $w'$ . The projections $G \times H \to G$ and $G \times H \to H$ are what you’d expect.

Now, the fact that there are any homomorphisms $G \times H \to G$ implies that $\chi(G \times H) \leq \chi(G)$ . The same goes for $H$ . So:

$\chi(G \times H) \leq \min\{ \chi(G), \chi(H) \}$ for all graphs $G$ and $H$ .

The conjecture is that this is an equality:

Conjecture (Hedetniemi, 1966) $\chi(G \times H) = \min \{ \chi(G), \chi(H)\}$ for all graphs $G$ and $H$ .

It’s known to be true for various classes of $G$ s and $H$ s, and I guess people have had their computers check it in millions of special cases. As I only learned about it yesterday, I know almost nothing more — only what I’ve read on Wikipedia and this page by Stéphan Thomassé. But presumably a question this basic, open since 1966, has attracted a lot of attention.

Intuitively (as Wikipedia says) the meaning of the conjecture is that $G \times H$ has no sneakily economical colourings. In other words, if your aim is to colour $G \times H$ with as few colourings as possible, you can’t improve on the following strategy: either colour $G$ minimally and then declare the colour of $(x, y) \in G \times H$ to be the colour of $x \in G$ , or do the same with the roles of $G$ and $H$ reversed.

Categorically, the conjecture can be expressed as follows:

Conjecture (Hedetniemi) The functor $\chi: Graph \to (\mathbb{N}, \leq)$ preserves binary products.

That’s just because binary products in the category $(\mathbb{N}, \leq)$ are minima.

Postscript: Perturbing the definition

In what I wrote above, I tried to stick closely to what I understand to be graph theorists’ conventions, except of course that some things are phrased in categorical language. I don’t know nearly enough graph theory to challenge the wisdom of those conventions.

However, I can’t help wondering whether things would become cleaner if we allowed our graphs to have loops. Formally, a graph-with-loops is a finite set equipped with a symmetric binary relation. Thus, what we’re calling a “graph” is a special sort of graph-with-loops: it’s a graph-with-loops with no loops! Formally, it’s a graph-with-loops in which the relation is irreflexive.

Homomorphisms of graphs-with-loops are defined just as for ordinary graphs, and products are described in the same way too. Thus, $Graph$ is a full subcategory of $Graph_\text{L}$ , the category of graphs-with-loops, and the inclusion preserves binary products.

Why allow loops? The reasons are aesthetic.

First, the irreflexivity condition tastes strange on a category theorist’s tongue. We’re suspicious of negatives.

Second, the category of graphs has the strange feature of possessing binary products but not a terminal object. This is “fixed” (if you think it’s a problem) by passing to the category of graphs-with-loops, in which the terminal object is the graph consisting of a vertex and a single loop on it.

Third, there’s a general rule, discussed at the Café before (though I can’t find it now) and possibly due to Grothendieck:

A good category containing some bad objects is preferable to a bad category containing only good objects.

I’m not keen on the words “good” and “bad” in mathematics, but I understand the intent. For instance, the rule tells us to work with the category of schemes rather than the category of varieties. The category of varieties is “bad” in lacking certain colimits, for example; but from the traditional point of view, some schemes are “bad”. Similarly, it suggests that categories of smooth spaces are preferable to categories of manifolds.

In our present situation, the presence of loops might be thought to make a graph “bad”, but allowing such graphs makes the category good.

One way in which a graph containing loops is “bad” is that it has no colourings at all. If a vertex $x$ has a loop on it, then there’s an edge between $x$ and $x$ , so there’s no colour you can give it. Thus, the chromatic number of a graph containing one or more loops should be taken to be $\infty$ . Chromatic number therefore defines a functor

$\chi\colon Graph_\text{L} \to \mathbb{N} \cup \{\infty\}.$

The category $\mathbb{N} \cup \{\infty\}$ is also “better” than $\mathbb{N}$ : unlike $\mathbb{N}$ , it has a terminal object (greatest element), $\infty$ . Since $1$ , the terminal graph-with-loops, contains a loop, we have $\chi(1) = \infty$ . That is, $\chi$ preserves terminal objects. So it preserves binary products if and only if it preserves all finite products.

Actually, there’s something funny going on. A loop in a graph $G$ is a homomorphism $1 \to G$ . In categories of spaces, a map from the terminal object to a space $X$ is often called a point of $X$ . So, loops are points. This means that the graphs without loops — the “good” graphs — are exactly the graphs without points! What’s funny is that in some categories of spaces, such as the category of locales, the nontrivial spaces with no points at all tend to be seen as rather exotic. (For example, there’s the locale of surjections $\mathbb{N} \to \mathbb{R}$ , which is nontrivial but has no points.)

Hedetniemi’s conjecture is straightforward when $G$ or $H$ contains a loop. For if $G$ contains a loop then we have a homomorphism $1 \to G$ , which induces another homomorphism

$H \cong 1 \times H \to G \times H.$

So $\chi(H) \leq \chi(G \times H)$ . (Concretely, if $G$ contains a loop on a vertex $x$ then $\{x\} \times H \subseteq G \times H$ is an isomorphic copy of $H$ contained in $G \times H$ .) But we also know that $\chi(G \times H) \leq \chi(H)$ ; so $\chi(G \times H) = \chi(H)$ . Since $\chi(G) = \infty$ , this is exactly what Hedetniemi’s conjecture predicts.

So the conjecture can equivalently be reformulated as:

Conjecture (Hedetniemi) The functor $\chi\colon Graph_\text{L} \to \mathbb{N} \cup \{\infty\}$ preserves finite products.

At first glance this looks harder than the previous versions, since $Graph_\text{L}$ is a larger category and we’re asking for the preservation of terminal objects as well as binary products. But the observations above show that it’s actually equivalent.

Here’s a final question. The chromatic number functor is defined in terms of the complete graphs $K_n$ . But what’s so special about the $K_n$ s? What is their place within the category of graphs? I see no nice universal property that complete graphs satisfy. They look “indiscrete”, so at first I looked for some universal property similar to that satisfied by indiscrete topological spaces or indiscrete categories. But no — you have to be careful about the lack of loops. Perhaps the interplay of perspectives between $Graph$ and $Graph_\text{L}$ is somehow helpful here.

Posted at April 12, 2013 12:54 AM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2610

55 Comments & 0 Trackbacks

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

I too find it a little perplexing that there has been little interaction between graph theory and category theory, so this is a welcome post.

Regarding “the” category of graphs: something that’s a little bit amusing is that if you forget about morphisms for a moment, then graphs as you defined them at the beginning (sets equipped with irreflexive symmetric relations) are sort of “the same thing” as sets with reflexive symmetric relations, in the sense that there is a canonical bijection between such structures (they are in fact isomorphic as Joyal species). But they are very different of course from the viewpoint of structure-preserving functions! One thing that reflexive symmetric relations support and irreflexive symmetric relations do not is the process of contracting an edge to a point, which seems to be a prominent operation in at least some aspects of Graph Theory.

I believe it is true that both the category of sets equipped with a symmetric relation, and the category of sets equipped with a reflexive symmetric relation, are quasitoposes (I’d have to double-check that). But the category of sets equipped with an irreflexive symmetric relation is not. This would sort of confirm the intuition that there’s something categorically “fishy” or not-good-smelling about the negative condition of irreflexivity.

Posted by: Todd Trimble on April 12, 2013 2:29 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Re contracting an edge to a point, if we want to do that then maybe it’s best to allow multiple edges as well as loops. For example, look at this picture of someone computing a Tutte polynomial. Starting at the graph at the top of the picture and heading south-east to the next graph, what we’re doing is contracting the edge in the middle. Doing so creates multiple edges.

Posted by: Tom Leinster on April 12, 2013 11:25 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

One of the standard, interesting things to do with graph colorings is to compute the number of them with n colors, the “chromatic polynomial” in n. I wonder if it would be interesting to count maps into a complete graph with n vertices, m of which have self-loops.

Posted by: Allen Knutson on April 12, 2013 3:42 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

That does sound like it could be interesting. Do you have any instinct as to whether this is going to be a polynomial in $n$ and $m$ , or even a polynomial in $n$ for a fixed value of $m$ ?

Posted by: Tom Leinster on April 12, 2013 11:21 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Thinking through the keyboard… Let’s give the name $\chi_G$ for the chromatic polynomial of $G$ , and $\chi_G(n,m)$ for this generalization, where we assume $m\leq n$ for the moment.

Allowing all $n$ colours to be self-adjacent, there are $n^V$ colourings, so the function $\chi_G(n,m)$ is bounded by a polynomial in $n$ . A colouring allowing the first $m$ colours to be self-adjacent corresponds exactly to

a choice of full subgraph $S \triangleleft G$
an $n-m$ -colouring of $G - S$ of which there are $\chi_{G-S}(n-m)$ , a polynomial in $m$ and $n$ .
a function $V_S \to m$ of which there are $m^{V_S}$ , again a polynomial

So, yes, $\chi_G(n,m)$ is a polynomial; I think this argument works even when $G$ is allowed self-loops, because $0$ is still a polynomial.

Posted by: Jesse C. McKeown on April 12, 2013 8:23 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

My initial reaction to the last paragraph of the post was that surely in the category of ‘graph-with-loops’, the ‘complete graphs’ should actually be complete in the context-appropriate sense, and hence have loops at every vertex? That would also prevent infinite chromatic numbers.

Posted by: Mike Shulman on April 13, 2013 5:51 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

The trouble with ‘complete graphs’ that have a loop at every vertex is that homomorphisms into them are too trivial; hence the interesting questions about graph colouring go away.

Posted by: Tom Leinster on April 13, 2013 12:45 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

As an aside, I would like to point out that there has been an application of chromatic numbers to algebraic topology. D.J. Anick proved that computing the rational homotopy groups of some contrived finite simplicial complexes is equivalent to determining some chromatic numbers of graphs. As a corollary one can conclude from computer science that computing rational homotopy groups of finite simplicial complexes is #P hard. There have been a number of results since then relating problems in rational homotopy theory to computing chromatic numbers of graphs.

Posted by: Jeremy Hahn on April 12, 2013 4:10 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Oh, that’s how he did it? I’m glad to hear it; so far, anything written by Anick I find hard to read.

Posted by: Jesse C. McKeown on April 12, 2013 4:45 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Can’t one call self loops “identities” and establish an n-coloring of a graph with loops via an identity reflecting homomorphism to $L_n$ , the complete graph with self loops (all identities)?

Or does this just push the distinctness problem back into the homomorphism?

Also, “hom”s seem an appropriate language to discuss graphs. Graphs with loops are those enriched in 2 while $L_n$ s are enriched in 1, and one can use hom definitions to define sub categories of $Graph_L$ . For example the functor $irefl : Graph_{L} \to Graph$ that forgets identities can be defined as:

$hom(irefl(a),irefl(b)) = not(equal(a, b)) \wedge hom(a,b)$

At the worst I hope I’ve said true things that really don’t help.

Posted by: RodMcGuire on April 12, 2013 6:43 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Part of the problem might be that the product of graphs seems to have no clear geometric meaning. For example $K_2$ looks like an interval so I would expect $K_2 \times K_2$ to resemble a square but instead it is a disjoint union of two $K_2$ s. If you allow loops then this product would be a square with both diagonals (previously there were only the diagonals) which is perhaps more geometrically intuitive.

Graphs can be seen as (unordered) 1-dimensional simplicial complexes so surely some people considered the question of how the product of graphs behaves with respect to geometric and homotopy theoretic properties of graphs regarded as simplicial complexes. Is anything known about this?

Posted by: Karol Szumiło on April 12, 2013 6:47 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

The construction you want is called the Cartesian product of graphs (confusingly, it is not the categorical product in the category of graphs).

Posted by: Qiaochu Yuan on April 12, 2013 7:18 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

As Qiaochu mentions, the terminology is highly confusing for someone more familiar with category theory than graph theory.

What graph theorists call the tensor product $\times$ of graphs is the product (in the categorical sense) in the category of graphs. So, it’s what category theorists might call the cartesian product, for emphasis. But…

What graph theorists call the cartesian product $\square$ of graphs (which I’ll define in a minute) is not the product in the categorical sense. But it does define a monoidal structure on the category of graphs, so it’s what category theorists might call a tensor product…

I’ll call $\square$ the “box product” in an attempt to avoid confusion. The definition may remind category theorists of the Gray tensor product or the so-called “funny tensor product”. Given graphs $G = (V, E)$ and $H = (W, F)$ , the vertex-set of $G \square H$ is $V \times W$ , and there is an edge between $(v, w)$ and $(v', w')$ if and only if:

either $v = v'$ and there is an edge between $w$ and $w'$
or vice versa.

The Wikipedia page notes that the box product is associative up to canonical isomorphism. It also has a unit (up to canonical isomorphism), namely, the graph with a single vertex and no edges.

It’s pointed out there that the symbol $\square$ depicts the box product of two copies of the edge graph $K_2$ . Magically, the symbol $\times$ also depicts the categorical product of two copies of $K_2$ ! As Karol observes, $K_2 \times K_2$ is the disjoint union of two edges, but if you draw it in the natural way, the two edges cross over, so it looks like an X.

There’s an intriguing counterpart to Hedetniemi’s conjecture:

Theorem (Sabidussi, 1957) $\chi(G \square H) = \max \{\chi(G), \chi(H)\}$ for all graphs $G$ and $H$ .

This suggests some kind of duality between $\square$ and $\times$ . I guess this thought has occurred to almost everyone who’s seen both Sabidussi’s theorem and Hedetniemi’s conjecture, but I have no idea whether there’s anything in it.

Posted by: Tom Leinster on April 12, 2013 11:03 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Those constructions remind me of things that linear logicians do with ‘coherence spaces’.

Posted by: Mike Shulman on April 13, 2013 5:53 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

“and this page by Stéphan Thomassé.”

links to Wikipedia, not Thomassé. Did you mean this low content page?

Posted by: RodMcGuire on April 12, 2013 8:04 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Oops, you’re quite right: that’s exactly what I meant. Thanks. I’ve fixed it now.

Although it’s very brief, I learned two things from that page. The first is that even a much weaker form of the conjecture is unproved (in his notation: $\sup g = \infty$ ). The second is his last sentence.

Posted by: Tom Leinster on April 12, 2013 10:38 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

A few days ago there was a question on stackexchange about graph theory and category theory http://math.stackexchange.com/questions/352020/why-should-a-combinatorialist-know-category-theory

Posted by: GHGH on April 12, 2013 9:43 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

There’s also a link there to a paper called Adjoint functors in graph theory.

Posted by: Tom Leinster on April 13, 2013 12:46 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

At the end of the post, I wrote:

The chromatic number functor is defined in terms of the complete graphs $K_n$ . But what’s so special about the $K_n$ s? What is their place within the category of graphs? I see no nice universal property that complete graphs satisfy.

Here’s an answer, though maybe not a completely satisfactory one.

A homomorphism between complete graphs is simply an injection between the vertex-sets. Hence the full subcategory of $Graph$ determined by the $K_n$ s is equivalent to the category of finite sets and injections.

Better, there’s an adjunction here. Write $Graph^{inj}$ for the category of graphs and injective homomorphisms, and $FinSet^{inj}$ for the category of finite sets and injections. There’s a forgetful functor $U: Graph^{inj} \to FinSet^{inj}$ , and it has a right adjoint, which sends a finite set to the complete graph on it:

$U \colon Graph^{inj} \stackrel{\longrightarrow}{\leftarrow} FinSet^{inj} \colon K$

Why? Let $G$ be a graph and $I$ a finite set. An injective homomorphism from $G = (V, E)$ to the complete graph $K_I$ with vertex-set $I$ is an injection $f\colon V \to I$ such that whenever there is an edge between $x$ and $y$ in $G$ , there is an edge between $f(x)$ and $f(y)$ in $K_I$ . In other words, it’s an injection $f\colon V \to I$ such that whenever there is an edge between $x$ and $y$ in $G$ , we have $f(x) \neq f(y)$ . But $G$ is a graph without loops, so if there is an edge between $x$ and $y$ then $x \neq y$ . Hence, it’s simply an injection $f\colon V \to I$ .

Posted by: Tom Leinster on April 13, 2013 12:57 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Tom wrote:

I see no nice universal property that complete graphs satisfy.

If we’re trying to apply category theory to graph theory, one way to take advantage of this negative insight might be to generalize the concept of chromatic number or chromatic polynomial by replacing complete graphs with more general graphs.

The biggest generalization is the coYoneda embedding

$Y: Graph^{op} \to Set^{Graph}$

which assigns to any graph $G$ the functor

$hom(G, -) : Graph \to Set$

that keeps count of how many graph homomorphisms there are from $G$ to any other graph.

When we restrict attention to the case where this other graph is a complete graph $K_n$ , we get the chromatic polynomial

$|\hom(G,K_n)|$

But it seems likely there’s more to say, and more ways to bring category theory to bear, if we don’t restrict attention to this case.

For example, I bet that the complete graphs $K_n$ are just one of many sequences of graphs $\Gamma_n$ such that the cardinality

$|hom(G,\Gamma_n)|$

is a polynomial in $n$ . Maybe someone here could examine the proof(s) that the chromatic polynomial is a polynomial and find properties of a sequence of graphs that makes the argument(s) work. Or, maybe someone could just make up sequences of graphs and experimentally determine which ones give polynomials!

Also, for any sequence of graphs we can pose the analogue of Hedetniemi’s conjecture: let $\chi_\Gamma(G)$ be the smallest $n$ such that $hom(G,\Gamma_n)$ is nonempty, and ask if

$\chi_\Gamma(G \times H) = \chi_\Gamma(G) \chi_\Gamma(H)$

Sometimes broadening out a conjecture this way makes it easier to figure out what’s going on.

Posted by: John Baez on April 13, 2013 9:51 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Nice idea! I hope someone will get interested enough to try it. There must be someone here who knows the proof that the chromatic polynomial is a polynomial.

By the way, there’s a slip in your last displayed equation. You presumably meant: $\chi_\Gamma(G \times H) = \min \{ \chi_\Gamma(G), \chi_\Gamma(H)\}.$

Something a bit like your idea appears in this paper:

R. Häggkvist, P. Hell, D.J. Miller, V. Neumann Lara, On multiplicative graphs and the product conjecture. Combinatorica 8 (1988), 63–74.

The abstract begins:

We study the following problem: which graphs $G$ have the property that the class of all graphs not admitting a homomorphism into $G$ is closed under taking the product (conjunction)? Whether all undirected complete graphs have the property is a longstanding open problem due to S. Hedetniemi.

This is a funny way of stating the conjecture. When $G = K_n$ , it says: if $X$ and $Y$ are graphs with $\chi(X) \gt n$ and $\chi(Y) \gt n$ then $\chi(X \times Y) \gt n$ . In other words, if $X$ and $Y$ are graphs with $\min\{\chi(X), \chi(Y)\} \gt n$ then $\chi(X \times Y) \gt n$ . Taken over all $n$ , this says that $\min\{\chi(X), \chi(Y)\} \leq \chi(X \times Y)$ for all $X$ and $Y$ . Since we already know the opposite inequality, this is Hedetniemi’s conjecture.

Posted by: Tom Leinster on April 13, 2013 10:24 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Actually, it’s easy to prove that the chromatic polynomial is a polynomial. This gives us a way to start implementing John’s idea.

Notation: given an edge $e$ of a graph $G$ , we can obtain two new graphs. We can delete $e$ (and keep the same vertices) to obtain a new graph $G - e$ . Or, we can contract $e$ (that is, delete $e$ and then identify the two vertices that it joined) to obtain a new graph $G/e$ .

Write $p_G(n)$ for the number of $n$ -colourings of a graph $G$ . Pick an edge $e$ of $G$ . Then

$p_{G - e}(n) = p_G(n) + p_{G/e}(n).$

Why? Let’s say that $e$ joins vertices $a$ and $b$ .

An $n$ -colouring of $G - e$ that gives $a$ and $b$ different colours is the same thing as an $n$ -colouring of $G$ .
An $n$ -colouring of $G - e$ that gives $a$ and $b$ the same colour is the same thing as an $n$ -colouring of $G/e$ .

That does it. So

$p_G(n) = p_{G - e}(n) - p_{G/e}(n).$

Since both graphs on the right-hand side have fewer edges than $G$ , we can prove that $p_G$ is a polynomial by induction. A tiny thing we’re using here is that if $p_1$ and $p_2$ are polynomials then so is $p_1 - p_2$ .

The base case involves graphs with no edges at all. For such a graph $G = (V, E)$ , the number of $n$ -colourings is $n^{|V|}$ , which is of course a polynomial in $n$ .

Now forget colourings and suppose we have a sequence $(\Gamma_n)$ of graphs, with the following properties:

There is a polynomial $f(x, y)$ such that for all graphs $G$ and edges $e$ ,

In the case $\Gamma_n = K_n$ , we have $f(x, y) = x - y$ .

The number of vertices of $\Gamma_n$ is a polynomial in $n$ . In the case $\Gamma_n = K_n$ , it’s just $n$ .

Then $|Hom(G, \Gamma_n)|$ is a polynomial in $n$ , for each graph $G$ .

I’m sure this is all obvious to any graph theorist. The next question is: are there interesting examples of sequences of graphs $(\Gamma_n)$ , other than $(K_n)$ , that satisfy the two conditions above?

Posted by: Tom Leinster on April 14, 2013 11:48 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

What happens if we look at homomorphisms into the cyclic graphs $C_n$ (which I’ll call $C_n$ -colourings) instead of into the complete graph $K_n$ ? Let’s deal with the base case first: as in the case of homomorphisms into $K_n$ , when $G$ has no edges there are $n^{|G|}$ $C_n$ -colourings (where $|G|$ is the number of vertices in $G$ ), so the base case still gives a polynomial in $n$ .

Now let’s follow the same deletion/contraction analysis: given an edge $e$ between vertices $a$ and $b$ in graph $G$ , we consider the graphs obtained by deletion $(G-e)$ and contraction $(G/e)$ of that edge:

A $C_n$ -colouring of $G-e$ that gives $a$ and $b$ the same colour is the same thing as a $C_n$ -colouring of $G/e$ .
A $C_n$ -colouring of $G-e$ that gives $a$ and $b$ colours that are adjacent in $C_n$ is the same thing as a $C_n$ -colouring of $G$ .
There may also be $C_n$ -colourings of $G-e$ that give $a$ and $b$ distinct non-adjacent colours in $C_n$ . For $n \leq 3$ all colours are adjacent, but for $n \gt 3$ there are $n(n-3)$ such pairs (since $a$ can take any of $n$ colours, and then $b$ can take any colour that’s not the same as, or one of the two neighbours of, $a$ ’s colour).

So, writing $c_G(n)$ for the number of $C_n$ -colourings of graph $G$ , we get: $c_{G}(n) = c_{G-e}(n) - c_{G/e}(n) - min(0,n(n-3))$

So $|Hom(G,C_n)|$ is a polynomial in $n$ for each graph $G$ (but with the complication that we get a slightly different polynomial for $n \leq 3$ than for $n \gt 3$ ).

The same analysis should then apply to other families of graphs, $(\Gamma_n)$ . The base case will give $|\Gamma_n|^{|G|}$ colourings of a graph $G$ with no edges, which will be polynomial in $n$ if $|\Gamma_n|$ is. The deletion and contraction cases of the analysis will be the same for any $\Gamma_n$ . The remaining case requires only that the number of distinct non-adjacent pairs in $\Gamma_n$ is a polynomial in $n$ . If these two conditions are satisfied, we should get $|Hom(G,\Gamma_n)|$ being a polynomial in $n$ for all $G$ .

Posted by: Stuart Presnell on April 15, 2013 10:40 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

I don’t understand your third bullet point. It seems to me that you counted only the ways of colouring vertices $a$ and $b$ with non-adjacent colours, not colourings of the entire graph such $a$ and $b$ have non-adjacent colours.

Posted by: Karol Szumiło on April 16, 2013 9:01 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Of course, you’re quite right – I’ve made a stupid error. And I don’t see any way to patch it by counting the number of colourings of $G-e$ in which $a$ and $b$ get non-adjacent colours (or get a specific pair of non-adjacent colours).

Posted by: Stuart Presnell on April 16, 2013 4:17 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Maybe this edge-at-a-time isn’t the best argument — although clearly it works when it does work.

For $G$ a graph and $f: G \to K_n$ a morphism, the preimage $f^{-1}(n-1)$ of the last colour must subtend no edges of $G$ , while $G - f^{-1}(n-1)$ must be $n-1$ -coloured. So $\chi_G(n) = \sum_{S : starDisjoint G} \chi_{G-S} (n-1)$ ; so the trick, I think, is to remark that this means

(1)

\chi_G(n) = \chi_G(n-1) + \sum_{S :starDisjoint^+ G} \chi_{G-S} (n-1)

By induction, suppose that the “remainder” term is a polynomial of degree $(|V_G|-1)$ — specifically, that each term is a polynomial of degree $|V_G - S|$ ; and the rest is “easy”.

Stuart wants to calculate the “cyclic” colourings of graphs; we can remark that $G$ having a $C_n$ -colouring means the cycles of $G$ have lengths $k n + 2 m$ for natural numbers $k$ and $m$ , not both zero; so we actually have that $# Hom(G,C_n)$ converges to zero unless $G$ is bipartite. But in particular, $C_{n+2}$ has a nice family of edgewise-surjective $C_n$ colourings, which might be handy for generalizing the previous kind of argument. On The Other Hand, the function $# Hom(G,C_n)$ is eventually a polynomial, much as Stuart’s first guess was also eventually a polynomial; just of different degree.

I’d recomend considering the family of complete tripartite graphs $K(a,b,c)$ : these will have cycles of lengths $3$ when $abc\gt 0$ , $4$ if $ab+bc+ac \geq 4$ , and $5$ as soon as $a + b + c \gt 3$ ; and so $C_n$ will also have lots of $K(a,b,c)$ colourings.

Posted by: Jesse C. McKeown on April 16, 2013 6:21 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

OK, $a + b + c \gt 3$ is not the right criterion. Say $\min(a,b,c) = 2$ instead.

Posted by: Jesse McKeown on April 16, 2013 6:24 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

I must be getting impatient, because I keep writing really-nonsense, and I blame three hours of watching a calculus exam.

Any persistent person can find sufficient conditions for the cycle lengths $3,4,5$ in a $K(a,b,c)$ , whether they are necessary or not.

Time for lunch.

Posted by: Jesse C McKeown on April 16, 2013 6:32 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

I’m perfectly happy to find sequences of graphs $\Gamma_n$ such that the number of homomorphisms from any graph $G$ to $\Gamma_n$ is eventually a polynomial in $n$ , that is, for large enough $n$ . I’d be happiest, of course, if this polynomial weren’t zero, so it could distinguish some graphs.

The business about eventual polynomials shows up other places too. If you have a graded ring (or algebra) $A = \sum_{n=0}^\infty A_n$ with finitely many homogeneous generators and relations, I believe the dimension $dim(A_n)$ is eventually a polynomial, called the Hilbert polynomial of $A$ . (Not to be confused with the Hilbert series!)

The interesting part is that there’s typically a ‘glitch’ near the beginning: $dim(A_n)$ only agrees with the Hilbert polynomial when $n$ is greater than equal to some number called the Hilbert regularity of $A$ . It’s fun to look at how this works in simple examples.

I have no idea if this is related to graph theory. In particular I have no idea if there’s a graded algebra $A(G)$ associated with a graph $G$ such that $\dim(A_n(G))$ is the number of $n$ -colorings of $G$ .

Posted by: John Baez on April 17, 2013 1:51 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

John wrote

I have no idea if this is related to graph theory. In particular I have no idea if there’s a graded algebra $A(G)$ associated with a graph $G$ such that $dim(A_n(G))$ is the number of $n$ -colorings of $G$ .

Actually now I’m thinking there might be. Could this be true? Let $A_n(G)$ be the vector space spanned by the set of $n$ -colorings of $G$ . Let’s try to make up an associative way to multiply an $m$ -coloring and an $n$ -coloring and get an $mn$ -coloring.

Clearly there are bijections

$m \times n \cong m n$

where now I’m using $m$ to mean some standard $m$ -element set, and similarly for $n$ and $m n$ . So clearly there’s a way to take an $m$ -coloring and an $n$ -coloring and reinterpret the pair of them as an $m n$ coloring. The problem is the associativity.

So it seems like we need to make the category of finite sets into a strict skeletal monoidal category: in other words, a category where there’s just one $n$ -element set for each $n$ , so we can say

$m \times n = m n$

and where the niggly ‘associator’ isomorphisms

$(\ell \times m) \times n \cong \ell \times (m \times n)$

can all be taken to be the identity.

Beginners often think that skeletality somehow helps a monoidal category be strict, but this is not true; indeed it makes it harder. Every monoidal category is equivalent to a strict one, and also to a skeletal one, but getting both at the same time is not generally possible.

However, an expert I know convincingly argued that the category of finite sets, made monoidal using the cartesian product, can be made both skeletal and strict.

So this seems to give an associative algebra $A(G)$ such that $A_n(G)$ has, as its basis, the $n$ -colorings of $G$ .

Is this right? Is this something graph theorists ever talk about?

(By the way, my proposed algebra doesn’t have a multiplicative unit, but you can throw one in ad hocly if you insist.)

Posted by: John Baez on April 17, 2013 2:22 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Here’s another take on the same thing, John.

Let’s try to make up an associative way to multiply an $m$ -coloring and an $n$ -coloring and get an $m n$ -coloring.

I noted before that there’s a functor

$K\colon FinSet^{inj} \to Graph$

sending a finite set $I$ to $K_I$ , the complete graph with vertex-set $I$ . Here $FinSet^{inj}$ is the category of finite sets and injections. We won’t need non-bijective injections in what follows, but it does no harm to keep them around.

There’s a monoidal structure on $FinSet^{inj}$ given by cartesian product. (It’s not actually the categorical product in $FinSet^{inj}$ , because the product-projections want to be non-injective.)

There’s also a monoidal structure on $Graph$ given by categorical product. Well: it’s not actually monoidal because there’s no terminal graph, but as I can’t bring myself to say “semigroupal”, I’ll continue to call it monoidal.

Finally, there’s a lax monoidal structure on the functor $K$ . In other words, for each finite set $I$ and finite set $J$ , there’s a natural map

$\phi_{I, J} \colon K_I \times K_J \to K_{I \times J}.$

The domain and codomain have the same vertex-set (namely, $I \times J$ ), and $\phi_{I, J}$ acts as the identity on vertices. From this, it’s immediate that $\phi$ satisfies the axioms for a lax monoidal functor.

It follows that for any graph $G$ and finite sets $I$ and $J$ , we have a map

$Hom(G, K_I) \times Hom(G, K_J) \cong Hom(G, K_I \times K_J) \stackrel{\phi_{I, J}}{\to} Hom(G, K_{I \times J}).$

Recalling that an $I$ -colouring of $G$ is a map $G \to K_I$ , this is a way of taking an $I$ -colouring together with a $J$ -colouring and producing an $I \times J$ -colouring. It’s the same as the obvious one you mentioned. Let’s call this the “product” of colourings.

One of the axioms for a lax monoidal functor (the one that involves a three-fold product) implies that this product is associative.

But you didn’t want a family $(A_I(G))$ of vector spaces indexed by finite sets $I$ : you wanted a family $(A_n(G))$ indexed by the natural numbers.

So, let $\mathbb{N}$ be the multiplicative monoid of natural numbers, regarded as a discrete monoidal category (both skeletal and strict, for what it’s worth). Choose a finite set $\langle n\rangle$ for each number $n$ , and choose a total ordering on $\langle n\rangle$ . As Jamie pointed out, lexicographic ordering defines a bijection

$\langle m \rangle \times \langle n \rangle \to \langle m n \rangle$

for each $m$ and $n$ . This gives the functor

$\begin{array}{ccc} \mathbb{N} &\to &FinSet^{inj} \\ n &\mapsto &\langle n \rangle \end{array}$

a monoidal structure.

So all in all, we have for each graph $G$ a string of lax monoidal functors

$\mathbb{N} \to FinSet^{inj} \stackrel{K}{\to} Graph \stackrel{Hom(G, -)}{\to} Set \stackrel{free  VS}{\to} Vect.$

So we get a lax monoidal functor $\mathbb{N} \to Vect$ : in other words, a graded associative algebra.

Posted by: Tom Leinster on April 17, 2013 3:15 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Interesting! At first I thought you were going to use fancy category-theoretic stuff to get around the need for a strict skeletal version of $FinSet$ (which seems like a silly stunt, even though when I wrote my comment I was very proud that I could pull it out of my bag of tricks when it was needed). But then at the end you used it.

But… clearly you’re hinting that before we pull that stunt, we get something even ‘better’ than a graded algebra whose grades have dimensions given by the chromatic polynomial of our graph. Namely, a lax monoidal functor

$A(G) : FinSet^{inj} \to Vect$

such that the dimension of $A(n)$ is equal to the chromatic polynomial of $G$ .

Of course the lax monoidal functor

$Hom(G,K_{-}): FinSet^{inj} \to Set$

is even ‘better’, since it gives rise to $A(G)$ and is more fundamental. But people like linear algebra, and my question was about that.

Posted by: John Baez on April 18, 2013 1:46 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

I confess, when I started to write my comment I didn’t think I’d need to use that comment of Jamie’s. But I’m glad you did pull it out of your bag of tricks, because I would have got stuck on it otherwise.

I guess what one should really say about Jamie’s construction is the following. Let $FinTot^{inj}$ be the category of finite totally ordered sets and order-preserving injections, made monoidal not in the usual way (addition) but via the lexicographic tensor product $\otimes$ . In other words, if $X$ and $Y$ are finite totally ordered sets then $X \otimes Y$ is the set $X \times Y$ with the lexicographic ordering. Then the functor $\langle -\rangle$ I defined above is really a monoidal functor $\mathbb{N} \to FinTot^{inj}$ .

The functor $\mathbb{N} \to FinSet^{inj}$ I defined before is the composite of this with the obvious forgetful functor $FinTot^{inj} \to FinSet^{inj}$ (which is monoidal too). So the diagram at the bottom of my comment becomes

$\mathbb{N} \stackrel{\langle-\rangle}{\to} FinTot^{inj} \stackrel{forget}{\to} FinSet^{inj} \stackrel{K}{\to} Graph \stackrel{Hom(G, -)}{\to} Set \stackrel{free VS}{\to} Vect.$

Posted by: Tom Leinster on April 18, 2013 4:45 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

John wrote:

I have no idea if this is related to graph theory. In particular I have no idea if there’s a graded algebra $A(G)$ associated with a graph $G$ such that $dim(A_n(G))$ is the number of $n$ -colorings of $G$ .

Actually now I’m thinking there might be.

… but what I actually constructed was not a graded algebra in the usual sense, but an algebra graded by the multiplicative monoid of natural numbers! In other words, I found an associative algebra

$A(G) = \bigoplus_{n \in \mathbb{N}} A_n(G)$

where $A_n(G)$ had a basis given by the $n$ -colorings of $G$ , but it has

$A_m(G) A_n(G) \subseteq A_{m n}(G)$

instead of the more usual

$A_m(G) A_n(G) \subseteq A_{m+n}(G)$

It took me a while to notice this…

But now Matthias Beck says:

There is such a graded algebra: it was constructed about a decade ago by Einar Steingrimsson; here’s the paper. It’s also worth checking out the follow-up work (see the forward pointers in MathSciNet).

Near the start of that paper Steingrimsson writes:

It should also be mentioned that Brenti asked [3] whether there exists, for an arbitrary graph $G$ , a standard graded algebra whose Hilbert polynomial equals the chromatic polynomial of $G$ . This was answered in the affirmative by Almkvist [1], but his proof is non-constructive.

Posted by: John Baez on April 24, 2013 9:08 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

There is such a graded algebra: it was constructed about a decade ago by Einar Steingrimsson; here’s the paper. It’s also worth checking out the follow-up work (see the forward pointers in MathSciNet).

Posted by: Matthias Beck on April 19, 2013 7:47 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

IF a sequence of graphs is going to describe eventually-polynomial cohomologies, then it had better have eventually-polynomial-many vertices. There’s a nifty recursion relation for $Hom(G,\square^n)$ as a sum over cuts of $G$ , but for obvious reasons it more than doubles from $n$ to $n+1$ .

Generalizing, for fixed $n$ , $| Hom (G, K(a_1,a_2,\cdots,a_n)) |$ is a homogeneous symmetric polynomial of $a_i$ , and a sum over $n$ -colourings of $G$ … The orthoplex $1$ -skeleton is actually a $K(2,2,\cdots,2)$ so an $Orth_n$ -colouring is an $n$ -colouring and a choice in $2^{V}$ , but that’s not more other information than was in the chromatic polynomial.

The same trick that leads to $| Hom (G, C_n) |$ eventually-linear also leads to $|Hom(G,T_{m,n})|$ eventually- $c m\times n$ , where $T_{m,n}$ is either $C_m \square C_n$ or a regular triangulation of a torus. A boxy torus is bipartite, and lots of triangulated tori are $3$ -colourable — though in at most three ways. In general, it seems that one wants the diameter of $\Gamma_n$ to grow much slower than the vertex number. The complete graph $K_n$ has $n$ vertices and is of diameter $1$ .

Since $K_n$ is the relation of being disjoint size-1 subsets of $\langle n\rangle$ , one might be interested the relation of being size- $l$ -intersecting size- $k$ -subsets of $\langle n \rangle$ ; let’s call these graphs $Inc_{l , k , n}$ .

In the family $Inc_{1,2,n}$ , an $Inc_{1,2,n+1}$ -colouring of $G$ has an $Inc_{1,2,n}$ -colouring of a full subgraph $S$ and a special $n$ -colouring of the complement of $S$ … but clarifying how that works or looking for relations with different $Inc$ -colourings, I can’t see how to do, just now.

Posted by: Jesse C. McKeown on April 18, 2013 5:18 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

It turns out that $Inc_{0,k,n}$ gives what are called $k$ -fold multicolourings of a graph; and I now have an argument that the number of $Inc_{l,k,n}$ -colourings is polynomial in $n$ . It involves $n$ -colourings of some different graphs.

Posted by: Jesse C. McKeown on April 18, 2013 3:19 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

What other categories are there where you can associate something to each object such that the thing of a product of objects is equal to an interesting function of the things of the objects?

Posted by: GHGH on April 13, 2013 11:30 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Lots! Vector spaces, sets, measure spaces…

But usually you add or multiply those things. So perhaps a more focused question is: when do you take the minimum of those things?

Posted by: John Baez on April 14, 2013 5:20 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Writing min as a semigroup operation looks neater

$\chi(G \times H)=\chi(G)\oplus\chi(H)$

Posted by: GHGH on April 14, 2013 10:36 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

The category of graphs (the ordinary one – no loops, at most one edge between two vertices) has one strange property.

On any category $\mathbf{C}$ you can introduce a binary relation on the class of all objects “there is an arrow”. This is clearly a preorder. Consider this preorder as a partial order of its equivalence classes, obtaining a partial order.

Most of the categories you meet in the wild collapse to triviality under this partial order: $\mathbf{Groups}$ or $\mathbf{Vect}$ give you a one-element poset; $\math{Sets}$ gives you a two elements poset “empty” and “nonempty” and so on. Nothing interesting.

$\mathbf{Graphs}$ is very different. Not only is the partial order inifinite, it is in fact dense, even if you consider only finite graphs.

In other words, whenever you have two graphs $G$ and $H$ such that there is an arrow $G\to H$ and there is no arrow $H\to G$ , there is a graph $K$ such that there are arrows $G\to K\to H$ , but no arrow $K\to G$ nor $H\to K$ .

I think that this property is very important, because the richness of this partial order is at the core of our ability to convert very many different problems to existence of graph homomorphisms, for example colorings.

See this paper for a nice introduction to graph homomorphisms.

Posted by: Gejza Jenča on April 14, 2013 9:59 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Very interesting; thanks! I’ve never come across a category in the wild whose underlying order is so interesting.

For anyone else following the link in your last sentence, the result on density is Theorem 2.33, with a proof on page 144.

Posted by: Tom Leinster on April 14, 2013 10:43 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

By the way, is there a standard term for the underlying preorder of a category, other than “underlying preorder” itself? Since it is intermediate between a category and its decategorification, could it be called “preorder decategorification”?

Alternatively, it can also be regarded as a change of enrichment from Sets to the poset of truth values along the obvious monoidal functor. Or as the underlying (0,1)-category of a (1,1)-category.

I have come across the underlying preorder in a different context, but would like to use the standard terminology, if there is one.

(The categories that I would like to consider this for are often comma categories, arrow categories, or of a similar flavor. Nothing comparable to Graphs here…)

Posted by: Tobias Fritz on April 15, 2013 2:05 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Hi Tobias. I don’t know a name for it. But I agree with your point of view: it’s nice to regard it as the functor

$\mathbf{Cat} = \mathbf{Set}\text{-}\mathbf{Cat} \to \mathbf{2}\text{-}\mathbf{Cat} = \mathbf{Poset}$

induced by the monoidal functor

$\mathbf{Set} \to \mathbf{2} = \{0, 1\}$

that sends the empty set to $0$ and everything else to $1$ . Even better, it’s good to notice that this monoidal functor is left adjoint to the inclusion

$\mathbf{2} \hookrightarrow \mathbf{Set}$

which itself induces the inclusion

$\mathbf{Poset} = \mathbf{2}\text{-}\mathbf{Cat} \hookrightarrow \mathbf{Set}\text{-}\mathbf{Cat} = \mathbf{Cat}.$

In other words, the adjunction

$\mathbf{2} \stackrel{\longrightarrow}{\leftarrow} \mathbf{Set}$

of monoidal (i.e. product-preserving) functors induces the adjunction

$\mathbf{Poset} \stackrel{\longrightarrow}{\leftarrow} \mathbf{Cat}.$

Posted by: Tom Leinster on April 15, 2013 2:37 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

I tend to call it the ‘preorder reflection’, since it is left adjoint to the inclusion of preorders in categories. I think the word ‘underlying’ is not really applicable with its usual connotations.

Posted by: Mike Shulman on April 15, 2013 3:08 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Thanks Tom and Mike! I didn’t know about those adjunctions, Tom, that’s useful input. And now that you mention it, Mike, I agree that “underlying” is not the right term.

Posted by: Tobias Fritz on April 15, 2013 11:36 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

For people interested in this subject, I can recommend the book “Algebraic Graph Theory” by Godsil and Royle. Chapter 6 is about Hedetniemi’s conjecture and its equivalents as well as other considerations surrounding graph homomorphisms.

The book generally has a lot of colourful exercises. A couple in particular from Chapter 6 which I recall enjoying when I took the course about a decade ago:

A retraction is a homomorphism $f: X \to Y$ where $Y$ is a subgraph of $X$ , such that the restriction of $f$ to $Y$ is the identity map.

$19.$ If $X$ and $Y$ are connected graphs, then show that $K_n$ is a retract of $X \times Y$ only if it is a retract of $X$ or a retract of $Y$ .

$20.$ Show that Hedetniemi’s conjecture is equivalent to the statement that $K_n$ is a retract of the product $X \times Y$ of two graphs only if it is a retract of $X$ or a retract of $Y$ .

Posted by: Cale Gibbard on April 14, 2013 10:50 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Well, there’s a challenge. Thanks a lot. I’m not sure whether I should try those problems without reading the relevant part of the book first. I guess it can’t hurt…

Let’s try thinking about 19 for some low values of $n$ .

For $n = 0$ : the graph $K_0$ is empty, so the statement is this:

if $\emptyset$ is a retract of $X \times Y$ then $\emptyset$ is a retract of $X$ or of $Y$ .

But $\emptyset$ is a retract of a graph $G$ if and only if $G$ is empty. So the statement is:

if $X \times Y$ is empty then $X$ is empty or $Y$ is empty.

That’s true.

For $n = 1$ : the graph $K_1$ is a single vertex (without a loop; our graphs don’t have loops anyway). So $K_1$ is a retract of a graph $G$ iff $G$ is nonempty and discrete (I mean, contains no edges). So the statement is:

if $X \times Y$ is nonempty and discrete then either $X$ or $Y$ is nonempty and discrete.

Well, if $X \times Y$ is nonempty then both $X$ and $Y$ are nonempty. Also, if $X \times Y$ is discrete then $X$ or $Y$ must be discrete, since if $X$ and $Y$ both contain an edge then $X \times Y$ does. So it’s true.

For $n = 2$ : the graph $K_2$ is two vertices joined by an edge. So $K_2$ is a retract of a graph $G$ if and only if $G$ is bipartite and not discrete. Hence the statement is:

if $X \times Y$ is bipartite and not discrete then either $X$ or $Y$ is bipartite and not discrete.

The discreteness part is easy: assuming $X \times Y$ is not discrete, neither $X$ nor $Y$ is discrete.

I guess a graph is bipartite if and only if it contains no cycles of odd length. So then, if $X$ is non-bipartite then it contains a cycle of odd length $k$ , and if $Y$ is also non-bipartite then it contains a cycle of odd length $\ell$ , in which case $X \times Y$ contains a cycle of odd length $lcm(k, \ell)$ , and is therefore non-bipartite.

I didn’t use connectedness in any of that, but I suppose it gets used for higher values of $n$ .

Posted by: Tom Leinster on April 15, 2013 2:27 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

OK, I can do exercise 20 now, but haven’t got 19. Can you give a hint, Cale?

Posted by: Tom Leinster on April 16, 2013 12:26 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

… and today is Euler’s 306th birthday, a fact that I know thanks to Google’s page for the day.

Posted by: Tim Porter on April 15, 2013 7:15 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

My impression is that graph theorists occasionally want the freedom to collapse adjacent vertices even while not allowing loops. This suggest that they are then working with Sets with reflexive symmetric relations but still think of these as graphs without loops: after all, when you demand a loop at every vertex and your graphs are simple anyway, then you might as well omit the loops from your diagram.

Of course in this szenario an $n$ -colouring of a graph $G$ would not correspond any more to all graph maps from $G$ to $K_n$ but only to those that have the right lifting property w.r.t. the inclusion $2\hookrightarrow K_2$ .

By the way, these (reflexive) graphs have a model structure where the cofibrations are the monomorphisms and the weak equivalences are those maps that induce bijections between connected components. In this model structure a graph is fibrant iff its relation is transitive. Hence the complete graphs $K_n$ are exactly those fibrant objects that are weakly equivalent to $1$ .

Posted by: Marc Olschok on April 15, 2013 6:20 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

> Of course in this szenario an $n$ -colouring of a graph $G$
> would not correspond any more to all graph maps
> from $G$ to $K_n$ but only to those that have the
> right lifting property w.r.t. the inclusion $2\hookrightarrow K_2$ .

Sorry, this should of course read:

[…] right lifting property w.r.t. $K_2\rightarrow 1$ .

Posted by: Marc Olschok on April 15, 2013 6:30 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

In 2019, the conjecture was disproved by Shitov!

Posted by: Mike Stay on July 17, 2020 8:47 PM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Yes! Thanks for mentioning that, Mike. Tobias Fritz started a conversation about Shitov’s result over on another thread, but I forgot about this thread here, so it’s good that you brought it up.

Posted by: Tom Leinster on July 18, 2020 1:19 AM | Permalink | Reply to this

Re: Colouring a Graph

$MathML-enabled post (click for more details).$

Hello, everyone. I have just posted an arXiv paper, Causal-net category, arXiv:2201.08963.In this paper, I show a new idea on a category-theoretic understanding of graph theory.

The abstract is as follows.

A causal-net is a finite acyclic directed graph. In this paper, we introduce a category, denoted as $\mathbf{Cau}$ , whose objects are causal-nets and morphisms are functors of path categories of causal-nets. It is called causal-net category and in fact the Kleisli category of the “free category on a causal-net” monad. We study several composition-closed classes of morphisms in $\mathbf{Cau}$ , which characterize interesting causal-net relations, such as coarse-graining, contraction, immersion-minor, topological minor, etc., and prove several useful decomposition theorems. In addition, we show that the notions of a coloring and a minor can be understood as a special kind of minimal-quotient and sub-quotient in $\mathbf{Cau}$ , respectively. Base on these results, we conclude that $\mathbf{Cau}$ is a natural setting for studying causal-nets, and the theory of $\mathbf{Cau}$ should shed new light on the category-theoretic understanding of graph theory.

The interpretion of a coloring as a minimal-quotient is contained in the second version of this arXiv paper, which will be announced at Wed, 26 Jan 2022 01:00:00 GMT.

Hope my paper is helpful for clearifying the relation of graph theory and category theory.

Posted by: Xuexing Lu on January 25, 2022 12:43 PM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

April 12, 2013