Graphs Embedded on Fractals - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T01:41:58Z http://mathoverflow.net/feeds/question/56245 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56245/graphs-embedded-on-fractals Graphs Embedded on Fractals Sergeib 2011-02-22T05:10:19Z 2011-02-23T11:50:51Z <p>It is fairly well know when graphs can be embedded on various surfaces. Also, it is not hard to see that any graph can be embedded in 3-dimensional space. Has anyone ever studied the embeddability of graphs on various fractals? If so, are there any interesting results?</p> <p>For example, I made some quick deductions about graphs on Sierpinski's Gasket. No graph that has vertices of degree greater than 4 can be embedded on Sierpinski's Gasket. Also, I conjecture that one can not embed $K_4$ into Sierpinski's Gasket either. </p> <p>Also, one might ask questions like, "Is it true that one can embed any graph on any space with Hausdorff dimension that is greater than or equal to 3?"</p> <p>These are just some curiosities that came to me and a friend of mine earlier today, and I am curious if the Math Overflow community knows anything about such things.</p> http://mathoverflow.net/questions/56245/graphs-embedded-on-fractals/56246#56246 Answer by ARupinski for Graphs Embedded on Fractals ARupinski 2011-02-22T05:55:31Z 2011-02-22T05:55:31Z <p>Offhand I don't think Hausdorff dimension greater than or equal to 3 is strong enough for embedding any graph. If one considers the analogue of the Sierpinski gasket in 7 dimensions, this fractal has Hausdorff dimension 3, but it doesn't seem that any graph with a node of valence greater than 14 could be embeddable by essentially the same reasoning as you used for embedding graphs in the ordinary Sierpinski gasket.</p> <p>Upon further thought, one <i>can</i> embed $K_4$ in the Sierpinski gasket since an embedding need not necessarily take straight lines to straight lines. In fact, one can embed it such that only one of the edges is not straight, so by extending this idea, it may still be possible to embed any (?) planar graph of valence &lt; 5 in the Sierpinski gasket.</p> <p>To see the embedding of $K_4$ I have in mind, let the three vertices of the triangle be (1,0,0), (0,1,0), and (0,0,1). The four vertices of the $K_4$ be $A = (\frac{1}{2},\frac{1}{2},0)$, $B = (\frac{1}{4},\frac{3}{4},0)$, $C = (\frac{1}{4},\frac{1}{2},\frac{1}{4})$, and $D = (0,\frac{3}{4},\frac{1}{4})$. The arcs $AB$, $AC$, $BC$, $BD$, and $CD$ are the straight line subsets of the gasket, while the arc $AD$ goes from $A$ to $(\frac{1}{2},0,\frac{1}{2})$ to $(0,\frac{1}{2},\frac{1}{2})$ to $D$.</p> http://mathoverflow.net/questions/56245/graphs-embedded-on-fractals/56264#56264 Answer by Benoît Kloeckner for Graphs Embedded on Fractals Benoît Kloeckner 2011-02-22T10:27:24Z 2011-02-22T10:27:24Z <p>You cannot expect Hausdorff dimension alone to be the right notion for graph embeddability, since it is too metric and not topological enough.</p> <p>To be more precise, consider snowflaking: for any metric space $(X,d)$ and any $\alpha\in(0,1)$, the function $d^\alpha$ defines a distance. Moreover, the Hausdorff dimension of $(X,d^\alpha)$ is $\alpha^{-1}$ times the Hausdorff dimension of $(X,d)$. So for example, you can metrize the Cantor set or the line so as to give them arbitrarily high Hausdorff dimension.</p> <p>You could restrict to length space to rule out Cantor sets and snowflakes spaces (they do not have any non-constant rectifiable curve), but I tend to think that any result in this direction will "factor through topology", by which I mean that one proves that the Hausdorff dimension bound on the length space imposes some topological property that in turns provides embeddability.</p> http://mathoverflow.net/questions/56245/graphs-embedded-on-fractals/56284#56284 Answer by BSteinhurst for Graphs Embedded on Fractals BSteinhurst 2011-02-22T14:16:44Z 2011-02-23T11:50:51Z <p>The Sierpinski gasket is not a good example for this because of the bound you saw on the degree of the graph. I'd venture to say that this is because the gasket falls into a class of fractals called post-critically finite. It is the fact that in pcf fractals when level n cells intersect there are a uniformly bounded number of them. You might be interested in looking at finitely ramified but not post-critically finite fractals. See <a href="http://arxiv.org/abs/0903.3681" rel="nofollow">this</a> for some nice pictures of the Diamond fractal. Since the number of level n-cells intersecting is unbounded in n you can embed graphs without a bound on degree.</p>