# Graphs, embeddings and dimensions

1. Jul 27, 2010

### 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.

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?

2. Jul 29, 2010

### tom.stoer

... push ...

3. Jul 31, 2010

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)

4. Aug 1, 2010

### tom.stoer

I am not sure if I understand.

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

5. Aug 1, 2010

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.

6. Aug 1, 2010

### 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 wich a foam does exist.

If this is true, this answers my question completely.

7. Aug 1, 2010

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.