# What is the max number of points in R^3, interconnected by generic curves?

The largest complete graph that embeds in 2 dimensions is $K_4$, while the largest complete graph that embeds in 3 dimensions is $K_{\infty}$, right? However, I don't know any constructive proof of it.

Informal Explanation: What is the max number of points in $\mathbb{R}^3$, interconnected by lines of any curvature, such that no line intersects any other line? Each point is connected with all other points. For $\mathbb{R}^2$ it is only 4 points (smth. like Mercedes symbol) - why 4 and not 3 or 5? How many points are possible to connect in such way in $\mathbb{R}^3$? (I suggest, infinite number, but it is interesting to look at a proof). What are some special properties of the Euclidean $\mathbb{R}^3$ such that the number of interconnected points jumps from 4 in $\mathbb{R}^2$ to infinity in $\mathbb{R}^3$?

PS: I don't understand why my question has got already 4 downvotes? No comments, no critics, why? English is not my native language, that's why?

-
psihodelia asks why there is there is the following radical change from 2 dimensions to 3: The largest complete graph that embeds in 2 dimensions is $K_4$, while the largest complete graph that embeds in 3 dimensions is $K_\infty$. – Greg Kuperberg Dec 18 '09 at 17:50
I don't want to come across as harsh, so I don't want to say the problem is trivial (although it's certainly well-known and not difficult.) But when other users repeatedly offer good answers to which you either reply that they aren't good or ask another very easy question as a follow-up, people are going to conclude that either you aren't phrasing the question you want to ask correctly or else you don't understand the topic at even a basic level. – Harrison Brown Dec 18 '09 at 19:10
"why there is no any constructive proof being given?" There are currently three constructive proofs on this page, and even the non-constructive proofs can be fairly easily modified to give "semi-constructive" proofs. The question on its own isn't great, but it's not terrible; but if you don't understand the answers being given, perhaps you shouldn't have asked it. – Harrison Brown Dec 18 '09 at 19:13
The Menger sponge example is constructive, but a construction wasn't written down explicitly. FYI, all you need to do is take a generic piecewise-linear map from a graph into $\mathbb R^3$ and with probability one it'll be an embedding. This can be turned into a proper algorithm without much effort. – Ryan Budney Dec 18 '09 at 19:13
@psihodelia: I tend to agree with Scott and Harrison. Your question is not very hard, and you shouldn't expect unlimited hand-holding. Four people gave you quality answers. You should spend time on their words, because they spent time on your words. – Greg Kuperberg Dec 19 '09 at 18:56

Take straight lines connecting the points $(t, t^2, t^3), t \in \mathbb{N}$. As far as I can tell you can also boost this to $t \in \mathbb{R}$. The point here is that two distinct lines between points on this curve intersect if and only if the four points involved lie on a plane (or there are only three points involved, but in that case you already know what the intersection is), but any plane $ax + by + cz = d$ intersects the curve in at most three points because $at + bt^2 + ct^3 = d$ has at most three roots.

-
I like mine better; you don't actually have to calculate anything. :) Seriously, +1. – Harrison Brown Dec 18 '09 at 19:04
I added the no-calculation justification, which I had temporarily forgotten :) – Qiaochu Yuan Dec 18 '09 at 19:25
This is the "moment curve" and it's important not just as a standalone set of points in general position as you describe here but also as a way to perturb arbitrary point sets into general position. See e.g. "Simulation of Simplicity", Edelsbrunner and Mücke, ACM Trans. Graphics 1990. – David Eppstein Dec 18 '09 at 19:27
That can also be turned into a legitimate construction, by the way, which requires essentially no work: start with three non-collinear points and, at each step, add points that are not on any of the planes determined by the finite set you have so far. – Qiaochu Yuan Dec 18 '09 at 19:53
The Edelsbrunner–Mücke construction is: take an arbitrary finite set of points p_i. Then for sufficiently small ε the points p_i+(εi,(εi)^2,(εi)^3)) will be in general position. "Sufficiently small" can be replaced by "infinitesimal" in algorithmic applications. – David Eppstein Dec 18 '09 at 20:00

I guess the main reason is that $\mathbb{R}^3$ minus any finite set of curves is still path-connected, so you can build any graph up inductively as a subset of $\mathbb{R}^3$.

Here is a slightly different answer: any graph is naturally a metric space. The Menger sponge $M$ (3d version of the Sierpinski carpet) has the interesting property that any 1-dimensional metric space is homeomorphic to some subset of $M$. So in particular, any graph is homeomorphic to a subset of $M$, which is itself a subset of $\mathbb{R}^3$. So in fact, you don't even need all of $\mathbb{R}^3$ to embed your complete graphs, just 2.7 dimensions worth!

This almost certainly can be improved. Are there "thinner" nice bounded subsets of $\mathbb{R}^3$ which also contain any $K_n$? I guess you could make a $K_\infty$ with vertices at the integers along the $x$ axis, connect all the vertices up, then smash the whole thing down to make it bounded, but the dimension of the resulting thing is not obvious to me near the vertices.

-
Thank you. Do you know how to prove that only 4 interconnected points are possible in R^2 and how to prove that the number of such points in really infinite in R^3? – psihodelia Dec 18 '09 at 18:16
@psihodelia: The usual proof that you can't have five points connected by non-intersecting lines uses Euler's formula for planar graphs: V - E + F = 2 (or 1 if you don't count the infinite face.) – Harrison Brown Dec 18 '09 at 18:25
@Harrison: How to prove that the number of such points is infinite in R^3? – psihodelia Dec 18 '09 at 18:43
You can turn the last paragraph of my answer into a proof. Start by connecting all of the integer points on the $x$ axis to the origin with arcs in the $xy$ plane. Then rotate and translate the graph you get to connect everything up. – Matt Noonan Dec 18 '09 at 18:55
@Matt: What if I try to connect all real numbers? Will it still work? – psihodelia Dec 18 '09 at 18:58

Matt's answer is correct, but at an even simpler level: If you take two generic line segments in a compact subset of R^2, they'll intersect with positive probability. If you take two generic line segments in R^3, they'll intersect with probability 0. This isn't a proof by any means, but it's the simplest conceptual reason I know of. If instead of edges we wanted surfaces, we'd have to go up to dimension 5.

::sigh:: Okay, here's a constructive example of an infinite set of points such that no straight line segments between any two of them intersect. Take any two real numbers, say 2 and $\pi$, that are algebraically independent. Then I claim that the set of points $(n, 2^n, \pi^n)$ is such a set.

Why? Suppose the line segment between the points with $x = a$ and $x = b$ intersected the line segment between $x = c$ and $x = d$, parameterizing the line segments so the equations:

$(a, 2^a, \pi^a) + \lambda (b-a, 2^b - 2^a, \pi^b - \pi^a)$

$(c, 2^c, \pi^c) + \gamma (d-c, 2^d - 2^c, \pi^d - \pi^c)$

give us the same point for some choice of the variables.

Looking at the first two components tells us that $\lambda, \gamma$ are both rational. But then the third component gives us a polynomial with rational coefficients that has a root equal to $\pi$, which is impossible since $\pi$ is transcendental. So none of these line segments can intersect.

-
Thank you very much! I understand and appreciate your answer. However, I give you my vote, but Yuan's proof is explained clearer and simpler for a layman like me - his answer I mark as accepted. – psihodelia Dec 19 '09 at 22:57

Generic curves in $\mathbb{R}^2$ intersect. Generic curves in $\mathbb{R}^3$ don't. This is why we have trouble embedding graphs in two dimensions but not in three; in three dimensions there's always enough room for curves to go around each other.

-
I got scooped! :) – Harrison Brown Dec 18 '09 at 18:23
This is not a proof at all. How to prove that the number of such points is infinite in R^3? – psihodelia Dec 18 '09 at 18:45
It's basically a cardinality issue. It boils down to fact that the unit sphere in $\mathbb R^3$ is not a countable union of arcs. – Ryan Budney Dec 18 '09 at 19:17