Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 12, 2013

Colouring a Graph

Posted by Tom Leinster

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 GG and HH,

The chromatic number of G×HG \times H is the minimum of the chromatic numbers of GG and HH.

It’s amazing that something so basic is unknown!

For this post, a graph is a finite set equipped with a symmetric, irreflexive binary relation. The elements of the finite set VV are called the “vertices”, the relation is usually called EE, 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 nn, the complete graph K nK_n has vertex-set {1,,n}\{1, \ldots, n\} and an edge between ii and jj whenever iji \neq j.

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

(x,y)E(f(x),f(y))E. (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 GG by nn colours, or an nn-colouring of GG for short, is a way of painting each vertex one of nn 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 nn-colouring of a graph GG is the same thing as a homomorphism GK nG \to K_n.

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

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

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

The functoriality of colouring means that χ(G)χ(H)\chi(G) \leq \chi(H) whenever there is a homomorphism GHG \to H. Categorically put, χ\chi is a functor χ:Graph(,). \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 mnm \to n when mnm \leq n, and there are no maps mnm \to n when m>nm \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)G = (V, E) and H=(W,F)H = (W, F), the vertex-set of G×HG \times H is V×WV \times W, and there’s an edge between (v,w)(v, w) and (v,w)(v', w') if and only if there are an edge between vv and vv' and an edge between ww and ww'. The projections G×HGG \times H \to G and G×HHG \times H \to H are what you’d expect.

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

χ(G×H)min{χ(G),χ(H)}\chi(G \times H) \leq \min\{ \chi(G), \chi(H) \} for all graphs GG and HH.

The conjecture is that this is an equality:

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

It’s known to be true for various classes of GGs and HHs, 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×HG \times H has no sneakily economical colourings. In other words, if your aim is to colour G×HG \times H with as few colourings as possible, you can’t improve on the following strategy: either colour GG minimally and then declare the colour of (x,y)G×H(x, y) \in G \times H to be the colour of xGx \in G, or do the same with the roles of GG and HH reversed.

Categorically, the conjecture can be expressed as follows:

Conjecture (Hedetniemi) The functor χ:Graph(,)\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, GraphGraph is a full subcategory of Graph LGraph_\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 xx has a loop on it, then there’s an edge between xx and xx, 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

χ:Graph L{}. \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 11, the terminal graph-with-loops, contains a loop, we have χ(1)=\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 GG is a homomorphism 1G1 \to G. In categories of spaces, a map from the terminal object to a space XX is often called a point of XX. 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 GG or HH contains a loop. For if GG contains a loop then we have a homomorphism 1G1 \to G, which induces another homomorphism

H1×HG×H. H \cong 1 \times H \to G \times H.

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

So the conjecture can equivalently be reformulated as:

Conjecture (Hedetniemi) The functor χ:Graph L{}\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 LGraph_\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 nK_n. But what’s so special about the K nK_ns? 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 GraphGraph and Graph LGraph_\text{L} is somehow helpful here.

Posted at April 12, 2013 12:54 AM UTC

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

52 Comments & 0 Trackbacks

Re: Colouring a Graph

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

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

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

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

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

Re: Colouring a Graph

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

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

  • a choice of full subgraph SGS \triangleleft G
  • an nmn-m-colouring of GSG - S of which there are χ GS(nm)\chi_{G-S}(n-m), a polynomial in mm and nn.
  • a function V SmV_S \to m of which there are m V Sm^{V_S}, again a polynomial

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

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

Re: Colouring a Graph

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

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

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

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

Can’t one call self loops “identities” and establish an n-coloring of a graph with loops via an identity reflecting homomorphism to L nL_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 nL_ns are enriched in 1, and one can use hom definitions to define sub categories of Graph LGraph_L. For example the functor irefl:Graph LGraphirefl : Graph_{L} \to Graph that forgets identities can be defined as:

hom(irefl(a),irefl(b))=not(equal(a,b))hom(a,b)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

Part of the problem might be that the product of graphs seems to have no clear geometric meaning. For example K 2K_2 looks like an interval so I would expect K 2×K 2K_2 \times K_2 to resemble a square but instead it is a disjoint union of two K 2K_2s. 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

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

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)G = (V, E) and H=(W,F)H = (W, F), the vertex-set of GHG \square H is V×WV \times W, and there is an edge between (v,w)(v, w) and (v,w)(v', w') if and only if:

  • either v=vv = v' and there is an edge between ww and ww'

  • 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 2K_2. Magically, the symbol ×\times also depicts the categorical product of two copies of K 2K_2! As Karol observes, K 2×K 2K_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) χ(GH)=max{χ(G),χ(H)}\chi(G \square H) = \max \{\chi(G), \chi(H)\} for all graphs GG and HH.

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

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

