Graphs, embeddings and dimensions

[tom.stoer]

Hello,

Let's start with a cellular decomposition of 3-space, a "foam". A foam can be represented by its dual graph: cells and faces are dual to vertices and links.

What about the opposite?

It is clear that one can construct graphs for which no dual foam exists: take a large foam and connect two far-distant, inner vertices with a new link; as this link crosses many cells of the original foam the graph has no dual cellular decomposition in 3-space.

Is there a theorem which says something about higher dimensions?

One can emdedd any graph in 3-space, but for the dual foam this does no longer work. Is there a result showing that the dual foam would live in higher dimensional space? Is anything known about the required number of dimensions for the dual foam? Does it always exist?

 

[tom.stoer]

... push ...

 

[adriank]

It is clear that one can construct graphs for which no dual foam exists: take a large foam and connect two far-distant, inner vertices with a new link; as this link crosses many cells of the original foam the graph has no dual cellular decomposition in 3-space.

This is not clear to me.

You should be able to show that for each n, there is a foam in n-space whose dual is the complete graph on n+1 vertices. Once you have that, can you say something about deleting edges from the dual graph? (I don't know the answer)

 

[tom.stoer]

I am not sure if I understand.

So you say that in principle it may require n-space?

 

[adriank]

It may, or it may not. I don't know.

I'm assuming you are considering convex cells that may be unbounded.

I can't think of a way you could produce a foam in 3-space whose dual is the complete graph on 5 vertices. Can you prove or disprove this?

My idea with the complete graph was: For general n, consider the n+1 vertices of a regular n-simplex (in n-space). Then the corresponding Voronoi cells partition n-space in such a way that the dual graph is the complete graph on n+1 vertices.

 

[tom.stoer]

OK, I understand where the confusion comes from. My description starting with foams in 3-space is inspired by qantum gravity which deals with 3-space. Now the problem is that foams in 3-space have duals (graphs) which allow for more complex graphs which no longer have duals in 3-space, but n-space.

So I am interested in finding out more regarding this n.

You can forget about the foam in 3-space for a moment.

My problem is that I am not able to show anything regarding the dimension given a general graph with N vertices. If I undersand you correctly you say that for N = n+1 the graph has a dual foam in n-space and that there is no lower n' < n for which a foam does exist.

If this is true, this answers my question completely.

 

[adriank]

I'm sure you can find graphs with arbitrarily many vertices that can be embedded in 3-space (or even 2 or 1). The point of the complete graph was that, by deleting edges, I *think* that you can embed any graph with n+1 vertices in n-space, but I don't know. And it may very well be possible to do it in lower dimensions.

You should see if there's some stuff that's been done in the literature.