11
$\begingroup$

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.

enter image description here

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:

  1. Arrange $4$ $G_{n - 1}$ graphs in a square.
  2. Call two of the $G_{n - 1}$ graphs adjacent if they are not diagonally opposite.
  3. 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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Graphs are special types of operators. Maybe by this point of view, we can see the iteration of operators and by some good using of Fourier transformation, we can find a meaning for self-similarity. Also, I think if we can get the fraction of $\frac{|Z(Aut(G))|}{|Aut(G)|}$, we have a good measure for self-similarity. Maybe, the concept of fractional graph theory be helpful in some scene. $\endgroup$
    – Shahrooz
    Commented Aug 7, 2015 at 22:18
  • $\begingroup$ What does Z denote? $\endgroup$
    – Halbort
    Commented Aug 7, 2015 at 22:55
  • 1
    $\begingroup$ For the group $G$, the symbol $Z(G)$ denotes the center of $G$. Since $Aut(\Gamma)$ shows the symmetric properties of graph $\Gamma$, I think the dimension of iterated graph must strongly depend to its auotomorphism group or some good fraction deduced from it. $\endgroup$
    – Shahrooz
    Commented Aug 8, 2015 at 7:11
  • $\begingroup$ Okay, that makes sense now. Thank you! $\endgroup$
    – Halbort
    Commented Aug 8, 2015 at 21:09

3 Answers 3

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What exactly is Ball growth? I could not find it on the internet. $\endgroup$
    – Halbort
    Commented Aug 8, 2015 at 21:09
  • 1
    $\begingroup$ All that was meant by ball growth was the rate that the volume of a metric ball around $x$, which was denoted $V_t(x)$, grows. In the post, a fractal graph has volume growth bounded by a polynomial. $\endgroup$
    – D. Kelleher
    Commented Aug 9, 2015 at 12:51
6
$\begingroup$

This should be more like a comment but I haven't got enough reputation :)

Have you tried

B. Krön. Growth of self-similar graphs. Journal of Graph Theory, 45 no. 3, 224-239 (2004). ? or

B. Krön. Green functions on self-similar graphs and bounds for the spectrum of the Laplacian. Ann. Inst. Fourier (Grenoble) 52 no. 6, 1875-1900 (2002).

B. Krön, E. Teufl. Asymptotics of the transition probabilities of the simple random walk on self-similar graphs. Trans. Amer. Math. Soc., 356 393-414 (2004).

Especially the first paper should have some answers for you.

Improve this answer
$\endgroup$
2
$\begingroup$

You ask for intuition, so I'll assume I'll get some wiggle room in mathematical content.

The typical box counting dimension measures the exponent in the relation

$$M(s)\sim s^d$$

Where $M(s)$ is some notion of 'mass' and $s$ is some notion of scale.

In this case, you'd just use $M(s)=E(n)$ and $n$. Where $E(n)$ is the number of edges in iteration n. You'd then find an exponent that fits the relationship between the two variables using.

$$d \sim {{\ln(E(n))} \over {\ln(n)}}$$

Things get more interesting when the edges are given varying weights. In that case, an analogy involving multi-fractals might be drawn.

Here's a reference to another MO discussion on the subject.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What do you mean: "Things get more interesting when the edges" $\endgroup$
    – Halbort
    Commented Aug 7, 2015 at 20:55
  • $\begingroup$ @Halbort terribly sorry :( I meant "things get more interesting when the edges are given varying weights" $\endgroup$
    – Zachary W. Robertson
    Commented Aug 7, 2015 at 21:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .