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.

June 26, 2007

Colorings of Graphs

Posted by Urs Schreiber

Just heard a talk by Dmitry Kozlov on combinatorial algebraic topology, concerned mainly with the problem of coloring graphs.

I didn’t fully understand many of the points and unfortunately I didn’t have the chance of asking the speaker about more details afterwards. Hence this here is not a report of the talk, but rather a vague mentioning of some aspects and a couple of questions. It feels like much of what Kozlov had to say would be of quite some interest to an nn-categorical audience, if maybe just because there might be room to make that nn-categorical structure more explicit.

The main point is this:

given a graph GG, we are looking for colorings of its vertices such that no two vertices connected by an edge have the same color. What is the minimum number of colors, the chromatic number χ(G), \chi(G) \,, such that such a coloring exists?

If the graph is the dual of a triangulation drawn on a plane, the answer is given by the famous four color theorem to be χ(G)=4. \chi(G) = 4 \,. The proof of that is not easy and in particular not elegant. This is symptomatic for the coloring problem more generally: exact answers are hard to come by. What one aims for instead are good estimates, lower bounds in particular, of χ(G)\chi(G).

One nice way to reformulate the problem of graph colorings, which all of Kozlov’s machinery is based on, amounts to realizing that a consistent (i.e. no equal-colored neighbours) coloring of a graph GG with nn-colors is the same as a graph morphism c:GCodisc(n). c : G \to \mathrm{Codisc}(n) \,. Here Codisc(n)\mathrm{Codisc}(n) is what graph theorists apparently call the “complete” graph on nn vertices, which here I call the codiscrete graph on nn vertices: it has precisely one edge from each of its vertices to every other.

A morphism of graphs is much like a functor of the corresponding categories, but with the important constraint that every edge has to go to an edge: as opposed to the categories generated from them, the graphs have no “identity edges”. (And, by the way, I think Kozlov assumes throughout all graphs to be oriented, to have at most one edge for every ordered pair of vertices, and to have no edges from a vertex to itself.)

This is what makes the above reformulation possible: a morphism from a graph GG to a codiscrete graph Codsic(n)\mathrm{Codsic}(n) will label each vertex of GG with one of the nn colors, and cannot assign the same color to two neighbouring vertices.

So then, the next step is to get a handle on the Hom-spaces Hom Graph(G,Codisc(n)) \mathrm{Hom}_{\mathrm{Graph}}(G,\mathrm{Codisc}(n)) in the category of graphs.

The crucial point of Kozlov’s work is that he realizes these Hom spaces as simplicial complexes. I don’t quite understand the precise definition in detail yet. You can find it for instance as definition 2.1.5 on p. 11 of

Dmitry N. Kozlov
Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
arXiv:math/0505563v2.

So this looks like we are secretly talking about an \infty-category of graphs now, or something like this. I don’t know.

The point is that using these simplicial complexes, the space of all possible graph colorings becomes more accessible. Kozlov proves powerful theorems using these complexes, in particular the Lovász conjecture:

For a graph GG, such that the complex Hom(C 2r+1,G)\mathrm{Hom}(C_{2r+1},G) is kk-connected for some integers r>0r\gt 0 and k>2k \gt -2, we have χ(G)>k+3. \chi(G) \gt k+3 \,.

(Here C nC_n is the graph corresponding to the nn-gon.)

The general strategy is to map these simplicial complexes functorially to topological spaces, and then use known obstruction theory of these spaces to determine if Hom(G,T)\mathrm{Hom}(G,T) can be nontrivial at all.

In this context I was quite intrigued by what Kozlov said about spin structures. As described in section 3 of the above paper, there is a way to use the theory of Stiefel-Whitney characteristic classes to study the Hom-complexes of graphs. That sounds fascinating, since it seems to indicate a relation of the abstract coloring problem – which has the appearance of being “of academic interest” only (if you know what I mean) – to interesting geometric and maybe even physical questions. I’d like to better understand this.

But not right now. I need to call it a day.

Posted at June 26, 2007 9:38 PM UTC

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

31 Comments & 1 Trackback

Re: Colorings of Graphs

This work seems to point to a bridge between the two cultures of mathematics. To see MacLane’s name appearing under Lovász’s in the bibliography of the paper by Koslov you mention is a sign.

Posted by: David Corfield on June 27, 2007 7:17 AM | Permalink | Reply to this

Re: Colorings of Graphs

Interesting stuff!

A simplicial complex is somewhat different from a simplicial set, but they’re closely related, so perhaps you won’t mind me talking about the latter instead of the former.

The word graph means many different things. A directed graph where every vertex xx has a chosen ‘identity’ edge from xx to itself is an example of a simplicial set. An undirected graph without loops is an example of a simplicial complex.

The category of simplicial sets is very nice: in particular, it’s cartesian closed, so given simplicial sets XX and YY there’s a simplicial set hom(X,Y)hom(X,Y), the ‘internal hom’.

So, if you allow me to work with directed graphs with identity edges, say XX and YY, and think of them as simplicial sets, there’s a very nice way to make hom(X,Y)hom(X,Y) into a simplicial set. The vertices of hom(X,Y)hom(X,Y) are the hopefully obvious structure-preserving maps from XX to YY. The edges of hom(X,Y)hom(X,Y) are ‘homotopies’ between such maps — but only ‘directed’ homotopies, I guess. And so on. It’s all very nice.

I don’t know if the category of simplicial complexes is cartesian closed; I’d be mildly shocked if it were.

Posted by: John Baez on June 28, 2007 7:54 AM | Permalink | Reply to this

Re: Colorings of Graphs

So, if you allow me to work with directed graphs with identity edges,

Unfortunately, I cannot allow you to do that! :-)

At least not unless you can somehow nicely introduce a certain constraint on morphism of such graphs.

Namely if we want to be able to say that a consistent (no equal neighbouring colors) coloring of some graph GG by nn colors is the same as a morphism of graphs GCodsic(n) G \to \mathrm{Codsic}(n) then this is true only if we don’t allow any “identity edges” in Codisc(n)\mathrm{Codisc}(n). It is precisely the absence of these identity edges which encodes the constraint “no equal neighbouring colors”.

(But recall that all I know about this comes from a 60 minute talk which didn’t make it far beyond the introduction before running out of time, and from spending 20 minutes or so with looking at the referenced literature.)

Posted by: urs on June 28, 2007 10:02 AM | Permalink | Reply to this

Re: Colorings of Graphs

I don’t know if the category of simplicial complexes is cartesian closed; I’d be mildly shocked if it were.

It is. If KK and LL are simplicial complexes, then define the vertices of hom(K,L)hom(K, L) to be maps of simplicial complexes KLK \to L, and define a finite set SS of maps ff to be a simplex if

fSf(σ)\bigcup_{f \in S} f(\sigma)

is a simplex of LL whenever σ\sigma is a simplex of KK.

See Marco Grandis’s paper here (section 1.4).

Posted by: Todd Trimble on June 28, 2007 1:57 PM | Permalink | Reply to this

Re: Colorings of Graphs

WARNING to the youngsters:

Originally they were complete semi-simplical complexes
CSS-complexes
then semi-simplicial complexes
then simplicial sets

whereas once upon a time a simplicial complex meant a (usually finite) union of
geometric simplices

jim

Posted by: jim stasheff on June 28, 2007 5:52 PM | Permalink | Reply to this

Re: Colorings of Graphs

And now I (and others?) like to use semi-simplicial set to mean a ‘simplicial set without degeneracies’, i.e. a contravariant Set-valued functor on the category of nonempty finite totally ordered sets and order-preserving injections.

Is that wholesome?

Posted by: Tom Leinster on June 28, 2007 6:35 PM | Permalink | Reply to this

Re: Colorings of Graphs

Dangerous - given the history.
Suggest : facial

jim

Posted by: jim stasheff on June 28, 2007 9:19 PM | Permalink | Reply to this

Re: Colorings of Graphs

By the way, is there an accepted precise meaning of ‘cell complex’? Brief wikipedia-ing suggests not, but I’d rather have an answer from an insider.

Posted by: Tom Leinster on June 28, 2007 6:37 PM | Permalink | Reply to this

Re: Colorings of Graphs

In any case, I think Kozlov is looking at an enrichment of the category of graphs over simplicial complexes.

He simply writes down a concrete definition for the simplicial Hom-complex Hom(G,T)\mathrm{Hom}(G,T) between two graphs GG and TT.

I feel like this step must have a more conceptual basis. Does anyone know what’s really going on here?

Posted by: urs on June 28, 2007 8:06 PM | Permalink | Reply to this

Re: Colorings of Graphs

Jim Stasheff warned, among other things:

once upon a time a simplicial complex meant a (usually finite) union of geometric simplices

Right: here we are talking about abstract simplicial complexes (a purely combinatorial notion). Here I’m following Spanier’s Algebraic Topology, where all singletons of a simplicial complex are simplexes; for some reason unbeknownst to me, some algebraic topologists like to drop that condition. Also, in the aforementioned paper by Grandis, the empty set is considered to be a simplex (of dimension -1), a harmless but convenient assumption.

I’ve also seen (e.g., in Paul Taylor’s Practical Foundations of Mathematics) the term simplicial complex applied to a contravariant functor from the category of finite sets and injective functions to Set. That’s not at all the same as the notion we’re using here!

Posted by: Todd Trimble on June 28, 2007 8:08 PM | Permalink | Reply to this

Re: Colorings of Graphs

Just a small footnote to the implicit question in

“where all singletons of a simplicial complex are simplexes; for some reason unbeknownst to me, some algebraic topologists like to drop that condition.”

Not having singletons be simplexes is indeed an unusual convention; I can’t see any reason for it, and was just taken aback reading that there should be topologists adopting it, or rather, taken aback by reading you raise this issue at all; usually, as you imply, singletons are simply 0-dimensional simplexes, and the convention that {}\{\} is a (-1)-dimensional simplex is also very usual. The reasons for that are also the usual ones: similar to the usefulness of the number 0, having these low-dimensional structures makes machines run smoothly. (Or: more quietly at least, by removing the need to spell out inessential exception-conditions.)

This is not to ‘start an argument’ or something, you probably know all that, just a footnote amplifying what was in this post anyway.

Posted by: Peter Heinig on October 2, 2017 12:20 PM | Permalink | Reply to this

Re: Colorings of Graphs

John wrote:

So, if you allow me to work with directed graphs with identity edges,

Urs wrote:

Unfortunately, I cannot allow you to do that! :-)

Hmm, so maybe we really need to work with undirected graphs. Can these graphs have loops, or more than one edge between vertices?

If not, we’re in business: then these graphs are just simplicial complexes where the highest dimension of a simplex is 1. This allows us to define a simplicial complex of maps between our graphs, since…

John wrote:

I don’t know if the category of simplicial complexes is cartesian closed; I’d be mildly shocked if it were.

but then Todd wrote:

It is.

I’m mildly shocked!

If Grandis’ construction works the way I’m guessing, we can really take two graphs XX and YY — that is, simplicial complexes where the highest dimension of a simplex is 1 — and see that nn-simplices in hom(X,Y)hom(X,Y) are a simplicial way of describing homotopies between homotopies between… maps from XX to YY.

In other words, if we think of the simplicial complex hom(X,Y)hom(X,Y) as a topological space, it’s homotopy equivalent to the space of continuous maps from XX to YY, where we regard these graphs as spaces too.

Suppose this is true. The next question is: how interesting can this space hom(X,Y)hom(X,Y) be? The graphs XX and YY can be any space with homotopy groups π n\pi_n vanishing for n>1n \gt 1. Given this, what’s the maximum possible homotopy dimension of hom(X,Y)hom(X,Y)? That is, what’s the highest nn for which the homotopy group π n(hom(X,Y))\pi_n(hom(X,Y)) can be nonzero?

I’ll guess the answer is just n=1n = 1. If it’s higher, I’ll be mildly shocked.

The reason this matters is that Urs suggested there’s an interesting nn-category of graphs lurking around here. The approach I’m describing makes graphs into a category enriched over simplicial complexes. But since simplicial complexes are a model for homotopy types, we get an (,1)(\infty,1)-category of graphs: that is, an \infty-category where all jj-morphisms are invertible for j>1j \gt 1.

However, it’s quite possible that this is ‘overkill’. If the maximum homotopy dimension of hom(X,Y)hom(X,Y) is nn, we essentially have just an (n+1,1)(n+1,1)-category: an (n+1(n+1-category where all jj-morphisms are invertible for j>1j \gt 1.

And, if n=1n = 1, we basically just have 2-category where all 2-morphisms are invertible.

My reason for guessing that the maximum homotopy dimension of hom(X,Y)hom(X,Y) for graphs XX and YY is just 1 comes from the case where XX and YY are homotopy equivalent to circles. In this case hom(X,Y)hom(X,Y) is homotopy equivalent to hom(S 1,S 1)hom(S^1,S^1), which I’m betting is homotopy equivalent to a disjoint union of circles!

(If I were really pretending to be a homotopy theorist, I’d just say “is” instead of constantly saying “is homotopy equivalent to”.)

Posted by: John Baez on June 28, 2007 9:45 PM | Permalink | Reply to this

Re: Colorings of Graphs

The reason this matters is that Urs suggested there’s an interesting n-category of graphs lurking around here. The approach I’m describing makes graphs into a category enriched over simplicial complexes.

Right, but Kozlov and Lovasz are considering a somewhat different enrichment, aren’t they?

Posted by: Todd Trimble on June 28, 2007 10:38 PM | Permalink | Reply to this

Re: Colorings of Graphs

John wrote

In this case hom(X,Y) is homotopy equivalent to hom(S 1,S 1)hom(S^1,S^1), which I’m betting is homotopy equivalent to a disjoint union of circles!

Looks good! pick a basepoint bb in the source S 1S^1 and bb' in S 1S^1. The subspace of fhom(S 1,S 1)f\in hom(S^1,S^1) sending bb to f(b)=bf(b)=b' is homotopy-equivalent to a countable infinite discrete space; specifically, π 1(S 1)Z\pi_1 (S^1) \simeq \Z. But each component of hom(S 1,S 1)hom(S^1,S^1) is then homotopic to the target circle S 1S^1 (let b’ vary). So hom(S 1,S 1)hom(S^1,S^1) is homotopic to a countable disjoint union of circles.

I think… there is something suspicious, though…

Posted by: some guy on the street on June 30, 2007 8:05 AM | Permalink | Reply to this

Re: Colorings of Graphs

I’ve remembered what it was! Maybe.

Is the subject “abstract” simplical graphs, or geometric graphs? Because—to be a bit simplistic (oh dear!)—i.i.r.c, the morphisms between abstract simplicial complexes are essentially functions mapping the vertices of one complex to vertices of the other such that abstract simplices map to abstract simplices. Right? So for finite graphs, the complex of graph morphisms ought to have finitely many vertices in it… is this making any sense? Is it relevant?

Posted by: some guy on the street on June 30, 2007 8:23 AM | Permalink | Reply to this

Re: Colorings of Graphs

someone on the street wrote:

Is the subject “abstract” simplical graphs, or geometric graphs?

The former.

is this making any sense?

Yes, it’s making sense. The question is how to most clearly define the ‘simplicial complex of graph morphisms’ — and Todd answered it, as far as I can tell.

Posted by: John Baez on June 30, 2007 4:47 PM | Permalink | Reply to this

Re: Colorings of Graphs

Also, the comment from some guy on the street shows that a continuous map |K||L||K| \to |L| is generally not homotopic to the realization of a simplicial map KLK \to L (e.g., when |K|=S 1=|L||K| = S^1 = |L|), if K,LK, L are given a priori. One has to pass to better and better simplicial approximations of the polyhedra to approximate maps.

In other words, while there is a canonical map

ϕ:|hom(K,L)|hom(|K|,|L|)\phi: |hom(K, L)| \to hom(|K|, |L|)

coming from the composite

|hom(K,L)|×|K||hom(K,L)×K||eval||L||hom(K, L)| \times |K| \cong |hom(K, L) \times K| \stackrel{|eval|}{\to} |L|

the map ϕ\phi is generally not a homotopy equivalence.

Posted by: Todd Trimble on June 30, 2007 5:55 PM | Permalink | Reply to this

Re: Colorings of Graphs

Tom asked about the meaning of ‘cell complex’.

Some people may use ‘cell complex’ loosely to mean CW complex, piecewise-linear CW complex or various other things. I may have been guilty of this myself, in my youth.

But, homotopy theorists like to make the category of topological spaces into a model category where the cofibrations are ‘relative cell complexes’, and this gives the term ‘cell complex’ a very precise definition, which I now support.

Roughly speaking, a map of spaces

XYX \to Y

is a relative cell complex if YY is built from XX by repeatedly attaching finite-dimensional balls along their boundaries… where ‘repeatedly’ means we get to use transfinite induction. If XX is empty, we then say YY is a cell complex.

So, the cell complexes defined this way are the cofibrant objects in TopTop!

A cell complex is a CW complex if the cells are attached in order of increasing dimension.

If you want more precision, try page 30 here:

  • Mark Hovey, Model Categories, AMS, Providence, Rhode Island, 1999.

for a general definition of ‘relative II-cell complex’, and then page 51 for what this amounts to in the case of topological spaces.

Since cofibrant objects are important, and CW complexes aren’t quite general enough to be the cofibrant objects in TopTop, I think using the word ‘cell complex’ for the necessary slight generalization is a good idea.

Posted by: John Baez on June 28, 2007 10:15 PM | Permalink | Reply to this

Re: Colorings of Graphs

A little more precision is needed for CW complex.
CW had meaning (not just an allusion to their creator jhCWhitehead):
Closure finite in the
Weak topology
so not just in order of increasing dim

this used to be standard Homotopy Theory 101

Posted by: jim stasheff on June 28, 2007 10:29 PM | Permalink | Reply to this

Re: Colorings of Graphs

Jim wrote:

this used to be standard Homotopy Theory 101

I’m sure it still is. I learned all about CW complexes in Homotopy Theory 101 with Whitehead — G. W., not J. H. C. But, he should not be blamed for my mistake.

Posted by: John Baez on June 28, 2007 10:44 PM | Permalink | Reply to this

Re: Colorings of Graphs

That’s useful information; thanks.

For present purposes I’m disappointed, because I’m writing something where I’d like to use ‘cell complex’ in a vague way (like a young Baez, perhaps) to mean some kind of space formed by sticking together a load of cells. Maybe I’ll go ahead and do it anyway.

Posted by: Tom Leinster on June 30, 2007 6:30 PM | Permalink | Reply to this
Read the post Bridge Building
Weblog: The n-Category Café
Excerpt: Might the cohomology of dynamical systems provide a meeting ground for researchers on the 'combinatorics' side of mathematics, and those on the 'theory-building' side?
Tracked: December 23, 2008 1:21 PM

Re: Colorings of Graphs

Just for the record, I thought I’d point out that all the graphs in the Babson-Kozlov theory are un-oriented, meaning that if there’s an edge from v to w, there’s a corresponding edge from w to v. And most of the time people just think of this as a single undirected edge.

Posted by: Dan Ramras on July 6, 2010 11:19 PM | Permalink | Reply to this

Re: Colorings of Graphs

That’s ambiguous. Do you mean .__. is no allowed but .== . is so to speak?

Posted by: jim stasheff on July 7, 2010 12:52 PM | Permalink | Reply to this

Re: Colorings of Graphs

I remember reading somewhere (perhaps papers of Vigna) that it is a good to think of un-directed graphs as directed graphs with specified involutions. Then maps of undirected graphs are equivariant maps of directed graphs with involutions and it’s clear what to do with loops.

Posted by: Eugene Lerman on July 7, 2010 7:21 PM | Permalink | Reply to this

Re: Colorings of Graphs

it is a good to think of un-directed graphs as directed graphs with specified involutions.

Dagger-graphs!

In line with \dagger-simplicial sets.

Posted by: Urs Schreiber on July 8, 2010 7:18 AM | Permalink | Reply to this

Re: Colorings of Graphs

Dagger-graphs!

Exactly.

In line with †-simplicial sets.

Yes, but much simpler than †-simplicial sets.

Posted by: Eugene Lerman on July 8, 2010 2:31 PM | Permalink | Reply to this

Re: Colorings of Graphs

Exactly.

Is this relation explicitly made use of anywhere in the literature?

but much simpler than †-simplicial sets.

Because a graph is a 1-skeletal simplicial set. We can just as well talk about \dagger-\infty-graphs.

Posted by: Urs Schreiber on July 8, 2010 2:36 PM | Permalink | Reply to this

Re: Colorings of Graphs

Is this relation explicitly made use of anywhere in the literature?

I don’t know the literature on dagger graphs all that well. I think this point of view may show up in

Graphs of morphisms of graphs by R. Brown, I. Morris, J. Shrimpton and C.D. Wensley,

in

P. Boldi and S. Vigna. Fibrations of graphs. Discrete Math. 243 (1-3) (2002) 21–66.

and, tangentially, in

S. Vigna. A guided tour in the topos of graphs. Technical Report 199-97, Universita di Milano, Dipartmento di Scienze dell’Informazione (1997). http://arXiv.org/abs/math.CT/0306394.

Posted by: Eugene Lerman on July 8, 2010 3:29 PM | Permalink | Reply to this

Re: Colorings of Graphs

Thanks for the links. Unfortunately I don’t have time to browse through these references now. What keyword do I need to look for, anyway?

I was gonna put a commented references list at \dagger-graph, but not sure.

Posted by: Urs Schreiber on July 8, 2010 3:42 PM | Permalink | Reply to this

Re: Colorings of Graphs

What keyword do I need to look for, anyway?

Not sure, but “dagger-graph” probably will point you back to this thread :).

I must have come across all this stuff when I was looking for two different things:

  • analogue of a Cayley graphs for a category free on a graph,

  • etale maps of directed graphs, which turned out to to go by the name of “graph fibrations” and half a dozen other names besides.

Dagger graphs should be related to complex systems consisting of interacting Hamiltonian systems. Sort of like Bond graphs that John Baez has been blogging about, but for conservative systems.

Posted by: Eugene Lerman on July 8, 2010 4:53 PM | Permalink | Reply to this

Re: Colorings of Graphs

(Small technical comment on the nice opening post: it is of course correct to write

If the graph is the dual of a triangulation drawn on a plane, the answer is given by the famous four color theorem to be χ(G)=4.

yet the usual way of stating the Four Color Theorem has another antecedent, namely ‘If the graph is any loopless planar countable multigraph’.

Yes, usually, proofs of the FCT make some reduction to triangulations, but I just would like to point out the obvious: not every planar loopless multigraph is “the dual of a triangulation in the plane”. E.g. the 4-circuit isn’t: the only way to realize the 4-circuit as a dual is as the dual of the dipole graph with four edges.)

Posted by: Peter Heinig on October 2, 2017 12:37 PM | Permalink | Reply to this

Post a New Comment