Metric chromatic numbers and Lovasz numbers

In 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!  I learned it from these notes, written by Big L himself.

Let M be a metric space, and let’s assume for simplicity that M has a transitive group of isometries.  Now write r_M(n) for the radius of the smallest ball containing n points whose pairwise distances are all at least 1.  (So this function is controlling how sphere-packing works in M.)

Let Γ be a graph.  By an M-coloring of Γ we now mean a map from v(Γ) to M such that adjacent vertices are at distance at least 1.  Write χ_Γ(M) for the radius of the smallest disc containing an M-coloring of Γ.  Then we can think of r^{-1}(χ_Γ(M)) as a kind of “M-chromatic number of Γ.”  Scare quotes are because r isn’t necessarily going to be an analytic function or anything; if I wanted to say something literally correct I guess I would say the smallest integer n such that r_M(n) >= χ_Γ(M).

The M-chromatic number is less than the usual chromatic number χ_Γ;  more precisely,

χ_Γ(M) <= r_M(χ_Γ)

Easy:  if there’s an n-coloring of Γ, just compose it with the map from [n] to M of radius r_M(n).  Similary, if ω_Γ is the clique number of Γ, we have

r_M(ω_Γ) <= χ_Γ(M)

because a k-clique can’t be embedded in a ball of radius smaller than r_M(k).

So this M-chromatic number gives a lower bound for the chromatic number and an upper bound for the clique number, just as the Lovasz number does, and just as the fractional chromatic number does.

Example 1:  Lovasz number.  Let M be the sphere in infinite-dimensional Euclidean space.  (Or |Γ|-dimensional Euclidean space, doesn’t matter.)  For our metric use (1/sqrt(2)) Euclidean distance, so that orthogonal vectors are at distance 1 from each other.  If n points are required at pairwise distance at least 1, the closest way to pack them is to make them orthonormal (I didn’t check this, surely easy) and in this case they sit in a ball of radius 1-sqrt(1/2n) around their center of mass.  So r_M(n) = 1 – sqrt(1/2n).  Define t(Γ) to be the real number such that

1 - \sqrt{1/2t(\Gamma)} = \chi_\Gamma(M).

Now I was going to say that t(Γ) is the Lovasz theta number of Γ, but that’s not exactly the definition; that would be the definition if I required the embedding to send adjacent vertices to points at distance exactly 1.  The answer to this MO question suggests that an example of Schrijver might actually separate these invariants, but I haven’t checked.

So I guess let’s say t(Γ) is a “Lovasz-like number” which is between the clique number and the chromatic number.  And like the Lovasz number, but unlike clique and chromatic numbers, it’s super-easy to compute.  An embedding of v(Γ) in the sphere, up to rotation, is specified by the pairwise distance matrix, which can be an arbitrary postive definite symmetric nxn matrix A with 1’s on the diagonal.  Each edge of Γ now gives an inequality a_{ij} > 1.  When you’re optimizing over a space cut out by linear inequalities in the space of psd matrices, you’re just doing semidefinite programming.  (I am punting a little about how to optimize “radius” but hopefully maximum distance of any vector from center of mass is good enough?)

(Note:  you know what, I’ll bet you can take an embedding like this, subtract a small multiple of the center of mass from all the vectors, and get an embedding of v(Γ) in n-space with all angles between adjacent vectors slightly obtuse, and probably this ends up being exactly the same thing as the vector chromatic number defined in the paper I linked to earlier.)

Where is example 2?  It was supposed to be about the fractional chromatic number but then I realized the way I was setting this up wasn’t correct.  The idea is to let M_b be the space of infinite bit strings with exactly b 1’s and use (1/2b) Hamming distance, so that the distance-1 requirement becomes a requirement that two b-element subsets be disjoint.  But I don’t think this quite fits into the framework I adopted at the top of the post.  I’ll circle back to this if I end up having what to say.




Tagged , ,

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: