0
$\begingroup$

Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by

  1. $V(\text{HN}_n) = \mathbb{R}^n$;
  2. $E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ and } |v_1-v_2| = 1\}$.

Is it true that the clique number $\omega(\text{HN}_n)$ equals $n+1$ for all $n\in \mathbb{N}$?

Improve this question
$\endgroup$
2
  • $\begingroup$ A nice, pure question. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 25, 2015 at 8:20
  • $\begingroup$ Could you provide known clique upper bounds, and chromatic lower+upper bounds? At least $\ \omega(HN_1)=2\ $ and $\ \omega(HN_2)=3,\ $ right? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 25, 2015 at 8:29

1 Answer 1

Reset to default
3
$\begingroup$

Yes. The moral reason is that cliques are 1-skeletons of regular simplices. If you want convincing quickly then it's straightforward to show inductively that there is exactly one clique in $\mathbb R^n$ of order $n+1$ up to the obvious symmetries, because when you go up a dimension you have exactly two choices for where to place the extra point, and can't take both of them because they're not the correct distance apart.

As a crude upper bound we have $\chi(\mathbb R^n) \leq (\sqrt n + 1)^n$. Tile $\mathbb R^n$ by cubes of side length $1/\sqrt n$, give a $(\sqrt n + 1) \times \cdots \times (\sqrt n + 1)$ block of cubes $(\sqrt n + 1)^n$ different colours and extend periodically.

Improve this answer
$\endgroup$

You must log in to answer this question.

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