Given a set of points on the plane you can construct unit distance graph by taking the points as vertices, and setting two points as adjacent if the distance between the two points is one.

I am curious about something analogous to this on a sphere.

Is there anything known about, for a fixed angle $\theta$ and dimension $n$, the graph whose vertices are the unit vectors in $\mathbb{R}^n$ with a pair of vertices adjacent if only if the angle between the two vectors are exactly $\theta$. I will refer to this as $G(n, \theta)$.

I am wondering if there are any bounds on the chromatic number of $G(n, \theta)$? I know for example that it contains $K_{n-1}$ because, if you set $\alpha = \sqrt{\cos{\theta}}$ and $\beta = \sqrt{1-\cos{\theta}}$ the vectors

  • $(\alpha, \beta, 0, 0,\ldots, 0)$
  • $(\alpha, 0, \beta, 0, \ldots, 0)$
  • ...
  • $(\alpha, 0, 0, \ldots, \beta)$

are all adjacent.

If you set $n = N^2 + N + 1$ and $\theta = \arccos{\frac{1}{N+1}}$, then you can get $K_n$ by having the dimensions correspond to the points in a projective plane of size $n$, and having the unit vectors correspond to the $n$ lines with $N+1$ non-zero entries each $\frac{1}{\sqrt{N+1}}$ for each point in the line.

I there a way to get subgraphs in $G(n, \theta)$ with high chromatic numbers?

  • $\begingroup$ As in the Hadwiger-Nelson problem, you obtain a finite colouring by dividing the sphere into patches of angular diameter less than $\theta$. $\endgroup$ – Anthony Quas Mar 11 '18 at 4:35
  • $\begingroup$ What exactly do you mean by the angle between two vectors $u$ and $v$? Is it the same as the angle between $u$ and $-v$? If not, then for $\theta$ great than $\pi/2$ the graph is related to the Lovasz theta function. Also for $\theta > \pi/2$ your construction for finding $K_{n-1}$ does not necessarily work. For instance, if $\theta = \pi$ then only antipodal vectors are adjacent, so the graph is just a perfect matching. $\endgroup$ – David Roberson Mar 12 '18 at 9:20
  • $\begingroup$ I believe the graph is also somewhat related to the topological bound for chromatic number. $\endgroup$ – David Roberson Mar 12 '18 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.