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

I Constructing dimensions out of a graph structure?

  1. Oct 3, 2016 #1
    I have a question to anyone experienced with graphs and topology. The question is relevant for this topic: https://www.physicsforums.com/threads/a-graph-based-model-of-physics-without-dimensions.887694/ [Broken]

    Is it possible to construct an arbitrarily large graph (a set of vertices, a set of edges), such that the following is true:

    There exists a mapping f(v) of vertices to (x,y,z) coordinates such that
    For any pair of vertices m,n:
    the euclidean distance of f(m) and f(n) is approximately equal to the length of the shortest path between m and n (inaccuracies are fine so long as the distance is small, but the approximation should be good at larger distances).

    In other words, is it possible to construct a graph that effectively simulates a 3 dimensional space?
    Last edited by a moderator: May 8, 2017
  2. jcsd
  3. Oct 8, 2016 #2
    Thanks for the thread! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post? The more details the better.
  4. Oct 19, 2016 #3
    FlorianDietz, this is an interesting question.

    But just asking for a mapping *from* the vertices of some graph G *to* 3-dimensional Euclidean space R3 is not at all the same as asking whether it's possible to construct a graph "that effectively simulates a 3 dimensional space".

    So I'm not sure if you are phrasing the question in such a way as to ask what you are really interested in.

    For example, I bet you can find such a mapping if a) G has 1 vertex and 0 edges, or b) G has 2 vertices and 1 edge, or c) if G has 3 vertices and 3 edges arranged in a triangle, or d) if G has n+1 vertices and n edges arranged in a straight line . . . but no one would think these come close to "simulating" even a finite portion of 3-dimensional space.

    Maybe if you thought about this question a little more you might rephrase the question so that it comes closer to what you are aiming at? One possibility is that you would like to find an *infinite* graph G with a mapping of its set V of vertices into R3:

    f: V → R3

    with certain properties that you might like to have? Or just let the vertices and edges of G be a subset of R3.

    For instance, you could imagine the graph whose vertices correspond to all the points of R3 having integer coordinates (K, L, M), and whose edges are all the unit intervals connecting a vertex to its 6 nearest neighbors (right, left, front, back, up down).

    In that case, in what precise sense would that graph "simulate" R3 ?
  5. Oct 24, 2016 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    A 3-D grid can be regarded as a graph. It seems to me that a fine enough grid satisfies your requirement.
  6. Nov 4, 2016 #5
    That gives a taxicab metric instead of the Euclidean metric the OP wants.
  7. Nov 4, 2016 #6

    Stephen Tashi

    User Avatar
    Science Advisor

    Can we connect diagonally opposite vertices with an edge ?
  8. Jan 7, 2017 #7
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted