# What is known about the chromatic number for minimum-distance graphs in higher dimensions?

For a set of points in $\mathbb{R}^d$ with minimum distance $a$, the minimum-distance graph connect two points iff they are at distance $a$. We can also view it as the tangency graph for a set of unit balls, so the upper bound for the chromatic number is obviously the one-side kissing number.

It is known that for large dimensions, the chromatic number for unit-distance graphs has an exponential lower bound (Frankl and Wilson), and the chromatic number for largest-distance graphs has a sub-exponential lower bound (Kahn and Kalai).

What is the best known bound for the chromatic number for minimum-distance graphs? Is there already a (sub-)exponential lower bound or a polynomial upper bound?

This is a very good question. Maybe I miss something but I don't know an example where the lower bound is not polynomial. There is an example of an infinite periodic configuration where the minimum degree is superpolynomial ($d^{\log d}$ or so) so it will be interesting to check what is the chromatic number in this case. (The kissing number in $R^d$ is exponential so the maximum degree can be exponential in $d$.) There are examples of linear binary codes where the degree of the minimum distance graph is exponential. Those are candidates to give superpolynomial or even exponential chromatic number.
• What is the best lower bound known to you? The best lower bound to my knowledge is linear ($2d$). I only know a construction with minimum degree at least $2^{\sqrt d}$ due to N. Alon. Do you have the references to the examples you mentioned? Jan 6, 2016 at 15:47