Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graphs, embeddings and dimensions

  1. Jul 27, 2010 #1


    User Avatar
    Science Advisor


    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?
  2. jcsd
  3. Jul 29, 2010 #2


    User Avatar
    Science Advisor

    ... push ...
  4. Jul 31, 2010 #3
    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)
  5. Aug 1, 2010 #4


    User Avatar
    Science Advisor

    I am not sure if I understand.

    So you say that in principle it may require n-space???
  6. Aug 1, 2010 #5
    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.
  7. Aug 1, 2010 #6


    User Avatar
    Science Advisor

    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.
  8. Aug 1, 2010 #7
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook