Graph Colouring and Cartesian Closed Categories

December 5, 2014

Graph Colouring and Cartesian Closed Categories

Posted by Tom Leinster

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

Just for fun, here’s a reformulation of a famous conjecture in terms of the cartesian closed structure on the category of graphs.

Hedetniemi’s conjecture says there’s no clever way of colouring a product of graphs. By “colouring”, I mean colouring the vertices in such a way that the ends of each edge get different colours.

Given graphs $X$ and $Y$ , any colouring of $X$ gives rise to a colouring of $X \times Y$ : just paint $(x, y)$ the same colour as $x$ . Of course, the same is true with $X$ and $Y$ interchanged. Hedetniemi conjectured that if you want to colour $X \times Y$ with as few colours as possible, you can’t beat this method. That is, writing $\chi$ for the chromatic number of a graph — the smallest number of colours needed to colour it —

$\chi(X \times Y) = \min \{ \chi(X), \chi(Y) \}.$

This has been open since 1966.

I’ll explain how Hedetniemi’s conjecture is equivalent to the following statement about the cartesian closed category of graphs: for any graph $X$ and complete graph $K$ , either $K^X$ or $K^{K^X}$ has a point.

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

For the purposes of this post, a graph $X$ is a finite set $V(X)$ with a symmetric relation $E(X)$ on it, and a homomorphism is a map of vertex-sets preserving the relation. Concretely, then, our graphs are undirected and can’t have multiple edges, but each vertex may have a loop on it (an edge from it to itself).

The category of graphs has finite products. They’re what you’d imagine: a vertex of $X \times Y$ is a pair $(x, y) \in V(X) \times V(Y)$ , and vertices $(x, y)$ and $(x', y')$ are adjacent (that is, there’s an edge between them) if and only if $x$ is adjacent to $x'$ and $y$ is adjacent to $y'$ .

The terminal graph $1$ consists of a single vertex with a loop on it. In a category with a terminal object $1$ , a point or global element of an object $X$ is simply a map $1 \to X$ . Here, then, a point of a graph $X$ is a loop in $X$ .

Graph theorists most often like to consider “pointless graphs” — those without loops. But for what we’re doing here, it’s important to allow graphs to have points.

The category of graphs not only has finite products; it’s also cartesian closed. This means that for any graphs $Y$ and $Z$ , there is another graph $Z^Y$ with the following property: for all graphs $X$ , there is a natural one-to-one correspondence between homomorphisms

$X \to Z^Y$

and homomorphisms

$X \times Y \to Z.$

Here’s what $Z^Y$ looks like. A vertex is not a homomorphism from $Y$ to $Z$ , as you might guess; it’s any function $V(Y) \to V(Z)$ . Two functions $\theta, \theta': V(Y) \to V(Z)$ are adjacent in $Z^Y$ if and only if

$(y, y') \,\,\text{ adjacent in }\,\, Y \implies (\theta(y), \theta'(y')) \,\,\text{ adjacent in }\,\, Z.$

In particular, $\theta: V(Y) \to V(Z)$ is adjacent to itself in $Z^Y$ (meaning that there is a loop on $\theta$ ) if and only if $\theta$ is a homomorphism $Y \to Z$ . Differently put, the points of $Z^Y$ are exactly the homomorphisms $Y \to Z$ . This is the special case $X = 1$ of the one-to-one correspondence just mentioned.

Now for colourings. As I wrote about once before, a (proper) colouring of a graph $X$ by $n$ colours is nothing more than a homomorphism from $X$ to the complete graph $K_n$ . By definition, $K_n$ has $n$ vertices and an edge between each pair of distinct vertices. It contains no loops, so it’s in some sense a maximal pointless graph.

I want to draw your attention to a trivial but important point, which I’ll give a grand name so that I can refer to it later:

The Exclusivity Principle Let $X$ be a graph and $K$ a complete graph. Then $X$ and $K^X$ cannot both have points.

Why? Well, a point of $X$ is a homomorphism $1 \to X$ , and a point of $K^X$ is a homomorphism $X \to K$ , so if we have both then we can compose to get a point $1 \to K$ — and that’s impossible, as complete graphs are pointless. Like I said, trivial.

Another way to put this is that a graph with a point has no colourings. Concretely, this is simply the fact that if our graph contains a loop then we fall foul of the condition that different ends of each edge have to be different colours: they can’t be, because they’re the same vertex!

The chromatic number of a graph is the smallest number of colours you need to colour it:

$\chi(X) = \min \{ n : Hom(X, K_n) \neq \emptyset \} \in \mathbb{N} \cup \{\infty\}.$

A pointless graph can always be coloured by painting each vertex a different colour. On the other hand, we just saw that if a graph has any points at all, it has no colouring. So $\chi(X) \lt \infty$ if and only if $X$ is pointless.

Any graph homomorphism $W \to X$ induces a function $\Hom(X, K_n) \to \Hom(W, K_n)$ from the set of $n$ -colourings of $X$ to those of $W$ , by composition. In particular, if $X$ is $n$ -colourable then so is $W$ . Let’s write $W \leq X$ if there exists a homomorphism $W \to X$ . Then

$W \leq X \implies \chi(W) \leq \chi(X).$

In particular, take graphs $X$ and $Y$ . Since we have projections $X \times Y \to X$ and $X \times Y \to Y$ ,

$\chi(X \times Y) \leq \min \{ \chi(X), \chi(Y) \}.$

Conjecture (Hedetniemi, version 1) This is an equality.

In the case where $X$ or $Y$ has a point, it’s trivial. For suppose that $X$ has a point. Then we have a map $Y \cong 1 \times Y \to X \times Y$ , as well as the projection $X \times Y \to Y$ . This gives $Y \leq X \times Y \leq Y$ , and so

$\chi(X \times Y) = \chi(Y) = \min \{\infty, \chi(Y)\} = \min \{\chi(X), \chi(Y)\}.$

So the substance of the conjecture is about pointless, or irreflexive, graphs.

To get to the rephrasing of the conjecture mentioned in the introduction, I want to move the focus away from the chromatic number $n$ and towards the family of complete graphs. So here’s a first, mild, rephrasing.

Conjecture (Hedetniemi, version 2) Let $X$ and $Y$ be graphs and $K$ a complete graph. If there is a homomorphism $X \times Y \to K$ , then there is a homomorphism $X \to K$ or a homomorphism $Y \to K$ .

Writing $K$ as $K_n$ , this just says: if $\chi(X \times Y) \leq n$ then $\chi(X) \leq n$ or $\chi(Y) \leq n$ . That is, if $\chi(X \times Y) \leq n$ then $\min\{\chi(X), \chi(Y)\} \leq n$ . That is, $\min\{\chi(X), \chi(Y)\} \leq \chi(X \times Y)$ . Since the converse inequality is trivial, that’s equivalent to version 1.

Now here’s a third, slightly different-looking, version of Hedetniemi’s conjecture. I learned it from Godsil and Royle’s book Algebraic Graph Theory (section 6.6).

Conjecture (Hedetniemi, version 3) For any graph $X$ and complete graph $K$ , either $K^X$ or $K^{K^X}$ has a point.

The Exclusivity Principle implies that they can’t both have a point: so it’s a strict either/or.

Let’s prove that this is equivalent to version 2.

First suppose that version 3 is true. Take graphs $X$ and $Y$ , and a complete graph $K$ . We’ll prove the contrapositive of version 2: if there’s no homomorphism $X \to K$ and no homomorphism $Y \to K$ then there is no homomorphism $X \times Y \to K$ . Supposing that there are no homomorphisms $X \to K$ or $Y \to K$ , version 3 implies that there are homomorphisms $\alpha: K^X \to K$ and $\beta: K^Y \to K$ . So we get homomorphisms

$K^{X \times Y} \cong (K^X)^Y \stackrel{\alpha^Y}{\longrightarrow} K^Y \stackrel{\beta}{\longrightarrow} K$

The composite is a homomorphism $K^{X \times Y} \to K$ . So by the Exclusivity Principle applied to $K^{X \times Y}$ , there’s no homomorphism $X \times Y \to K$ .

Conversely, suppose that version 2 is true. Take a graph $X$ and a complete graph $K$ . The cartesian closed structure gives us a counit homomorphism

$K^X \times X \to K,$

(which concretely is just $(\theta, x) \mapsto \theta(x)$ ). Version 2 then tells us that either there’s a homomorphism $K^X \to K$ or there’s a homomorphism $X \to K$ . And that’s exactly what version 3 says.

So that’s the rephrasing of Hedetniemi’s conjecture. As I said, it’s just for fun: there’s no evidence that it leads anywhere.

You could also state a fourth version:

Conjecture (Hedetniemi, version 4) For any graph $X$ and complete graph $K$ , at least one of the graphs $X, K^X, K^{K^X}, K^{K^{K^X}}, \ldots$ has a point.

But that seems like just a dressing-up of version 3. Why? Well, for any graph $A$ , the cartesian closed structure gives us a unit map $\eta_A: A \to K^{K^A}$ . Taking $A = X$ and $A = K^X$ in turn gives us maps

$K^{(\eta_X)}: K^{K^{K^X}} \to K^X, \qquad \eta_{K^X}: K^X \to K^{K^{K^X}}.$

(Category theorists will now mumble the words “triangle identity”.) So $K^X$ has a point iff $K^{K^{K^X}}$ does. More generally, by the same argument, the $n$ th member of this sequence has a point iff the $(n + 2)$ th member does, for $n \geq 2$ . So we might as well truncate the sequence to

$X, K^X, K^{K^X}.$

We can also drop the $X$ , since the unit map $\eta_X: X \to K^{K^X}$ tells us that if $X$ has a point then $K^{K^X}$ does too. So we’re back to version 3.

Posted at December 5, 2014 1:18 PM UTC

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

60 Comments & 0 Trackbacks

Re: Graph Colouring and Cartesian Closed Categories

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

If you could use the ideas to help prove the Hedetniemi conjecture, category theorists would be eternally grateful, since they’d have a nice answer to “what has category theory ever done for graph theory?”

Of course you’ve already thought of this.

Posted by: John Baez on December 5, 2014 4:31 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

I wish I had more success at communicating with graph theorists. I’ve been trying to do so ever since I started working on the magnitude of graphs, but with almost total failure. Just this week, I gave a colloquium at Birmingham (UK!), where there’s a big graph theory/combinatorics group. Though lots of them came to the talk and I explicitly appealed for their help during it, apparently I didn’t succeed in reeling them in. (At least, I heard nothing from them.)

Several other efforts of mine to involve graph theorists have failed. I don’t know whether my viewpoint is so different from theirs that I’m just not interesting them, or it’s just bad luck, or what.

Posted by: Tom Leinster on December 5, 2014 4:45 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Actually I regard just the sheer formulation of the conjecture in categorical terms, and moreover in a way that has some resonance in categorical logic, already a small victory.

What I mean is: it seems to me that a lot of things that excite graph theorists are somewhat opaque from the standpoint of expressing them in categorical language. For example, there is a much celebrated result, perhaps the most celebrated result in all of graph theory, called the Robertson-Seymour theorem. A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from $G$ in finitely many steps where each step consists either in removing an edge, removing an isolated point, or contracting an edge (i.e. remove the edge and merge its endpoints). The minor relation is a partial order, and the Robertson-Seymour theorem says that the graph minor relation on the class of finite (simple loop-free) graphs has no infinite antichain. This result has useful consequences; for instance, if a class of graphs (for example, planar graphs) is closed under taking graph minors, then there exists a finite collection $\mathcal{C}$ of “forbidden minors”: the given class consists of exactly those graphs which have no element of $\mathcal{C}$ as a minor up to isomorphism – in the case of planar trees, the forbidden minors would be $K_5$ and $K_{3, 3}$ .

But what is a graph minor, categorically? It doesn’t seem very obvious to me. It looks like a subquotient of some kind: certainly if $H$ is a subgraph of $G$ , then $H$ can be obtained from $G$ by removing edges and isolated points, whereas edge contraction looks more like a quotient construction.

To make this work, it seems convenient to formally identify a simple loop-free graph with a set carrying a reflexive symmetric relation. (Yes, it seems strange at first that loop-free graphs are identified with reflexive relations, but by analogy with categories, we can think of the “identity loop” at a vertex (enforced by reflexivity) as a path of length $0$ which we don’t bother to draw. In any case, there is a canonical bijection between reflexive relations and irreflexive relations, and we can choose whichever is more convenient.) It’s convenient here to use reflexive relations because if we think of contracting an edge between two distinct points as a quotient, then that edge has to go somewhere under the quotient map, so take it to the identity loop at the merged point.

But of course edge contraction is but one sort of quotient; another would be simply to merge two points which didn’t have an edge between them. Is there some categorical way of picking out (series of) edge contractions? I don’t know. So here even just formulating graph minors in categorical terms could be tricky.

Posted by: Todd Trimble on December 24, 2014 12:26 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Here is, I think, the correct categorical definition of a contraction. Note first that for the category $Graph$ of undirected graphs (possibly with loops) we have a functor $CC: Graph \to Graph$ which takes each graph to its “set” of connected components represented as a discrete graph with loops at all vertices. The loops are essential because then we have a natural transformation $\phi : 1_{Graph} \to CC$ which sends each vertex to its connected component.

$G'$ is a contraction of $G$ iff there is a map $m: G \to G'$ which satisfies two conditions. 1) m is epi (which is the same as surjective in this category) and 2) $m(x) = m(x')$ implies that there is a path from $x$ to $x'$ in $G$ .

Now, consider any homomorphism $f: K \to G$ . It’s not hard to see that $im(f)$ ’s connected components uniquely determine a contraction. I claim that $G'$ is a contraction of $G$ iff there is a pushout square composed of some $K$ , $f$ , $m: G \to G'$ , $\phi_K: K \to CC(K)$ , and $q: CC(K) \to G'$ . (Sorry, don’t know how to TeX commutative diagrams.) There is a lot to verify here but it all checks out. One has to use the fact that $G \to CC(G')$ factors through $CC(G)$ .

Now the definition applies to Top, FinTop, et al. I’m guessing Robertson-Seymour doesn’t hold in Graph? Does anyone have a counterexample? (Just to be safe, it holds for graphs possibly with loops, right? If not, replace $Graph$ above with the category of undirected graphs with loops.)

Posted by: Ibrahim Tencer on January 17, 2015 12:44 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Ibrahim, I’m glad you’re looking at this. I didn’t follow you when you said that epi means surjective in this category: it seems to me that the map from $\{0, 1\}$ (the discrete graph, say with loops) to $\{0 \leftrightarrow 1\}$ (add an edge to the preceding graph; it’s supposed to be undirected), the one which is the identity on vertices, is epi in the categorical sense, but not surjective on edges. It also satisfies condition 2).

If we strengthen “epi” to “regular epi” in condition 1), that would remove this counterexample. But I’m still not yet happy. Suppose we take a graph like this (and again let’s assume loops at every vertex):

$0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow 3$

and then we identify $0$ with $3$ to make a triangle. This is a regular epi and certainly satisfies condition 2). But it is not an edge contraction in any sense relevant to graph minors. So I’m not following you.

Finally, I’m not following your remark about Robertson-Seymour not holding in $Graph$ , because RS is a theorem about graphs! I think their graphs are simple graphs without loops, i.e. sets equipped with an irreflexive symmetric relation, but as I noted earlier, there is a bijection between irreflexive and reflexive relations, and I think we can add a loop to every vertex (to make the category theory work better) as long as we’re careful with language in the graph-theoretic statement.

Posted by: Todd Trimble on January 17, 2015 12:39 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Ah yes, surjective does not mean epi. But the definition with the pushout square should still correspond to the contractions: vertices are identified exactly when they are in the same connected component of the image of $f$ . So the example with identifying 0 and 3 to make a triangle should not have a pushout square like this: it would require that all vertices are identified because there has to be a path from 0 to 3 in the image of $f$ .

The process of going to irreflexive graphs to reflexive graphs by adding a loop at every vertex manifestly maintains the orders on subgraphs and contractions, so it shouldn’t change the existence of infinite antichains. But I guess that while contractions work more cleanly for reflexive graphs the definition doesn’t seem to require reflexivity on the face of it (if two different vertices are being identified, their image will have a loop, but if a vertex is left alone it doesn’t need to get a loop per se). And I guess the definition doesn’t even require the graph to be undirected either. So I was wondering if there is an obvious counter example to the theorem in these cases, or if it is feasible that it might still be true.

Posted by: Ibrahim Tencer on January 23, 2015 12:22 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Fascinating stuff! I’m particularly fond of your version 2 of the conjecture, and I’d like to reformulate it a little bit more.

To large extent, it seems that we don’t need to consider the category of graphs as a category. For graphs $X$ and $Y$ , we’re only interested in whether a morphism $X\to Y$ exists, and not so much in how many there are and how they compose with other morphisms. So, we might squash down the category of graphs to a proset of graphs, in which we have $X\geq Y$ if and only if there is a morphism $X\to Y$ ; I like to think of a relation $X\geq Y$ as the statement “ $X$ can be turned into $Y$ ”.

Then, the categorical product becomes the join $\vee$ , the coproduct the meet $\wedge$ , and so we are actually dealing with a lattice. Moreover, I guess that the exponentials turn this lattice into a Heyting algebra?

With this, your version 2 of the conjecture can be phrased as asking whether $X\vee Y\geq K$ implies that $X\geq K$ or $Y\geq K$ . In lattice-theoretic terminology, you are asking whether complete graphs are join primes in the lattice of finite graphs.

Posted by: Tobias Fritz on December 5, 2014 5:29 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Thanks!

I know what you mean by the order being what matters. As Gejza Jenča described rather winningly here, the underlying ordered set of the category of graphs is much more interesting than that of most other familiar categories. For example, it’s dense.

On the other hand, I’m not entirely ready to forget how many homomorphisms there are and pass to the underlying order. I can’t put my finger on why.

Posted by: Tom Leinster on December 5, 2014 5:39 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

By the way: (i) your order relation is the other way round from the one in my post, and (ii) I hope “proset” is a typo rather than an abbreviation for “preordered set”! It would be really confusing, as “pro” is already systematically used a prefix with a completely different meaning (pro- $p$ -group, etc).

Posted by: Tom Leinster on December 5, 2014 5:41 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Tom wrote:

your order relation is the other way round from the one in my post

Right, sorry about that. Feel free to edit my previous comment accordingly.

(The reason for me writing “ $X\geq Y$ ” as representing $X\to Y$ is that I like to think of $X\geq Y$ as stating “if I have $X$ , then I can turn it into $Y$ , and therefore $X$ is at least as good as $Y$ ”.)

I hope “proset” is a typo rather than an abbreviation for “preordered set”!

No, and in fact I thought that this was standard terminology — at least I’ve seen this term being used in this sense on many nLab pages. I hadn’t noticed the clash with other things “pro-” before, so thanks for pointing that out. Would you agree that the term “ordered set” is better, in the sense of a preset equipped with an ordering relation, plus the equality relation defined by the ordering?

Posted by: Tobias Fritz on December 5, 2014 5:56 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

I wrote:

Would you agree that the term “ordered set” is better

Just to clarify the reason for why I didn’t simply suggest “poset” in that context: I’m currently writing a paper in which the protagonists are ordered commutative monoids, in the sense of symmetric monoidal categories enriched over the Booleans. In order to make the terminology more uniform, I’d like to say things like this:

Definition: An ordered commutative monoid is an ordered set equipped with…

But I don’t want to turn this into a discussion on terminology, so I’ll stop here.

Posted by: Tobias Fritz on December 5, 2014 6:06 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

For some reason, the convention among category theorists is that when you turn a poset into a category, you put arrows $a \to b$ in the direction of inequalities $a \leq b$ . So when you turn categories into posets, it would make sense to do things the same way round. But of course, it’s an arbitrary convention. It sits well with situations where maps are injections (such as inclusions), but badly with situations where maps are surjections (such as the product-projections $X \times Y \to Y$ that I used in my post). It’s not important!

I hadn’t heard “proset” before. Maybe I over-reacted to the potential for confusion with “pro” as in “pro-object”; after all, people say “profunctor” without anyone getting confused. As for “preset”, I think I’ve only heard this from nLab users. I don’t understand the definition given on the nLab page. Previously I’d understood it to mean “set equipped with an equivalence relation”, but there’s probably some subtle point of logic that I’m not getting.

Posted by: Tom Leinster on December 6, 2014 11:55 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

I don’t understand presets, but they’re cool. A preset is a gizmo that consists of a rule for ‘generating members’ of it, but not necessarily a rule for proving two members are equal. If you have the latter, and it’s well-behaved, you have a set.

It’s somewhat going against the point of this idea to formalize presets using set theory; the goal seems to be to formalize sets as special presets. This is why it’s a bit hard for set-based mathematicians to understand presets.

Posted by: John Baez on December 15, 2014 2:40 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

One reason why I like this reformulation of Hedetniemi’s conjecture —

for every graph $X$ and complete graph $K$ , either $K^X$ or $K^{K^X}$ has a point

— is that it involves something like double duals, which I’ve been thinking about a lot lately.

There’s a cute way to put this conjecture into words.

Remember that the points of the graph $K_n^X$ are the $n$ -colourings of $X$ . This graph $K_n^X$ might not have any points, but it still makes sense to refer to it as “the graph of $n$ -colourings of $X$ ”, just as it makes sense to talk about pointless locales such as “the locale of surjections $\mathbb{N} \to \mathbb{R}$ ” and “the locale of random sequences of 0s and 1s”.

So, the conjecture says:

for every graph $X$ and $n \geq 0$ , either $X$ has an $n$ -colouring, or the graph of $n$ -colourings of $X$ has an $n$ -colouring.

Posted by: Tom Leinster on December 7, 2014 12:03 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Just to get a bit of exercise, let’s check that the conjecture holds for complete graphs $X$ . This ought to be easy…

We have to show that for complete graphs $K$ , either $K^X$ or $K^{K^X}$ has a point.

If $X$ has no more vertices than $K$ , it’s a pushover. You simply choose an injection $V(X) \to V(K)$ , and that’s a graph homomorphism. So then, $K^X$ has a point.

If $X$ has more vertices than $K$ then clearly $X^K$ has no points, so we’re going to have to show that $K^{K^X}$ has a point. Constructing elements of a double dual is often interesting. Think about vector spaces or ultrafilters, for instance.

It turns out that when $X$ has more vertices of $K$ , there is a point of $K^{K^X}$ that can be described as “choose a nontrivial fibre”. More exactly, we can define a homomorphism $\Phi: K^X \to K$ as follows: for any vertex $f: V(X) \to V(K)$ of $K^X$ , choose an element $\Phi(f) \in V(K)$ such that $\left|f^{-1}\bigl(\Phi(f)\bigr)\right| \gt 1.$ There’s always at least one such element, as $X$ has more vertices than $K$ . A little check reveals that $\Phi$ is a homomorphism — the kind of check that’s actually quite pleasant to do, but is never pleasant to read.

Posted by: Tom Leinster on December 7, 2014 12:17 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Or to put it more dramatically, Hedetniemi’s conjecture is:

Every graph either has an $n$ -colouring, or its graph of $n$ -colourings has an $n$ -colouring.

That doesn’t sound like it makes sense: if $X$ has no $n$ -colouring, surely its graph of $n$ -colourings is empty? Nope — it’s just pointless.

Posted by: Tom Leinster on December 7, 2014 8:04 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Here’s a rather obvious question on trying to generalize the conjecture that you’ve certainly considered already. I haven’t thought about it much, so this might be totally naive. In any case, I’d be curious to know what your thoughts are.

You’ve defined the category of graphs as the category of internal symmetric relations on FinSet. So what if we make the analogous definition in some other regular or Barr-exact category? Can we find a sensible generalization of the conjecture?

The critical issue is to ask what the analogues of the complete graphs might be. In a topos, we could possibly define the complete graph over any object $A$ by taking the complement of the diagonal $A\to A\times A$ to be its object of edges, where I mean “complement” in the sense of negating its characteristic function. Is this sensible? Should we also have to restrict the question to objects $A$ that are finite in some sense?

So, in order to get some idea about how to attack the conjecture, maybe one can try to generalize it first and get some feel for how far one can push generalizations before they are easily seen to be false.

On a different note, there is the De Bruijn–Erdős theorem which states that an infinite graph can be coloured with $k\in\mathbb{N}$ colours if and only if every finite subgraph can. The proof seems related to the fact that an infinite graph is the colimit of its finite induced subgraphs, but I haven’t stared at it long enough to say for sure. In any case, gluing graphs together by taking colimits is something that one might want to do in graph theory, and in order to do so one really needs to look at the category of graphs instead of just the poset of graphs.

Posted by: Tobias Fritz on December 7, 2014 9:27 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

This post:

Gil Kalai, When do a few colors suffice?, December 19, 2014.

says:

When can we properly color the vertices of a graph with a few colors? This is a notoriously difficult problems. Things get a little better if we consider simultaneously a graph together with all its induced subgraphs. Recall that an induced subgraph of a graph $G$ is a subgraph formed by a subset of the vertices of $G$ together with all edges of $G$ spanned on these vertices.

Maybe there’s a category-theoretic perspective on this? Are we replacing the graph by some sort of poset of subobjects? (Not all subobjects, apparently.)

Posted by: John Baez on December 21, 2014 3:17 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Thanks for the link. I guess the induced subgraphs are the regular monics: in other words, the maps that arise as equalizers.

Here’s a question for someone like you who knows lots about logic.

In linear logic, one often thinks of the unit object $I$ of the monoidal category as “falsity”, and of $\mathbf{Hom}(X, I)$ as “not $I$ ”. Here I’m imagining that we’re in a symmetric monoidal closed category, and writing $\mathbf{Hom}$ for the internal hom.

Hedetniemi’s conjecture states that for any graph $X$ and complete graph $K$ , either $K^X$ or $K^{K^X}$ has a point. Now, $K$ isn’t the unit of any monoidal structure that I know of, and besides, there are lots of complete graphs $K$ . Nevertheless, maybe it’s possible to construe the statement

either $K^X$ or $K^{K^X}$ has a point

either $\neg X$ or $\neg \neg X$ has a proof.

The fact that $K^X$ and $K^{K^X}$ can’t both have a point encourages me in this, as does the fact that $K^X$ has a point if and only if $K^{K^{K^X}}$ has a point.

So the question is this. I know there are lots of logics in which $P \vee \neg P$ fails, for some statements $P$ . But in such logics, is it usually the case that $\neg P \vee \neg\neg P$ holds?

(These matters are delicate — probably the answer to the question I just asked depends on exactly how I phrased it. But I’m also interested in answers to differently-phrased questions in the same spirit. So don’t feel the need to interpret the question too literally.)

Posted by: Tom Leinster on December 21, 2014 5:59 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Just to clarify, the mention of linear logic was incidental. My question —

In logics where $P \vee \neg P$ fails, is it usually the case that $\neg P \vee \neg\neg P$ holds?

— was about logics of all kinds. And my idea of interpreting Hedetniemi’s conjecture as a statement about multiple negations wasn’t related to linear logic either.

Posted by: Tom Leinster on December 21, 2014 10:19 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

So the question is this. I know there are lots of logics in which $P \vee \neg P$ fails, for some statements $P$ . But in such logics, is it usually the case that $\neg P \vee \neg\neg P$ holds?

It’s actually fairly rare. Even though it’s not a very strong principle. At least, it’s weaker than the well-ordering of the propositions $(A\rightarrow B)\vee (B\rightarrow A)$ . So there are, I think, plenty of toposes where it holds but the excluded middle doesn’t.

What you always have is $\neg\neg(P\vee\neg P)$ (independently, even of the choice of negation, so $\neg A$ can be chosen to mean $A\rightarrow K$ for an arbitrary $K$ , not that it’s terribly useful for the case at hand).

It’s an entertaining thought, however. As it leads to rephrase the conjecture, in a more logical style, as $K^X + K^{K^X}$ has a point for all $K$ .

Posted by: Arnaud Spiwack on December 22, 2014 12:51 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Thanks! I think I had that fact about $\neg\neg(P \vee \neg P)$ in the back of my mind, without remembering it accurately.

Posted by: Tom Leinster on December 22, 2014 1:00 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Maybe it is useful, then, to note that $\neg\neg(P\vee\neg P)$ is equivalent to $\neg(\neg P \wedge \neg\neg P)$ , so it is an instance of $\neg(Q\wedge \neg Q)$ which, fortunately, holds.

Personally, though, I like to see it more operationally: a function of type $(A+(A\rightarrow K))\rightarrow K$ (an arrow in some ccc with finite sums), is both a function $A\rightarrow K$ and a function $(A\rightarrow K)\rightarrow K$ . Composition gives us a $K$ .

Of course both amount to the same thing. But one of these may be easier to remember.

Posted by: Arnaud Spiwack on December 23, 2014 10:27 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

I’m not sure what to make of it, but your version 2 of the Hedetniemi conjecture actually reminds me a bit of the “focalisation” property of linear logic, which is a way of saying that the inversion properties of the connectives can in a certain sense be turned around. For example, in the case of additive conjunction $A\& B$ , the inversion property says that the $\&$ -right rule sending [a pair of a proof of $\Gamma \vdash A$ and a proof of $\Gamma \vdash B$ ] to [a proof of $\Gamma \vdash A\& B$ ] witnesses an isomorphism. Turning to the other side of the turnstile, in general of course it is not true that [a proof of $A \& B \vdash \Delta$ ] is [either a proof of $A \vdash \Delta$ or a proof of $B \vdash \Delta$ ]. However, the idea behind focusing is that we can “focus” on the formula on the left side of the turnstile $\underline{A\& B} \vdash \Delta$ and temporarily enter a situation where this isomorphism holds: that is, by definition, a proof of $\underline{A\& B} \vdash \Delta$ is either proof of $\underline{A} \vdash \Delta$ or a proof of $\underline{B} \vdash \Delta$ . (The original interest of this was that focusing proof search is complete: that is, any sequent which is provable can be built bottom-up by a repeated cycle of 1. apply invertible rules, 2. pick a formula somewhere in the sequent to focus on, 3. apply focusing rules.)

One easy consequence of focalization (it is also an easy consequence of cut-elimination) is that when the right-hand side $\Delta$ consists purely of atomic formulas, any proof of $A \& B \vdash \Delta$ is either a proof of $A \vdash \Delta$ or a proof of $B \vdash \Delta$ . Which sounds a bit like your version 2, though whether it is of any formal relevance I can’t say…

Posted by: Noam Zeilberger on December 23, 2014 8:38 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

I might add that the category of graphs (sets with symmetric relations) is not just a cartesian closed category: it’s a quasitopos. In more detail, one may calculate that it’s the category of separated presheaves for the $\neg\neg$ -topology on the topos of presheaves on the category $1 \stackrel{\to}{\to} 2$ , or the site of finite sets $1$ and $2$ and injections between them (I’m copying down what I wrote in the nLab article some while back).

One immediate reason for making this comment is that in a quasitopos, one has a classifier for regular monics (not for all monics), so that it would probably be fortuitous if the right notion of subobject for induced subgraph turns out to be regular subobject, as Tom is surmising.

There are some little points to make with regard to linear logic. The term “linear logic” is often used these days in a pretty broad sense, embracing more than the “classical” linear logic first outlined by Girard whose categorical semantics is naturally valued in a $\ast$ -autonomous category. The classical models were really “classical”, in that Girard wanted to retain the law of excluded middle for his so-called multiplicative linear logic, or MLL. Here MLL is interpreted using two monoidal structures, one called “conjunction” which has operations $(\otimes, I)$ [where $I$ = “true”], and one called “disjunction” which has operations $(\wp, D)$ [where $D$ = “false”; I forget the standard way of writing that funny ‘par’ symbol these days, which stands for disjunction], taking $D$ to be the dualizing object for the $\ast$ -autonomous structure. If we interpret linear negation as the contravariant functor $(-)^\ast \coloneqq (-) \multimap D$ , then one can define $A \wp B$ to be $(A^\ast \otimes B^\ast)^\ast$ , and one can witness excluded middle via a canonical map $I \to A^\ast \wp A$ , dual to a map $A \otimes A^\ast \to D$ .

What Tom was referring to looks more to me like some form of what is called multiplicative intuitionistic linear logic, or MILL. Here we don’t have an involutory negation that interchanges two monoidal structures. Often the categorical semantics is taken to be a symmetric monoidal closed category with monoidal product interpreting conjunction and monoidal unit interpreting “true”, but there is some wiggle room in what we might consider as playing the role of “false”, for example maybe some object like a complete graph $K$ . I don’t have any good ideas about this at the moment, but I did want to clarify that “linear logic” can be considered as a rubric for a pretty broad umbrella, and one should be prepared to be flexible and not doctrinaire as to the meaning of the term.

Posted by: Todd Trimble on December 21, 2014 8:28 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Thanks for the generous and learned interpretation of what I wrote about linear logic! The memory of trying to write upside-down ampersands while taking notes in seminars I didn’t understand is pleasantly nostalgic for me.

I know you mentioned before that the category of (reflexive) graphs is a quasitopos. At the time, I didn’t know what to do with that thought. I’m not sure I do now, but this observation of yours did come back into my mind as I began to try out this logical interpretation of $K^X$ .

Posted by: Tom Leinster on December 21, 2014 8:57 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Turn your notes upside down and they might make more sense.

¿əəs

Posted by: John Baez on December 21, 2014 10:06 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

I think Todd said everything about linear logic better than I would have. The fact that there are lots of complete graphs $K$ , most of which don’t seem to be units for interesting tensor products, makes me shy away from thinking of them as meaning ‘false’ in some sort of linear logic, or $K^X$ as a kind of ‘negation’ of the graph $X$ .

Nonetheless, I couldn’t help noting that both Tom and Todd mentioned double negation. Tom was talking about improving the logic of graph theory, making it more classical, by replacing each graph $X$ with some sort of ‘double negation’ $K^{K^X}$ . This is like Gödel’s old trick for embedding classical logic in intuitionistic logic through double negation: when the classical logician says “ $X$ ”, the intuitionistic logician should interpret it as meaning “not not $X$ .” In the case of graph theory, we don’t know that either $X$ or its ‘negation’ has a point, but we know that either the double negation $K^{K^X}$ or its negation has a point. So we’re getting a ‘law of excluded middle’ in an intuitionistic context just as Gödel did.

Later, Todd mentioned that the quasitopos of graphs could be defined using a ‘double negation’ topology. Are these ideas truly related? It would be really cool, but I don’t see how.

I’m a bit more optimistic about the idea that graphs (sets with symmetric relations) form a quasitopos, and the induced subgraphs $i: X \hookrightarrow Y$ are exactly the strong monomorphisms.

(Is the second part true? I think so. Todd and Tom said ‘regular’ monomorphisms, but it’s the strong monomorphisms that are classified by the weak subobject classifier of a quasitopos.)

What did Gil Kalai mean, exactly, by saying it’s “better if we consider simultaneously a graph together with all its induced subgraphs”? We’d have to look at his results and psychoanalyze them to see if there’s a slick category-theoretic way to state this perspective. But that would take work, so maybe first we can ask: is there some standard way to take a topos (or quasitopos) and form a new category of posets, e.g. Heyting algebras (or “quasi-Heyting algebras”, whatever those might be), by taking each object and replacing it with its poset of (strong) subobjects? Obviously there are certain contexts where doing this doesn’t really change anything, like going from the category $Set$ to the category of complete Boolean algebras. But maybe there are contexts, and ways to do this trick, that somehow “improve” the original category.

Posted by: John Baez on December 21, 2014 9:31 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Here’s a simple way to get some ideas. As you both probably know, Lawvere had a schtick about how the graphs category theorists like best — the directed multigraphs—form a presheaf category on the category $1 \stackrel{\to}{\to} 2$ . The fun part of this schtick is that the subobject classifier is a graph, where the two usual truth values — true and false — become vertices, but we also have some edges with nice meanings like “going from truth to truth while staying true”, “going from truth to truth while becoming false”, “going from truth to falsity”, and so on. (Lawvere had other names for these, like “sojourn”.)

One can try to learn to think using this kind of logic: that is, think using the internal logic of the topos of directed multigraphs.

Similarly, one can try to learn to think using the internal logic of the quasitopos of graphs that Tom is studying here: sets with symmetric relations. How does the logic change? There’s at most one way to go from truth to truth, or truth to falsity, etc. And whenever you can go from one to the other, you can go back.

Can we intuitively understand what Todd said, that this quasitopos is the category of separated presheaves on $1 \stackrel{\to}{\to} 2$ with a ‘double negation topology’? Obviously this sets up some functors going between the topos of direct multigraphs and the quasitopos of sets with symmetric relations. But what are these functors like in terms of logic? How is this ‘double negation topology’ related to double negation in logic?

And what’s this trick of ‘making the logic more classical’ by replacing objects $X$ by objects $K^{K^X}$ , where $K$ is a complete graph on $n$ vertices?

What’s the ‘logical’ way of thinking about $K$ ?

Is a strong subobject $i : K \to X$ what graph theorists call an $n$ -element clique? If so, I guess we’re saying $i$ is a kind of proposition about vertices of $X$ , namely that they’re in some $n$ -element induced graph, with the property that you can go between any two vertices where this is proposition is true, using an edge of the sort “going from true to true”.

It would take a while to learn to think in the internal logic of this quasitopos, and only certain people could do it, but a fair fraction of them are reading this blog.

Posted by: John Baez on December 21, 2014 10:02 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Lots here to think about, obviously, but let me just say one thing in response to this:

What’s the ‘logical’ way of thinking about $K$ ?

As I said in the post, complete graphs are in some sense maximal pointless graphs. “Pointless” means that there’s no map $1 \to K$ ; or in the language I’m now trying out, that there’s no proof of $K$ . “Maximal” means that there are as many edges as possible, given that it’s pointless and has the prescribed number of vertices. (It would be nice to put that into logical language.)

The fact that “there’s no proof of $K$ ” is another justification for thinking of $K$ as “false”.

It’s clear that I don’t know how to make any of this precise!

Posted by: Tom Leinster on December 21, 2014 10:15 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Tom wrote:

The fact that “there’s no proof of $K$ ” is another justification for thinking of $K$ as “false”.

You may have talked about this before, but there’s a functor

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

where $1$ is the terminal object, and this sends “pointless” objects to the empty set. That would be one obvious way to formalize your idea. What’s this functor like and how does it interact with

$K^{-} : Graph^{op} \to Graph \quad ?$

Posted by: John Baez on December 22, 2014 2:27 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

What’s the functor $hom(1, -): Graph \to Set$ like? Well, it sends a graph to its set of points (loops). It preserves limits, like all representables. It’s neither full nor faithful.

How does it interact with $K^{-}: Graph^{op} \to Graph$ ? Well, the composite functor $Graph^{op} \to \Set$ sends a graph $X$ to the set $hom(X, K)$ of $K$ -colourings of $X$ .

Am I answering the kinds of question you had in mind?

Posted by: Tom Leinster on December 22, 2014 12:47 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Just a small correction:

In the case of graph theory, we don’t know that either $X$ or its ‘negation’ has a point, but we know that either the double negation $K^{K^X}$ or its negation has a point.

We don’t know the latter: that’s exactly Hedetniemi’s conjecture!

The statement “either $X$ or $K^X$ has a point” is demonstrably false for some values of $X$ and $K$ . E.g. if $X$ is a graph with no loops and $K$ is the complete graph on some number of vertices smaller than the chromatic number of $X$ , then the statement fails.

The statement “either $K^{K^X}$ or $K^{K^{K^X}}$ has a point” is equivalent to “either $K^X$ or $K^{K^X}$ has a point” (since $K^X$ has a point iff $K^{K^{K^X}}$ does). And that last statement in quotation marks is one of the versions of Hedetniemi’s conjecture stated in my post.

Posted by: Tom Leinster on December 21, 2014 10:25 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Tom wrote:

We don’t know the latter: that’s exactly Hedetniemi’s conjecture!

Right. I meant that in this dream you’re cooking up, that’s how things go. But the word ‘know’ was the wrong one.

Posted by: John Baez on December 22, 2014 2:13 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

You’re trying to prove that $hom(1,-)$ and $K^-$ have a rather remarkable interaction, namely either $hom(1,K^X)$ or $hom(1,K^{K^X})$ is nonempty. So I thought that listing all the ways in which these functors get along—either for any object $K$ in any quasitopos, or especially in this one, or especially for these particular objects $K$ —would be helpful. The ones you’ve listed so far aren’t very promising yet; mostly they’re the reasons I asked the question. I was hoping there would be some more tricky and surprising facts already known.

Posted by: John Baez on December 23, 2014 3:53 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Ah, I see what you mean now. Thanks.

(Just logged on to see that lots of people have left interesting comments…)

Posted by: Tom Leinster on December 24, 2014 4:04 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

One category-theoretic line of indirect attack would be this: define an object $K$ in a quasitopos (e.g. a topos) to be false if either $hom(1,K^X)$ or $hom(1,{K^K}^X)$ is nonempty for every object $X$ . What are the most interesting examples of false objects? What do they have in common?

Posted by: John Baez on December 24, 2014 3:41 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Did you mean to say exactly what you said? Wouldn’t $1$ be ‘false’ in that case?

Posted by: Todd Trimble on December 24, 2014 3:58 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Actually, come to think of it, every object would be false in that case, since we can take $X$ to be $K$ and get one of those homs to be nonempty. But maybe you slipped in a typo.

Posted by: Todd Trimble on December 24, 2014 4:00 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Not quite, because John wanted $\mathrm{hom}(1,K^X)$ or $\mathrm{hom}(1,K^{K^X})$ to be nonempty for every $X$ . But I agree that $1$ itself is trivially “false” in John’s sense. More generally, every $K$ which has a point is “false”, since then we have a composite $X\to 1\to K$ .

Posted by: Tobias Fritz on December 24, 2014 4:11 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Oops, yes; sorry.

Posted by: Todd Trimble on December 24, 2014 5:13 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Moreover, if $X$ has a point, then evaluation at that point yields a morphism $K^X\to K$ . Therefore, when checking John’s condition, it is enough to consider ‘pointless’ $X$ .

Posted by: Tobias Fritz on December 24, 2014 4:27 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Okay, I was shooting from the hip and shot myself in the foot, but maybe it’s only a flesh wound. To capture the concept I was vaguely imagining, perhaps I should redefine a false object to be an object $K$ with no points, such that for every object $X$ either $K^X$ or $K^{K^X}$ has a point.

It’s embarrassing, but I need to check: in a topos, or more generally a quasitopos, is $0$ always false in this sense?

I’m trying to capture Tom’s idea that Hedetniemi’s conjecture says any complete graph behaves in some important ways like the empty graph, also known as 0. It seems they both act like ‘false’ in intuitionistic logic.

(It’s obvious but someone must come out and say it: the empty graph is an example of a complete graph.)

Posted by: John Baez on December 25, 2014 5:40 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Sorry to shoot this down, but unfortunately I do not think $0$ is a false object in this new sense.

Let’s remind ourselves that in a quasitopos or even in any cartesian closed category that has an initial object, $0$ is a what is called a strict initial object, which means: if an object $X$ maps to $0$ , $X \to 0$ , then $X$ is isomorphic to $0$ . (Proof: given a map $f: X \to 0$ , we can manufacture a map $\langle 1_X, f\rangle: X \to X \times 0$ . In the other direction, we have a projection map $X \times 0 \to X$ left inverse to the previous map, i.e., the composite of these two maps is $1_X$ . But also, in a cartesian closed category, $X \times -$ is left adjoint to an exponential functor $(-)^X$ , and like any left adjoint it preserves all colimits, including the empty colimit $0$ . Thus $X \times 0 \cong 0$ . Thus $X \to X \times 0 \cong 0$ has a left inverse $!: 0 \to X$ , and $!: 0 \to X$ has a left inverse $f: X \to 0$ (by initiality of $0$ ), and so $!$ and $f$ are inverse to one another.)

Armed with this fact, let $K = 0$ and let $X$ be any object. If $K^X$ has a point, naming a map $X \to K = 0$ , then $X \cong 0$ . In fact $K^X$ has a point iff $X \cong 0$ . But now let’s consider the topos $Set/2$ where $2 = 1 + 1$ – this is the same as the topos $Set^2 \simeq Set \times Set$ if you prefer – and let’s take $X$ to be the object $1 \to 2$ given by the first coproduct inclusion $1 \to 1 + 1$ . (Or the object $(1, 0)$ in $Set \times Set$ if you prefer.) By the above, $K^X$ does not have a point. Now let $Y$ be the object $1 \to 2$ given by the second inclusion, or $(0, 1)$ if you prefer. Then $X \times Y \cong 0 = K$ in this topos, which curries (or should it be curryes?) to a map $Y \to K^X$ . If $K^{K^X}$ has a point, naming a map $K^X \to K = 0$ , then we’d be forced to have $K^X = 0$ by the previous paragraph, and since we also have a map $Y \to K^X = 0$ , we’d be forced into $Y = 0$ , which is a contradiction.

That was probably phrased more circuitously than it might have been, but I hope it’s followable.

I haven’t thought enough about all this to propose a possible fix yet.

Posted by: Todd Trimble on December 25, 2014 6:33 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Todd wrote:

I haven’t thought enough about all this to propose a possible fix yet.

Could you explain a bit more what the problem is with $0$ not being false? Is it just that the term “false” might be a bit off the mark, or is there more to it? Your argument shows that $0$ is not necessarily a false object for both the original definition and the revised one, doesn’t it?

I have two more simple observations, still in terms of the original definition of false objects.

First observation: if $K$ is false, and $K'$ is such that there are morphisms $K\to K'$ and $K'\to K$ , then $K'$ is false as well.

Proof: By currying, $K$ is false whenever for every $X$ there exists $X\to K$ or $K^X\to K$ . If the former happens for a given $X$ , then we also have the composite $X\to K\to K'$ ; if it is the latter $K^X\to K$ , then we have the composite $K'^X \to K^X \to K \to K',$ where the first arrow comes from functoriality of exponentials. Hence $K'$ is false as well.

Second observation: In order to talk about false objects, the structure of a category is more than we actually need! In fact, it is enough to consider the preordered set $P(C)$ determined by the category $C$ . If $C$ is a quasitopos, then $P(C)$ is a Heyting algebra, since the bijection $C(X\times Y,Z)\cong C(X,Z^Y)$ shows that the functor $C\to P(C)$ preserves exponentials. Therefore, $K$ is false in $C$ if and only if it is false in $P(C)$ .

Note that this makes the first observation even more trivial than it already is, because having arrows $K\to K'$ and $K'\to K$ makes the two objects isomorphic in $P(C)$ .

In a Heyting algebra, we can reformulate the definition of false objects a bit further, using the observation that an element (object?) in a Heyting algebra has a point if and only if it is a top element. This implies that $K$ is false if and only if $K^X \vee K^{K^X} \cong 1$ for every $X$ . To me, this suggests that we’re not doing much category theory here, but mostly order theory. In fact, this point of view simplifies Todd’s counterexample significantly: $P$ (Set/2) is the poset whose Hasse diagram looks like a diamond, with bottom and top elements $0$ and $1$ , and intermediate elements $X$ and $Y$ that are not ordered relative to each other. Todd’s argument shows that this poset is itself a quasitopos in which $0$ is not a false object!

Posted by: Tobias Fritz on December 25, 2014 10:39 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Tobias asked:

Could you explain a bit more what the problem is with $0$ not being false?

Maybe no problem! But John seemed to want this, and in any case he asked the question, so I decided to answer.

Posted by: Todd Trimble on December 25, 2014 12:55 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Todd wrote:

Sorry to shoot this down, but unfortunately I do not think $0$ is a false object in this new sense.

Keep on shooting, I’ll just deal with it.

Tobias asked:

Could you explain a bit more what the problem is with $0$ not being false?

In very ‘classical’ categories like $Set$ the principle of excluded middle kicks in and for any object, either $X$ or $0^X$ has a point (and only one does). This fails in more ‘intuitionistic’ categories. But sometimes — and I see I’m quite unclear about exactly when — we can rescue the situation: either $0^X$ or $0^{0^X}$ has a point. I over-optimistically hoped it would be true in every quasitopos, so that then we could march on and ponder other objects $K$ in quasitopoi where either $K^X$ or $K^{K^X}$ has a point… as a warmup to studying Hedetniemi’s conjecture.

Later I saw Arnaud Spiwack’s remark so I realized my hope had to be trimmed down:

Tom wrote:

So the question is this. I know there are lots of logics in which $P \vee \neg P$ fails, for some statements $P$ . But in such logics, is it usually the case that $\neg P \vee \neg\neg P$ holds?

Arnaud replied:

It’s actually fairly rare. [… But] there are, I think, plenty of toposes where it holds but the excluded middle doesn’t.

So now I’m curious about when it holds.

Posted by: John Baez on December 25, 2014 8:42 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

John said:

So now I’m curious about when it holds [that for every $X$ , either $0^X$ or $0^{0^X}$ has a point].

By putting together Tom’s reasoning with Todd’s, we can characterize all those cartesian closed categories with initial object in which this holds: they are precisely those CCCs that do not have ‘zero divisors’, in the sense that $X\times Y\cong 0$ implies $X\cong 0$ or $Y\cong 0$ .

Proof: Going back to Tom’s original post and the proof of the equivalence between versions 2 and 3 of Hedetniemi’s conjecture, you’ll see that the statement “for every $X$ , either $0^X$ or $0^{0^X}$ ” is equivalent to “if there is a morphism $X\times Y\to 0$ , then there is a morphism $X\to 0$ or $Y\to 0$ ”. But by Todd’s comment on strictness of initial objects, this is equivalent to “if $X\times Y\cong 0$ , then $X\cong 0$ or $Y\cong 0$ ”. QED.

As a nice family of examples, let’s consider the topos of sheaves on a topological space.

Claim: The topos of sheaves on a space does not have zero divisors if and only if the space is hyperconnected (also called irreducible).

Proof (of the contrapositive): Suppose we have $X$ and $Y$ with $X\times Y\cong 0$ , but $X\ncong 0$ and $Y\ncong 0$ . This means that there are nonempty opens $U$ and $V$ with $X(U)\neq \emptyset$ and $Y(V)\neq \emptyset$ . But then both $X$ and $Y$ also have a section over $U\cap V$ , and then so does $X\times Y$ . By $X\times Y\cong 0$ , this forces $U\cap V=\emptyset$ . (Recall that every sheaf has exactly one section over the empty set, including the empty sheaf.) Hence $U$ and $V$ are disjoint and nonempty opens, so that the space is not hyperconnected.

Conversely, if the space is not hyperconnected, then we have disjoint nonempty opens $U$ and $V$ , and their indicator sheaves have the empty sheaf as their product. QED.

So, the category of sheaves on a space has the propery that ‘ $0$ is false’ in John’s sense if and only if the space is hyperconnected. Not very surprisingly, the same statement and proof also apply to the topos of presheaves. (And also to the quasitopos of separated presheaves, if products of these can be computed as $(X\times Y)(U)=X(U)\times Y(U)$ , but I’m not sure about this.)

Posted by: Tobias Fritz on December 26, 2014 9:20 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

With regard to Tobias’s last paragraph: separated presheaves form a reflective subcategory of the presheaf category, so the inclusion $SepPreSh \hookrightarrow PreSh$ preserves all limits, and so products in particular can be computed as he says. See the nLab article.

It’s also true that the reflector preserves some finite limits such as products. A paper by Garner and Lack gives more details on this.

Posted by: Todd Trimble on December 26, 2014 1:16 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Tobias wrote:

We can characterize all those cartesian closed categories with initial object in which [for every $X$ , either $0^X$ or $0^{0^X}$ has a point]: they are precisely those CCCs that do not have ‘zero divisors’, in the sense that $X\times Y\cong 0$ implies $X\cong 0$ or $Y\cong 0$ .

That’s very nice! One can imagine the latter as a plausible logical principle, akin to “if $X \& Y$ is false, either $X$ is false or $Y$ is false” — a principle which of course can fail if both $X$ and $Y$ hold ‘somewhere’, but only in non-overlapping locations, as we’d get in a topos of presheaves on a space with two disjoint nonempty open sets.

That makes your followup very nice too: the topos of presheaves (or separated presheaves, or sheaves) on a space has zero divisors iff the space fails to be hyperconnected — that is, iff it contains two disjoint nonempty open sets.

So now I can’t resist asking about the generalization from spaces to sites? Have people defined ‘hyperconnectedness’ for sites?

If so, I guess it must be true that graphs of Tom’s sort are separated presheaves on a ‘hyperconnected’ site. (Todd has already described the site.)

If so, we can think of Hedetniemi’s conjecture as some sort of strengthening of hyperconnectedness, where some nice property of $O$ is shared by all complete graphs.

Have people looked at such strengthenings? Can we?

Posted by: John Baez on December 27, 2014 6:38 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

John asked:

(Is the second part true? I think so. Todd and Tom said ‘regular’ monomorphisms, but it’s the strong monomorphisms that are classified by the weak subobject classifier of a quasitopos.)

Happily, in a quasitopos the regular monomorphisms and strong monomorphisms coincide. So we’re okay there. (I don’t know who wrote that into the nLab, but anyway I think the result could probably be found in Wyler’s notes.)

By the way, my picture of the site was slightly wrong. The words were right, but my picture should have included a loop $\stackrel{2}{\circlearrowright}$ to indicate the nontrivial automorphism on $2$ that interchanges co-source and co-target – that’s the baby that puts the “symm” in “symmetric graph”. Without that automorphism, the separated presheaves on the presheaf topos would be the category of simple directed graphs (i.e., sets equipped with a binary relation).

Posted by: Todd Trimble on December 21, 2014 11:08 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Happily, in a quasitopos the regular monomorphisms and strong monomorphisms coincide. So we're okay there. (I don't know who wrote that into the nLab, but anyway I think the result could probably be found in Wyler's notes.)

I think I remember that Wyler glosses over this very quickly. But it’s just a matter of writing the pullback diagram for the classifier as an equivalent equaliser diagram (a classified mono $f:A\rightarrow B$ equalises its characteristic function $\chi_f$ and the top element $\top:B\rightarrow A$ ).

In fact Wyler’s definition of a quasitopos is a topos where some collection of monos is classified (it follows that the classified monos are precisely the equalisers, which includes (hence equals) the strong monos).

Posted by: Arnaud Spiwack on December 22, 2014 12:34 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

OK, so we’ve got the subcategory $C$ of $Set$ consisting of the objects $1$ and $2$ and the injections between them.

A presheaf on $C$ consists of a directed multigraph $E \stackrel{\to}{\to} V$ together with an involution $\sigma$ of $E$ that exchanges source and target. That almost amounts to an undirected multigraph (with each undirected edge represented by a pair of arrows in $E$ in opposite directions). But not quite, as we have to think about the behaviour of the involution $\sigma$ on loops. It might fix some of them.

I haven’t tried to work through what the separated presheaves for the double negation topology are, but you’re telling me that they’re exactly the symmetric graphs, i.e. sets equipped with a symmetric binary relation. I guess that means they’re just those presheaves such that for all vertices $x$ and $y$ , there’s at most one directed edge from $x$ to $y$ . Is that right?

Posted by: Tom Leinster on December 22, 2014 12:58 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Is that right?

That’s right. Actually the calculation is easy as pie. But since I seem to rehearse this type of argument to myself every few months or so, I might as well write it down somewhere I can find it again if I’m in a hurry.

So let $C$ be this category of finite sets $1$ , $2$ and injections between them. You can think of a presheaf on $C$ as a directed graph equipped with a direction reversing involution on the set of edges. We want to determine those presheaves $X: C^{op} \to Set$ such that, for every $\neg\neg$ -dense sieve $i: F \hookrightarrow \hom(-, c)$ , the induced map

$X(c) \cong Set^{C^{op}}(\hom(-, c), X) \stackrel{i^\ast}{\to} Set^{C^{op}}(F, X)$

is monic. Being $\neg\neg$ -dense means that $\neg\neg F$ , as a subobject of $\hom(-, c)$ , is all of $\hom(-, c)$ . Which is the same as saying $\neg F = 0$ – or that the only subgraph that doesn’t intersect $F$ is the empty subgraph. So let’s work out what that means.

For $c = 1$ , there are only two subgraphs of $\hom(-, 1)$ , the empty graph and $\hom(-, 1)$ . The only dense subobject is $F = \hom(-, 1)$ ; there are no other dense subobjects. So this case is uninteresting and we can ignore it.

For $c = 2$ , there are again precious few subgraphs of $\hom(-, 2)$ . [Maybe take a moment to draw this graph.] For example, if a subgraph contains either of the two edges of $\hom(-, 2)$ , the $C$ -action can be used to generate all of $\hom(-, 2)$ . So the only proper subgraphs are the discrete ones (the ones with no edges), and the only one of those which is dense is the one with both vertices of $\hom(-, 2)$ , namely the subobject

$\langle s, t \rangle: \hom(-, 1) + \hom(-, 1) \to \hom(-, 2)$

which names those two vertices $s, t$ . So $F = \hom(-, 1) + \hom(-, 1)$ .

Thus, for $c = 2$ , the induced map

$X(2) \cong Set^{C^{op}}(\hom(-, 2), X) \to Set^{C^{op}}(\hom(-, 1) + \hom(-, 1), X) \cong X(1) \times X(1)$

is required to be monic, and this is the only condition imposed by being separated as a presheaf. So we are talking about a subobject $X(2) \hookrightarrow X(1) \times X(1)$ closed under the symmetry, i.e., a set equipped with a symmetric relation.

You can apply the same type of reasoning to see all of the following categories, in addition to the one above, as quasitoposes of separated $\neg\neg$ -presheaves on a smallish category:

The category of monomorphisms between sets, as separated presheaves on the interval category $\mathbf{2}$ . (You may have heard of $\mathcal{M}$ -categories; these are categories enriched in this quasitopos.)
The category of sets equipped with a relation, as separated presheaves on $G_1 = (0 \stackrel{\overset{s}{\to}}{\underset{t}{\to}} 1)$ (a truncation of the globular category).
The category of sets equipped with a reflexive relation, as separated presheaves on a truncated reflexive globular category.
The category of sets equipped with a reflexive symmetric relation, as separated presheaves on the full subcategory of finite sets consisting of just the objects $1$ , $2$ .

Posted by: Todd Trimble on December 22, 2014 6:00 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

People who liked this thread might like

Daniel Glassock, What is a graphon?

which discusses (among other things) the homomorphism density of graphs $G$ and $H$ , meaning the fraction of maps from vertices of $G$ to vertices of $H$ that are graph homomorphisms.

It’s a fun short expository paper.

Posted by: John Baez on January 9, 2015 3:18 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Just for the record: Hedetniemi’s conjecture has been solved in the negative.

Posted by: Tobias Fritz on June 6, 2019 11:17 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Wow!

Posted by: Tom Leinster on June 7, 2019 10:36 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Let me try and say a little about the proof, whose outline I now very roughly understand.

The disproof of Hedetniemi’s conjecture — by Yaroslav Shitov — is almost an explicit counterexample. I’ll come back to that “almost” in a minute.

Shitov disproves what I called “version 3” of the conjecture. In other words, he finds a graph $X$ and a complete graph $K$ such that there is neither a homomorphism $X \to K$ nor a homomorphism $K^X \to K$ . Translated into the usual product form of the conjecture, this means that

$\chi(K^X \times X) \lt \min \{ \chi(K^X), \chi(X)\}.$

In the language I used at the start of the post, that means there’s a “clever way” of colouring $K^X \times X$ .

Graphs of the form $K^X$ , where $K$ is complete, are apparently called exponential graphs. This seems to be standard terminology, and it’s what Shitov calls them in his paper.

Which $X$ and $K$ does Shitov use in his counterexample (or really, family of counterexamples)?

The graph $X$ he uses is of the form $G \boxtimes K_q$ , where $\boxtimes$ is the strong product. Neither the graph $G$ nor the integer $q$ are constructed explicitly; Shitov merely shows that a $G$ and a $q$ with the required properties exist. Whether it’s possible/easy to extract explicit constructions from his proof, I don’t know.

The complete graph $K$ that Shitov uses is the complete graph $K_c$ on $c$ vertices, where $c$ is any integer $\geq 4.1q$ . So that bit’s easy.

Gil Kalai’s blog post that Tobias linked to says more.

Posted by: Tom Leinster on June 8, 2019 10:47 AM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

Thank you for that clear summary!

Posted by: Tobias Fritz on June 8, 2019 7:36 PM | Permalink | Reply to this

Re: Graph Colouring and Cartesian Closed Categories

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

So, if we phrase Hedetniemi’s conjecture this way:

For any positive integer $c$ , if $G \times H$ is $c$ -colorable, then at least one of $G$ and $H$ is $c$ -colorable.

then Shitov’s original counterexample showed that this fails whenever $c$ is at least

55693855195583437727553364327396134337075543 30137402259007803366576263631846530012824600 59975265063449541297555370411048668054775558 52514627107682125515309915185481864749328003
9413353545728

Today on the arXiv Xuding Zhu brought this down to 912.

For all we know at this point, it could go down to 5.

Posted by: John Baez on April 21, 2020 3:11 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

December 5, 2014