9
$\begingroup$

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?

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.

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?"

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ For questions of homeomorphic embedding, the topological dimension should be used, not the Hausdorff dimension, since the Hausdorff dimension is not a homeomorphic invariant. $\endgroup$
    – Gerald Edgar
    Feb 23, 2011 at 14:35

3 Answers 3

Reset to default
5
$\begingroup$

You cannot expect Hausdorff dimension alone to be the right notion for graph embeddability, since it is too metric and not topological enough.

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.

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There's also the issue of projections onto dust-like sets. For instance, the Cartesian product of some totally-disconnected dust-set and the unit-square will only ever admit planar-graph embeddings. The question is perhaps better-posed in terms of connected self-affine sets with some non-snowflake-like conditions imposed (I'm not familiar with the definition of a "snowflake space"). $\endgroup$
    – Nick Loughlin
    Feb 22, 2011 at 11:27
4
$\begingroup$

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.

Upon further thought, one can 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 < 5 in the Sierpinski gasket.

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ No non-planar graph should embed, since the gasket may be realised as sitting on the plane $\endgroup$
    – Nick Loughlin
    Feb 22, 2011 at 11:38
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.