“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

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: supg=\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

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

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

At the end of the post, I wrote:

The chromatic number functor is defined in terms of the complete graphs K nK_n. But what’s so special about the K nK_ns? 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 GraphGraph determined by the K nK_ns is equivalent to the category of finite sets and injections.

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

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

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

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

Re: Colouring a Graph

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 opSet Graph Y: Graph^{op} \to Set^{Graph}

which assigns to any graph GG the functor

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

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

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

|hom(G,K n)| |\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 nK_n are just one of many sequences of graphs Γ n\Gamma_n such that the cardinality

|hom(G,Γ n)| |hom(G,\Gamma_n)|

is a polynomial in nn. 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 χ Γ(G)\chi_\Gamma(G) be the smallest nn such that hom(G,Γ n)hom(G,\Gamma_n) is nonempty, and ask if

χ Γ(G×H)=χ Γ(G)χ Γ(H)\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

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: χ Γ(G×H)=min{χ Γ(G),χ Γ(H)}. \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 GG have the property that the class of all graphs not admitting a homomorphism into GG 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 nG = K_n, it says: if XX and YY are graphs with χ(X)>n\chi(X) \gt n and χ(Y)>n\chi(Y) \gt n then χ(X×Y)>n\chi(X \times Y) \gt n. In other words, if XX and YY are graphs with min{χ(X),χ(Y)}>n\min\{\chi(X), \chi(Y)\} \gt n then χ(X×Y)>n\chi(X \times Y) \gt n. Taken over all nn, this says that min{χ(X),χ(Y)}χ(X×Y)\min\{\chi(X), \chi(Y)\} \leq \chi(X \times Y) for all XX and YY. 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

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 ee of a graph GG, we can obtain two new graphs. We can delete ee (and keep the same vertices) to obtain a new graph GeG - e. Or, we can contract ee (that is, delete ee and then identify the two vertices that it joined) to obtain a new graph G/eG/e.

Write p G(n)p_G(n) for the number of nn-colourings of a graph GG. Pick an edge ee of GG. Then

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

Why? Let’s say that ee joins vertices aa and bb.

  • An nn-colouring of GeG - e that gives aa and bb different colours is the same thing as an nn-colouring of GG.

  • An nn-colouring of GeG - e that gives aa and bb the same colour is the same thing as an nn-colouring of G/eG/e.

That does it. So

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

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

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

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

  • There is a polynomial f(x,y)f(x, y) such that for all graphs GG and edges ee,

|Hom(G,Γ n)|=f(|Hom(Ge,Γ n)|,|Hom(G/e,Γ n)|) |Hom(G, \Gamma_n)| = f\bigl(|Hom(G - e, \Gamma_n)|, |Hom(G/e, \Gamma_n)|\bigr)

In the case Γ n=K n\Gamma_n = K_n, we have f(x,y)=xyf(x, y) = x - y.

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

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

I’m sure this is all obvious to any graph theorist. The next question is: are there interesting examples of sequences of graphs (Γ n)(\Gamma_n), other than (K n)(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

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

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

  • A C nC_n-colouring of GeG-e that gives aa and bb the same colour is the same thing as a C nC_n-colouring of G/eG/e.

  • A C nC_n-colouring of GeG-e that gives aa and bb colours that are adjacent in C nC_n is the same thing as a C nC_n-colouring of GG.

  • There may also be C nC_n-colourings of GeG-e that give aa and bb distinct non-adjacent colours in C nC_n. For n3n \leq 3 all colours are adjacent, but for n>3n \gt 3 there are n(n3)n(n-3) such pairs (since aa can take any of nn colours, and then bb can take any colour that’s not the same as, or one of the two neighbours of, aa’s colour).

So, writing c G(n)c_G(n) for the number of C nC_n-colourings of graph GG, we get: c G(n)=c Ge(n)c G/e(n)min(0,n(n3)) c_{G}(n) = c_{G-e}(n) - c_{G/e}(n) - min(0,n(n-3))

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

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

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

Re: Colouring a Graph

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

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

Re: Colouring a Graph

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 GeG-e in which aa and bb 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

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

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

(1)χ G(n)=χ G(n1)+ S:starDisjoint +Gχ GS(n1) \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)(|V_G|-1) — specifically, that each term is a polynomial of degree |V GS||V_G - S|; and the rest is “easy”.


