0

In other words, what is the largest clique that can be drawn without any crossing edges in $\mathbb{R}^n$?

It's trivial in $\mathbb{R}$: 2.

In $\mathbb{R}^2$: 4, as we know that $K_5$ is non-planar

But what if we take it further to $\mathbb{R}^3$ and beyond? I can imagine at least a planar clique of size 6 in $\mathbb{R}^3$ by adding a vertex "above" and "below" the planar form of $K_4$ and adding edges appropriately. But is that the limit? Is there a general law for $\mathbb{R}^n$?

Anthony Abello
  • 3
  • 1
    Any graph is "planar in $\mathbb{R}^3$". Pick $n$ random points on $S^2$ and connect all of them through edges: the probability that these segments intersect in the interior of $S^2$ is zero, so $K_n$ is planar in $\mathbb{R}^3$. – Jack D'Aurizio Dec 18 '17 at 00:39
  • What do you think the word "planar" means? – bof Dec 18 '17 at 05:07

1 Answers1

2

You can draw a clique of any size in $\mathbb R^3$. To construct the points inductively, all you have to do is place the $n^{\text{th}}$ point off any of the $\binom{n-1}{3}$ planes spanned by any three of the previous points; if you do, then no crossings occur.

Misha Lavrov
  • 142,276