What classes of complete graphs can be linklessly embedded in k-dimensional euclidean space?

by jjzun   Last Updated August 13, 2019 20:20 PM - source

I have been thinking a lot about the clique problem and the reason for its complexity recently, and have been studying the worst-case graphs, complete graphs.

I am particularly interested in what "forms" the "same" graph can take on, if you alter its shape in your imagination, without "changing" it in any way and the smallest dimension you can reach with it. (A very joyful activity!)

While reading the wikipedia article today, I stumbled upon the following facts:

1.) Kuratowski showed that $K_4$ is not linklessly embeddable in 2-dimensional euclidean space.

2.) Conway and Gordon showed that $K_6$ is not linklessly embeddable in 3-dimensional space.

It seems to me, that if you go 1 dimension higher all these graphs can be linklessly embedded.

My question: Is the following conjecture true?

$\forall n \in N, n>=2 : K_{2n}$ is not linklessly embeddable in n-dimensional euclidean space. It is however, linklessly embeddable in $(n+1)$-dimensional euclidean space.

It seems very likely to me, that Kuratowski's theorem and the result of Conway and Gordon are "just" particular cases of something far bigger, which is hard to grasp.

I would like to prove it myself, but unfortunately I lack the ability and the knowledge.

The technique that Conway and Gordon apply in their paper however, as far as I could understand, seems like there may be a chance to generalize their approach.



Related Questions




Planar graph contains bipartite subgraph

Updated September 25, 2019 19:20 PM

Graph Theory: How to proof the Fan's Lemma?

Updated October 14, 2018 13:20 PM

How to find a minimal planar covering of a graph

Updated January 24, 2018 05:20 AM