Stuart wants to calculate the “cyclic” colourings of graphs; we can remark that GG having a C nC_n-colouring means the cycles of GG have lengths kn+2mk n + 2 m for natural numbers kk and mm, not both zero; so we actually have that #Hom(G,C n)# Hom(G,C_n) converges to zero unless GG is bipartite. But in particular, C n+2C_{n+2} has a nice family of edgewise-surjective C nC_n colourings, which might be handy for generalizing the previous kind of argument. On The Other Hand, the function #Hom(G,C n)# 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)K(a,b,c): these will have cycles of lengths 33 when abc>0abc\gt 0, 44 if ab+bc+ac4ab+bc+ac \geq 4, and 55 as soon as a+b+c>3a + b + c \gt 3; and so C nC_n will also have lots of K(a,b,c)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

OK, a+b+c>3a + b + c \gt 3 is not the right criterion. Say min(a,b,c)=2\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

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,53,4,5 in a K(a,b,c)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

I’m perfectly happy to find sequences of graphs Γ n\Gamma_n such that the number of homomorphisms from any graph GG to Γ n\Gamma_n is eventually a polynomial in nn, that is, for large enough nn. 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= n=0 A nA = \sum_{n=0}^\infty A_n with finitely many homogeneous generators and relations, I believe the dimension dim(A n)dim(A_n) is eventually a polynomial, called the Hilbert polynomial of AA. (Not to be confused with the Hilbert series!)

The interesting part is that there’s typically a ‘glitch’ near the beginning: dim(A n)dim(A_n) only agrees with the Hilbert polynomial when nn is greater than equal to some number called the Hilbert regularity of AA. 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)A(G) associated with a graph GG such that dim(A n(G))\dim(A_n(G)) is the number of nn-colorings of GG.

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

Re: Colouring a Graph

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)A(G) associated with a graph GG such that dim(A n(G))dim(A_n(G)) is the number of nn-colorings of GG.

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

Clearly there are bijections

m×nmn m \times n \cong m n

where now I’m using mm to mean some standard mm-element set, and similarly for nn and mnm n. So clearly there’s a way to take an mm-coloring and an nn-coloring and reinterpret the pair of them as an mnm 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 nn-element set for each nn, so we can say

m×n=mn m \times n = m n

and where the niggly ‘associator’ isomorphisms

(×m)×n×(m×n) (\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)A(G) such that A n(G)A_n(G) has, as its basis, the nn-colorings of GG.

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

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

Let’s try to make up an associative way to multiply an mm-coloring and an nn-coloring and get an mnm n-coloring.

I noted before that there’s a functor

K:FinSet injGraph K\colon FinSet^{inj} \to Graph

sending a finite set II to K IK_I, the complete graph with vertex-set II. Here FinSet injFinSet^{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 injFinSet^{inj} given by cartesian product. (It’s not actually the categorical product in FinSet injFinSet^{inj}, because the product-projections want to be non-injective.)

There’s also a monoidal structure on GraphGraph 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 KK. In other words, for each finite set II and finite set JJ, there’s a natural map

ϕ I,J:K I×K JK I×J. \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×JI \times J), and ϕ I,J\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 GG and finite sets II and JJ, we have a map

Hom(G,K I)×Hom(G,K J)Hom(G,K I×K J)ϕ I,JHom(G,K I×J). 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 II-colouring of GG is a map GK IG \to K_I, this is a way of taking an II-colouring together with a JJ-colouring and producing an I×JI \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))(A_I(G)) of vector spaces indexed by finite sets II: you wanted a family (A n(G))(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 n\langle n\rangle for each number nn, and choose a total ordering on n\langle n\rangle. As Jamie pointed out, lexicographic ordering defines a bijection

m×nmn \langle m \rangle \times \langle n \rangle \to \langle m n \rangle

for each mm and nn. This gives the functor

FinSet inj n n \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 GG a string of lax monoidal functors

FinSet injKGraphHom(G,)Setfree VSVect. \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 Vect\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

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 FinSetFinSet (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 injVect A(G) : FinSet^{inj} \to Vect

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

Of course the lax monoidal functor

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

is even ‘better’, since it gives rise to A(G)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

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 injFinTot^{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 XX and YY are finite totally ordered sets then XYX \otimes Y is the set X×YX \times Y with the lexicographic ordering. Then the functor \langle -\rangle I defined above is really a monoidal functor FinTot inj\mathbb{N} \to FinTot^{inj}.

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

FinTot injforgetFinSet injKGraphHom(G,)Setfree VSVect. \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

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)A(G) associated with a graph GG such that dim(A n(G))dim(A_n(G)) is the number of nn-colorings of GG.

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)= nA n(G) A(G) = \bigoplus_{n \in \mathbb{N}} A_n(G)

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

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

instead of the more usual

A m(G)A n(G)A m+n(G) 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 GG, a standard graded algebra whose Hilbert polynomial equals the chromatic polynomial of GG. 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

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

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, n)Hom(G,\square^n) as a sum over cuts of GG, but for obvious reasons it more than doubles from nn to n+1n+1.

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

