Coloring the Odd Distance Graph

Importance: High ✭✭✭

Author(s):

Subject:	Graph Theory
	» Coloring
	» » Vertex coloring

Keywords:	coloring
	geometric graph
	odd distance

Recomm. for undergrads: no

Posted	by:	mdevos
	on:	October 3rd, 2007

The Odd Distance Graph, denoted ${\mathcal O}$ , is the graph with vertex set ${\mathbb R}^2$ and two points adjacent if the distance between them is an odd integer.

Question Is $\chi({\mathcal O}) = \infty$ ?

This question is a relative of the famous problem about coloring the Unit Distance Graph (the graph on ${\mathbb R}^2$ where two points are adjacent if the distance between them is 1). See Moshe's online lecture Famous and lesser known problems in “elementary” combinatorial geometry and number theory at time 15:20 for a nice introduction.

Perhaps the first property of ${\mathcal O}$ to determine is the size of the largest complete subgraph (were ${\mathcal O}$ to contain arbitrarily large complete subgraphs, its chromatic number would be $\infty$ ). It is obvious that ${\mathcal O}$ contains triangles, but perhaps surprisingly, it does not contain a complete subgraph on four vertices. In other words, there do not exist four points in ${\mathbb R}^2$ so that all pairwise distances are odd. This was a problem on the Putnam Exam in 1993, and is proved by Rosenfeld in [R1] and [R2].

A natural strengthening of the above question is to ask if there exists a proper $n$ -coloring $f: V({\mathcal O}) \rightarrow \{1,2,\ldots,n\}$ so that $f^{-1}(\{i\})$ is a measurable set for every $i$ . Such colorings are called measurable colorings, and interestingly, the Odd Distance Graph has no finite measurable coloring. This follows from immediately from a theorem of Furstenberg, Katznelson and Weiss [FKW] which asserts that for every measurable subset $A \subseteq {\mathbb R}^2$ with positive upper density, there exists a number $r$ so that $A$ contains a pair of points at distance $r'$ for every $r' > r$ . This theorem has a number of independent proofs, see also Falconer and Marstrand [FM], Bourgain [Bo], and Bukh [Bu].

All that seems to be known about the (usual) chromatic number of ${\mathcal O}$ is that $\chi({\mathcal O}) \ge 5$ .

Bibliography

[Bo] J. Bourgain, A Szemerédi type theorem for sets of positive density in $R\sp k$ . Israel J. Math. 54 (1986), no. 3, 307--316. MathSciNet

[Bu] B. Bukh, Measurable sets with excluded distances.

[FM] K. J. Falconer and J. M. Marstrand, Plane sets with positive density at infinity contain all large distances. Bull. London Math. Soc. 18 (1986), no. 5, 471--474. MathSciNet

[FKM] H. Furstenberg, Y. Katznelson, and B. Weiss, Ergodic theory and configurations in sets of positive density. Mathematics of Ramsey theory, 184--198, Algorithms Combin., 5, Springer, Berlin, 1990. MathSciNet

[R1] M. Rosenfeld, Odd integral distances among points in the plane. Geombinatorics 5 (1996), no. 4, 156--159. MathSciNet

[R2] M. Rosenfeld Famous and lesser known problems in “elementary” combinatorial geometry and number theory (video lecture - time 15:20)

* indicates original appearance(s) of problem.

add new comment

The Odd-Distance Graph

On March 19th, 2012 Anonymous says:

In the book Research Problems in Discrete Geometry, on page 252, it is stated that every K_4 free graph is a subgraph of the odd distance graph. We just proved that W_5, the five wheel is not a subgraph of the odd distance graph. I further believe that there are triangle free graphs that are not subgraphs of the odd distance graph, and even graphs with large girth.

Flaw

On May 8th, 2008 JSteinhardt says:

Actually, it appears there is a flaw with the below proof. The spectral bound on the chromatic number assumes a measurable coloring, as we want to say the following:

$2(\chi-1)\lambda_{\min}||f||^2 & = & \sum_{i,j=1}^{\chi} \lambda_{\min}||f_i-f_j||^2$ $\leq \sum_{i,j=1}^{\chi} \langle f_i-f_j, B(f_i-f_j) \rangle$ $= \sum_{i,j=1}^{\chi} \langle f_i,Bf_i \rangle + \langle f_j,Bf_j \rangle - 2\langle f_i,Bf_j \rangle$ $= -2\sum_{i,j=1}^{\chi} \langle f_i,Bf_j \rangle$ $= -2\langle\sum_{i=1}^{\chi} f_i,B(\sum_{i=1}^{\chi} f_i\rangle$ $= -2\langle f,Bf \rangle$ $= -2\lambda ||f||^2$

but this assumes that each $f_i$ is Lesbegue integrable, which in turn requires measurable coloring classes.

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)}$ .

Solution (continued)

On May 4th, 2008 JSteinhardt says:

We see that the eigenvalue of the eigenfunction $f_{(r,s)}$ is given by

$\lambda_{(r,s)} = \int_{-\pi}^{\pi} \sum_{k=0}^{\infty} a^{-k} e^{i(2k+1)(r\cos(t)+s\sin(t))} dt = \int_{-\pi}^{\pi} \sum_{k=0}^{\infty} a^{-k} e^{i(2k+1)\sqrt{r^2+s^2}\cos(t+\phi)} dt$

for an appropriately chosen $\phi$ . Thus we need only actually consider $\lambda_{(r,0)}$ , which we from now on denote $\lambda(r)$ . Then some calculation gives us that the integral is

$\int_{-\pi}^{\pi} \frac{a(a-1)\cos(r\cos(t))}{(a-1)^2+4a\sin^2(r\cos(t))} dt$

We can show that (and this will suffice) that when $a$ is near $1$ ,

$\int_{0}^{\frac{\pi}{2}} \frac{(a-1)\cos(r\cos(t))}{(a-1)^2+4a\sin^2(r\cos(t))} dt \geq -4(a-1)^{-\frac{3}{4}}-\frac{\pi}{2}$

Solution (final part)

On May 4th, 2008 JSteinhardt says:

Let $h$ be the function we are integrating. Let $R_k$ denote the region for which $|h(t)| \geq 1$ and that contains the value of $t$ where $\cos(t) = \frac{k\pi}{r}$ . Then we note that $|\int_{R_k} h(x) dx| > |\int_{R_{k-1}} h(x) dx|$ and the sines of the integral alternate, so we can just calculate the first one and everything else will be bounded (in particular by $\frac{\pi}{2}$ ). With a bit of Taylor approximation, we can bound the size of each $R_k$ by $\frac{4\sqrt[4]{a-1}}{\sqrt{r}}$ , and noting that $h$ is always positive for $r \leq \frac{\pi}{2}$ , we can replace the $\sqrt{r}$ with $1$ and then bound $h$ by $\frac{1}{a-1}$ . This gives us the bound we claimed above and we are done.

Jacob Steinhardt

Circular chromatic number of the odd distance graph

On October 31st, 2007 Anonymous says:

The proof for $\chi(G)\geq 5$ has been recently extended to $\chi_c(G)\geq 5$ , which implies the previous result, where $\chi_c$ is the circular chromatic number.