Many fractals can be generated using and infinite sequence of graphs. For example, Sierpinski's Gasket could be generated by the following sequence of graphs.
Many definitions of fractal dimensions (box-counting, correlation, capacity etc.) give the fractal dimension of Sierpinski's Gasket as $\log_23 \approx 1.58$. Is there a nice way to recover this number from the graph construction. More generally, given a sequence of self-similar graphs, can one assign a fractional dimension that makes sense with the typical definition from continuous fractals ?
I was trying this by myself. However, all the proofs I has seen for the fractal dimension of Sierpinski's Gasket involved a definition of length. This length was defined to be of dimension $1$. How would this be extended to graphs?
My idea was simply to use the diameter of a graph as a base one-dimensional measure. This works wonderfully with the Sierpinski Gasket. However, consider the following sequence of graphs. Let $G_1$ just be $4$ points arranged in a cycle. Now to construct $G_n$ we have the following algorithm:
- Arrange $4$ $G_{n – 1}$ graphs in a square.
- Call two of the $G_{n – 1}$ graphs adjacent if they are not diagonally opposite.
- Given a point $A$ connect it to the corresponding point in both of the adjacent $G_{n – 1}$ graphs.
In this case, using diameter does not work because the diameter of $G_n$ is only $2$ more than the diameter of $G_{n – 1}$. On the other hand, the number of vertices has quadrupled. This is different from the Sierpinski Gasket in that the number of points roughly triples between consecutive Sierpinski graphs. However, the diameter doubles. How should a one-dimensional measure be defined? Or is this the wrong approach entirely?
Is there an intuitive meaning to the dimension of a self-similar graph?
Best Answer
One way to think of dimension on graphs is to consider Ball growth. In fact there is some literature that refers to a graph $G = (V,E)$ as being "fractal" if there is a constant $C$ and an exponent $q$ such that for any vertex $x$, $$ V_t(x):= \#\{ \text{vertices no more than } t \text{ steps away from }x \} \leq C t^q.$$ If one had the corresponding lower bound, then this would correspond to the graph being Ahlfors $q$-regular with the graph distance and the measure which counts verteces.
Checking the examples, the Sierpinski latices $V_{2^n} (x) \leq C 3^n$. This is essentially because, as you point out, the number of vertices in $S_n \approx 3^n$ while the diameter is $2^n$.
On the other hand, the counterexample graphs you mention are not fractal because the diameter grows too slowly.