The same trick that leads to |Hom(G,C n)|| Hom (G, C_n) | eventually-linear also leads to |Hom(G,T m,n)||Hom(G,T_{m,n})| eventually-cm×nc m\times n, where T m,nT_{m,n} is either C mC nC_m \square C_n or a regular triangulation of a torus. A boxy torus is bipartite, and lots of triangulated tori are 33-colourable — though in at most three ways. In general, it seems that one wants the diameter of Γ n\Gamma_n to grow much slower than the vertex number. The complete graph K nK_n has nn vertices and is of diameter 11.

Since K nK_n is the relation of being disjoint size-1 subsets of n\langle n\rangle, one might be interested the relation of being size-ll-intersecting size-kk-subsets of n\langle n \rangle; let’s call these graphs Inc l,k,nInc_{l , k , n}.

In the family Inc 1,2,nInc_{1,2,n}, an Inc 1,2,n+1Inc_{1,2,n+1}-colouring of GG has an Inc 1,2,nInc_{1,2,n}-colouring of a full subgraph SS and a special nn-colouring of the complement of SS… but clarifying how that works or looking for relations with different IncInc-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

It turns out that Inc 0,k,nInc_{0,k,n} gives what are called kk-fold multicolourings of a graph; and I now have an argument that the number of Inc l,k,nInc_{l,k,n}-colourings is polynomial in nn. It involves nn-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

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

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

Writing min as a semigroup operation looks neater

χ(G×H)=χ(G)χ(H)\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

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

On any category C\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: Groups\mathbf{Groups} or Vect\mathbf{Vect} give you a one-element poset; mathSets\math{Sets} gives you a two elements poset “empty” and “nonempty” and so on. Nothing interesting.

Graphs\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 GG and HH such that there is an arrow GHG\to H and there is no arrow HGH\to G, there is a graph KK such that there are arrows GKHG\to K\to H, but no arrow KGK\to G nor HKH\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

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

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

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

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

induced by the monoidal functor

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

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

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

which itself induces the inclusion

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

In other words, the adjunction

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

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

PosetCat. \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

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

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

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:XYf: X \to Y where YY is a subgraph of XX, such that the restriction of ff to YY is the identity map.

19.19. If XX and YY are connected graphs, then show that K nK_n is a retract of X×YX \times Y only if it is a retract of XX or a retract of YY.

20.20. Show that Hedetniemi’s conjecture is equivalent to the statement that K nK_n is a retract of the product X×YX \times Y of two graphs only if it is a retract of XX or a retract of YY.

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

Re: Colouring a Graph

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 nn.

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

if \emptyset is a retract of X×YX \times Y then \emptyset is a retract of XX or of YY.

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

if X×YX \times Y is empty then XX is empty or YY is empty.

That’s true.

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

if X×YX \times Y is nonempty and discrete then either XX or YY is nonempty and discrete.

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

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

if X×YX \times Y is bipartite and not discrete then either XX or YY is bipartite and not discrete.

The discreteness part is easy: assuming X×YX \times Y is not discrete, neither XX nor YY is discrete.

I guess a graph is bipartite if and only if it contains no cycles of odd length. So then, if XX is non-bipartite then it contains a cycle of odd length kk, and if YY is also non-bipartite then it contains a cycle of odd length \ell, in which case X×YX \times Y contains a cycle of odd length lcm(k,)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 nn.

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

Re: Colouring a Graph

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

… 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

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 nn-colouring of a graph GG would not correspond any more to all graph maps from GG to K nK_n but only to those that have the right lifting property w.r.t. the inclusion 2K 22\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 nK_n are exactly those fibrant objects that are weakly equivalent to 11.

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

Re: Colouring a Graph

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

Sorry, this should of course read:

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

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

Post a New Comment