0
$\begingroup$

If $G =(V,E)$ is a simple, undirected graph (finite or infinite), and $\kappa \neq \emptyset$ is a cardinal, we say that the complete graph $K_\kappa$ is a minor of $G$ if there is a collection ${\frak S}$ of connected and pairwise disjoint subsets of $G$ such that

  1. $|{\frak S}| = \kappa$, and
  2. whenever $S\neq T\in {\frak S}$, then there is $e\in E$ such that $(S\cap e) \neq \emptyset \neq (T\cap e)$.

The Hadwiger-Nelson graph has $\mathbb{R}^2$ as its ground set, and two elements $x,y\in\mathbb{R}^2$ form an edge if and only if their Euclidean distance equals $1$.

Question. Is the set of cardinals $\kappa \neq \emptyset$ such that $K_\kappa$ is a minor of the Hadwiger-Nelson graph finite? If yes, what is its greatest member?

Note. Since the Hadwiger conjecture is correct for $k\leq 6$, the set asked for in the question is a super-set of $\{1,2,3,4,5\}$, because it is known that the chromatic number of the Hadwiger-Nelson graph is a member of $\{5,6,7\}$.

$\endgroup$
1
  • 1
    $\begingroup$ Since the Hadwiger conjecture is known for $t \leq 6$, can't you state your note unconditionally? $\endgroup$ Commented Aug 28, 2023 at 0:32

1 Answer 1

3
$\begingroup$

No, the set of such cardinals is infinite.

Take $\kappa$ points on the interval $(0, 1) \times \{0\}$. Every two points $(u, 0)$ and $(v, 0)$ have a common neighbour $$\left(\frac{u+v}{2}, \sqrt{1 - \frac{(u-v)^2}{4}}\right)$$ which is not adjacent to any other vertex on the interval. Thus the Hadwiger-Nelson graph has a $K_\kappa$ minor.

Note that we can pick $\kappa$ to be any natural number (as well as $\aleph_0$ or $2^\aleph_0$), thus there are infinitely many cardinals $\kappa$ such that $K_\kappa$ is a minor of the Hadwiger-Nelson graph.

$\endgroup$

You must log in to answer this question.

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