Home ยป Coloring the Odd Distance Graph

Solution

On May 4th, 2008 JSteinhardt says:

I believe I have a solution. I will sketch it here. (Sorry, it's broken up into three posts because I cannot figure out how to post something more than 1000 characters...but I have seen longer solutions posted elsewhere so I assume it's okay; if not, I apologize.)

Consider the operator $ B_{a} : L^2(R^2) \to L^2(R^2) $ defined by

$$(B_{a}f)(x,y) = \int_{-\pi}^{\pi} \sum_{k=0}^{\infty} a^{-k} f(x+(2k+1)\cos(t),y+(2k+1)\sin(t)) dt$$

This is in some sense a weighting of the adjacency operator. We can then prove the result (well-known for finite graphs) that $ \chi(O) \geq 1-\frac{\lambda_{\max}}{\lambda_{\min}} $, where $ \lambda_{\max},\lambda{\min} $ are the sup and inf of the spectrum of $ B_{a} $.

We note that the eigenfunctions of $ B_{a} $ are simply the exponential maps $ f_{(r,s)}(x,y) = e^{i(rx+sy)} $.

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options