11
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Hao Chen
    Commented Jan 6, 2016 at 15:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .