Metric chromatic numbers

Idle thought.  Let G be a (loopless) graph, let M be a metric space, and let b be a nonnegative real number.  Then let Conf(G,M,b) be the space of maps from the vertices of the graph to M such that no two adjacent vertices are within b of each other.

When b=0 and G is the complete graph K_n, this is the usual ordered configuration space of n points on M.  When G is the empty graph on n vertices, it’s just M^n.  When M is a set of N points with the discrete metric, Conf(G,M,b) is the same thing for every b;  a set of points whose cardinality is χ_G(N), the chromatic polynomial of G evaluated at N.  When M is a box, Conf(G,M,b) is the “discs in a box” space I blogged about here.  If M is (Z/2Z)^k with Hamming distance, you are asking about how many ways you can supply G with k 2-colorings so that no edge is monochromatic in more than k-b-1 of them.

Update:  Ian Agol links in the comments to this paper about Conf(G,M,0) by Eastwood and Huggett; the paper points out that the Euler characteristic of Conf(G,M,0) computes χ_G(N) whenever M has Euler characteristic N; so M being N points works, but so does M = CP^{N-1}, and that’s the case they study.

When b=0 and G is the complex plane, Conf(G,C,0) is the complement of the graphic arrangement of G; its Poincare polynomial is  t^-{|G|} χ_G(-1/t).  Lots of graphs have the same chromatic polynomial (e.g. all trees do) but do they have homeomorphic Conf(G,C,0)?

This is fun to think about!  Is Conf(G,M,0), for various manifolds other than discrete sets of points, an interesting invariant of a graph?

You can think of

vol(Conf(G,M,b)) vol(M)^{-n}

as a sort of analogue of the chromatic polynomial, especially when b is small; when M = C, for instance, Conf(G,M,b) is just the complement of tubular neighborhoods around the hyperplanes in the graphical arrangement, and its volume should be roughly b^|G|χ_G(1/b) I think.  When b gets big, this function deviates from the chromatic polynomial, and in particular you can ask when it hits 0.

In other words:  you could define an M-chromatic number χ(G,M) to be the smallest B such that Conf(G,M,1/B) is nonempty.  When M is a circle S^1 with circumference 1, you can check that χ(G,M) is at least the clique number of G and at most the chromatic number.  If G is a (2n+1)-cycle, the clique number is 2, the chromatic number is 3, and the S^1-chromatic number is 2+1/n, if I did this right.  Does it have anything to do with the Lovasz number, which is also wedged between clique number and chromatic number?  Relevant here:  the vector chromatic number, which is determined by χ(G,S^{v(G)-1}), and which is in fact a lower bound for the Lovasz number.





Tagged , , ,

3 thoughts on “Metric chromatic numbers

  1. It’s amusing to see the set of proper colouring of the graph described as “a set … whose cardinality is χ_G(N), the chromatic polynomial of G evaluated at N.”

  2. […] the first post of this series I asked whether there was a way to see the Lovasz number of a graph as a chromatic number.  Yes! […]

  3. ianagol says:

    You might be interested in this article, which tells one something about Conf(G,M,0).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: