Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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
4  
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
3  
"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
2  
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
2  
@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

4 Answers 4

up vote 11 down vote accepted

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.

share|improve this answer
    
I like mine better; you don't actually have to calculate anything. :) Seriously, +1. –  Harrison Brown Dec 18 '09 at 19:04
1  
I added the no-calculation justification, which I had temporarily forgotten :) –  Qiaochu Yuan Dec 18 '09 at 19:25
2  
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
1  
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
1  
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

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.

share|improve this answer
    
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.

share|improve this answer
    
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

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.

share|improve this answer
    
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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.