Open Access

Research articles

Fractal dimensions for iterated graph systems

Department of Mathematics, Huxley Building, Imperial College London, London SW7 2AZ, UK

z5222549@zmail.unsw.edu.au; ziyu.li21@imperial.ac.uk

Contribution: Conceptualization, Data curation, Formal analysis, Funding acquisition, Investigation, Methodology, Project administration, Resources, Software, Validation, Visualization, Writing – original draft, Writing – review and editing

Google Scholar

Find this author on PubMed

Search for more papers by this author

Ziyu Neroli

Published:16 October 2024https://doi.org/10.1098/rspa.2024.0406

Abstract

Building upon Li & Britz (Li NZ, Britz T. 2024 On the scale-freeness of random colored substitution networks. Proc. Amer. Math. Soc. 152, 1377–1389 (doi: 10.1090/proc/16604)), this study aims to introduce fractal geometry into graph theory and to establish a potential theoretical foundation for complex networks. Specifically, we employ the method of substitution to create and explore fractal-like graphs, termed iterated graph systems (IGS) for the first time. While the concept of substitution is commonplace in fractal geometry and dynamical systems, its analysis in the context of graph theory remains a nascent field. By delving into the properties of these systems, including distance and diameter, we derive two primary outcomes. Firstly, within the deterministic IGS, we establish that the Minkowski dimension and Hausdorff dimension align through explicit formulae. Secondly, in the case of random IGS, we demonstrate that almost every Gromov–Hausdorff scaling limit exhibits identical Minkowski and Hausdorff dimensions analytically by their Lyapunov exponents. The exploration of IGS holds the potential to unveil novel directions. These findings not only, mathematically, contribute to our understanding of the interplay between fractals and graphs, but also, physically, suggest promising avenues for applications for complex networks.

1. Introduction and main results

(a) Introduction

Graph theory originated in the eighteenth century and saw rapid development throughout the twentieth century, while fractal geometry was proposed and explored during the twentieth century as well. Both fields have undergone rigorous mathematical development to this day. The integration of these two fields is generally associated with the study of complex networks [1]: this is primarily due to the work of Watts on small-world networks [2], Barabási’s discovery on scale-free networks [3] and Song’s exploration of fractal networks [4]. These remarkable works demonstrate certain distinctive patterns of real-world complex networks.

However, the underlying mathematical principles of complex networks still remain unclear. Few attempts have been made to develop the theory: most relevant studies are based on real-world data and finite networks, rather than mathematical objects. Such a gap is to be filled, and it is of great interest to explore the behaviour of infinite graph fractals.

To establish the fractals for graphs, we utilize the idea of substitution and iterated function systems (IFS), where these two concepts are more than common in dynamical systems and fractal geometry. It is also always natural to relate substitutions to dynamics because a natural source of substitutions is tiling and substitutive dynamical systems [5–8]. Since Hutchinson [9] set up the IFS strictly in a general framework, large numbers of notable works contribute to the studies of self-similar sets, for instance graph-directed systems [10,11], IFS with overlaps [12–14] and random IFS [15,16]; see also [17–21].

Building on these foundations, we rigorously define the iterated graph system (IGS) by iteratively substituting the (coloured) arcs in a graph (randomly) with certain fixed graphs. However, the concept of the IGS is not entirely new; it evolves from the predecessor known as substitution networks, which were first introduced by Xi et al. [22], where fractality and scale-freeness are obtained. Li et al. [23,24] brought coloured graphs into this model and the average distance was studied by Ye et al. [25,26] in which the existence of average distance is exhibited under some circumstances. IGS can also be viewed both as the graph version of graph-directed fractals [10,27] and also as a generalization of them because the substitution process inherent to IGS includes a graph-directed methodology. We will discuss this issue in another work.

Therefore, from a mathematical perspective, studying IGS is at least intriguing: we anticipate that fractals on graphs will exhibit unique behaviours not seen in Euclidean spaces. This is indeed the case, as evidenced by the specially defined degree dimension [1] for graph fractals. Physically, IGS provide a solid mathematical foundation for the study of complex networks, especially those with scale-freeness and fractality. The potential applications include considerations of fractal dimensions, degree distributions, average distance, random walks, diffusion process and percolation, among others. See a recent interesting work [28] by Eriksson-Bique et al. For instance, a quick corollary in this paper is that for any network characterized by a specific fractal dimension, it is possible to correspondingly design an iterated graph system that mirrors this dimension.

(b) Main results

The deterministic (or random) IGS roughly refers to the system generating infinite graphs (randomly) iteratively by independent coloured arc substitutions. Find figure 1 as an example. Rigorous definitions will be given in §2b and §4a.

Figure 1. An example of a deterministic iterated graph system.

This paper mainly contains two conclusions, the first of which solves the problem left in Li et al. [24]:

Theorem 1.1. Given any irreducible deterministic IGS and its Gromov–Hausdorff scaling limit $Ξ$ , we have:

\dim_{B} (Ξ) = \dim_{H} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ_{\min} (D)} .

Here, $ρ (*)$ represents the spectral radius, and relevant definitions of $𝐌$ and $D$ will be given in §2a,b, and the proof will be presented in §3 later.

Another result is to construct random IGS and prove that the associated graph limits $Ξ$ satisfy the following property.

Theorem 1.2. Given any irreducible random IGS, for $ℙ$ -almost all $Ξ \in G^{\infty}$ or equivalently:

ℙ (\dim_{B} (Ξ) = \dim_{H} (Ξ) = \frac{L (M)}{\min_{D \in D} L (D)}) = 1 .

Here, $Ξ$ is the Gromov–Hausdorff scaling limit of a stochastic process of graphs ${(Ξ^{n})}_{n \in ℕ}$ , and related definitions of $ℙ$ , $G^{\infty}$ , $L (*)$ , $M$ , $D$ and $D$ will be addressed in §4a, and the proof will be shown in §4e.

The concept of IGS is straight and simple. However, the difficulty and novelty of this paper lie in the solution of a combinatorial matrix problem (§3a), estimation of diameter and distal (§3b) and analysis of random substitution (§4).

2. Deterministic iterated graph systems

(a) Minkowski dimension for graphs

In this subsection, we will define the limit of a graph sequence and the Minkowski dimension, also known as the box-counting dimension, for graphs to facilitate the study of fractal-like graphs. With these foundational concepts established, we can proceed to analyse IGS.

Definition 2.1. Let $G$ be a weakly connected graph containing no self-loops or multiple edges but with directions and uniform weights. To be specific, we say $G$ is a triple $G = (V (G), E (G), μ_{G} (e))$ . $V (G)$ is the set of vertices, and $E (G) \subset V (G) \times V (G)$ is the set of edges if they are undirected, or arcs if directed. $μ : E (G) \to [0,1]$ is the weight or measure of arcs. In this paper, the weight of arcs in a graph is always uniform. Unless otherwise specified, the weight of an unscaled graph is always $1$ , that is $G = (V (G), E (G), 1)$ given $μ_{G} (e) = 1$ .

In this paper, the distance between vertices $a$ and $b$ on a directed graph $G$ is also defined as

\begin{aligned} d_{G} (a, b) & := d_{\underline{G}} (a, b) \end{aligned},

where $G$ is the underlying undirected graph of $G$ . That is, regarding the distance we always omit the direction.

Denote a simple path, omitting the direction of arcs, from vertex $a$ to vertex $b$ in $G$ by $P (a, b)$ and denote the collection of all simple paths between $a$ and $b$ in $G$ paths by $P (a, b)$ . If there is no ambiguity, we may abbreviate $P (a, b)$ as $P$ and $P (a, b)$ as $P$ in our notation.

Define

d_{G} (a, b) = inf {| E (P (a, b)) | : P (a, b) \in P (a, b)} .

Let the diameter of $G$ be

Δ (G) = \sup {d_{G} (a, b) : a, b \in V (G)} .

Definition 2.2. We now define the scaling graph $\hat{G}$ of $G$ by

\hat{G} = (V (G), E (G), μ_{\hat{G}} (e) = \frac{1}{Δ (G)}) .

Define the metric of $\hat{G}$ by

\begin{aligned} d_{\hat{G}} (a, b) = inf {\sum μ_{\hat{G}} (e) : e \in E (P (a, b))} . \end{aligned}

$(V (G), d_{\hat{G}})$ naturally constructs a compact metric space.

Definition 2.3. Let $d_{H} (X, Y)$ be the Hausdorff distance between two subsets $X$ and $Y$ on a metric space [ 29 ]. For any two metrics spaces $(X, d_{X})$ and $(Y, d_{Y})$ , we say $η$ is an admissible metric on $X \cup Y$ if $(X \cup Y, η)$ is metric space and $(X, η) = (X, d_{X})$ and $(Y, η) = (Y, d_{Y})$ . Let $d_{G H}^{η}$ be the Hausdorff metric induced by $η$ on $X \cup Y$ . Define

d_{G H} (X, Y) = inf {d_{H}^{η} (X, Y) : η is an admissible metric on X \cup Y}

be the Gromov–Hausdorff distance in Gromov [30].

Let ${(G^{n})}_{n \in ℕ}$ be a graph sequence of finite graphs. ${(G^{n})}_{n \in ℕ}$ is said to have a Gromov–Hausdorff scaling limit $G^{\infty}$ if there exists a metric space $({\hat{G}}^{\infty}, d_{{\hat{G}}^{\infty}})$ such that:

\lim_{n \to \infty} d_{G H} (({\hat{G}}^{n}, d_{{\hat{G}}^{n}}), ({\hat{G}}^{\infty}, d_{{\hat{G}}^{\infty}})) = 0 .

It is evident that the Gromov–Hausdorff scaling limit $G^{\infty}$ associated with the metric space $({\hat{G}}^{\infty}, d_{{\hat{G}}^{\infty}})$ can contain infinitely many vertices and arcs.

Example 2.1. An example of scaling graphs is given in figure 2, which shows the first four scaling graphs ${\hat{Ξ}}^{0}, {\hat{Ξ}}^{1}, {\hat{Ξ}}^{2}, {\hat{Ξ}}^{3}$ associated to the iterated graph system with ${\hat{Ξ}}^{0}$ as initial graph and with ${\hat{Ξ}}^{1}$ as the substitution rule graph. For simplicity, arcs are here drawn as undirected edges. As $Δ (Ξ^{n}) = 3^{n}$ , the measure of each arc in ${\hat{Ξ}}^{n}$ is scaled to $\frac{1}{3^{n}}$ .

Also refer to figure 3 for an illustration of $Ξ^{6}$ represented as a complex network. This figure is generated using Python NetworkX.

Figure 3. Xi fractal as a complex network.

Definition 2.4. Let $(G, d_{G})$ be a metric space. A family of sets $C_{L} : = {U_{i}}_{i \in I}$ , where $I$ is an indexed set, is said to be a $L$ -covering of $G$ if:

G \subset ⋃_{i \in I} U_{i} a n d d i a m (U_{i}) \leq L .

Define the smallest number of $L$ -covering boxes for $G$ by:

N_{L} (G) := inf {| C_{L} | : C_{L} is a L -covering of G} and hence N_{L} (G) = N_{ℓ = \frac{L}{Δ (G)}} (\hat{G}) .

In this paper, we stipulate that $L$ -covering applies to $G$ , while $ℓ$ -covering applies to $\hat{G}$ .

Definition 2.5. Let $G$ be a Gromov–Hausdorff scaling limit of some graph sequence. The Minkowski dimension is defined as:

\dim_{B} (G) := \dim_{B} (\hat{G}) := lim_{ℓ \to 0} \frac{\log N_{ℓ} (\hat{G})}{- \log ℓ},

if such a limit exists. We say that a graph $G$ has the fractality property if and only if the Minkowski dimension of $G$ exists and is positive. In this case, we call $G$ a graph fractal.

(b) Deterministic iterated graph systems

Definition 2.6. See figure 4 for example.

Figure 4. An example of deterministic IGS.

Let the number of colours be $K \in ℕ$ . The Iterated Graph System $R = (Ξ^{0}, R, S)$ is a triple containing that:

—	$Ξ^{0}$ is a finite directed graph;
—	$R = {R_{i}}_{i = 1}^{K}$ , a family of directed graphs, is called seed graphs. For each seed graph, it must contain two planting vertices ${ν_{i}^{+}, ν_{i}^{-}} \subset V (R_{i})$ .

The colour function is described by $C : E (G) \to [1, K] \cap ℕ$ representing the colour of some arc in $E (G)$ . The substitution operator is defined as:

—

$S : e = (a, b) \mapsto R_{C (e)}$ fixing $a = ν_{C (e)}^{+}, b = ν_{C (e)}^{-} .$

That is, for an arc linking from vertex $a$ to $b$ , we substitute the arc with $R_{C (e)}$ by $a$ and $b$ coinciding with $ν^{+}$ and $ν^{-}$ . In this paper, we require $d_{R_{i}} (ν_{i}^{+}, ν_{i}^{-}) \geq 2$ .

We now define a discrete time $n \in ℕ$ dynamical systems by

Ξ^{n + 1} : = S (Ξ^{n}) : = ⋃_{e \in E (Ξ^{n})} S (e),

satisfying

$S (Ξ^{0}) = Ξ^{0},$

$S^{n + m} (Ξ^{0}) = S^{n} (S^{m} (Ξ^{0}))$ for any $n, m \in N$ .

We call such $R$ an Iterated Graph System and the graph sequence ${(Ξ^{n})}_{n \in ℕ}$ substitution networks. Let $Ξ$ be the Gromov–Hausdorff scaling limit of ${(Ξ^{n})}_{n \in ℕ}$ .

Intuitively, to construct a sequence of growing graphs:

start from the initial graph $Ξ^{0}$ , which is usually just a single arc (for instance a blue arc in figure 4);
we construct $Ξ^{1}$ by replacing all $k$ -coloured arc in $Ξ^{0}$ by $R_{k}$ . To ensure the substitution is unique, we fix $ν_{i}^{+}$ of $R_{i}$ at the starting vertex of the arc and fix $ν_{i}^{-}$ of $R_{i}$ at the ending vertex of the arc;
we then iteratively replace all $k$ -coloured arcs for all $k$ in $Ξ^{1}$ to obtain $Ξ^{2}$ . In this way, denote the graph after $n \in ℕ$ iterations by $Ξ^{n}$ ; accordingly, we have a sequence of graphs ${(Ξ^{n})}_{n \in ℕ}$ called substitution networks. We will prove in §3d that for any iterated graph system $R$ , the Gromov–Hausdorff scaling limit $Ξ$ always exists.

(c) Relevant definitions

Before strictly presenting the main results, several definitions are to be introduced in advance.

Notation 2.1. For any $k$ -dimensional vector $𝐱 = (x_{1}, \dots, x_{n}) \in ℝ_{+}^{k}$ , write ${[𝐱]}_{i} = x_{i}$ for each $i = 1, \dots, k$ . Define $𝝌 (G)$ to be the vector whose $j$ -th entry is the number of $j$ -coloured arcs in graph $G$ . For instance, $𝝌 (Ξ^{1}) = (2,3)$ in figure 1. Let $𝐮 \leq 𝐯$ denote that ${[𝐮]}_{i} \leq {[𝐯]}_{i}$ for all $i = 1, \dots, k$ .

Definition 2.7. Define the $K \times K$ matrix $𝐌 = (m_{i j})$ with entries:

m_{i j} = {[𝝌 (R_{i})]}_{j} .

Definition 2.8. Recall that a path in a graph is simple if it has no repeating vertices. In this paper, we assume that all paths are simple.

Denote a path between vertices $ν^{+}$ and $ν^{-}$ in underlying (undirected) $R_{i}$ by $P_{i} (ν^{+}, ν^{-})$ , and:

P_{i} : = {P_{i} (ν^{+}, ν^{-}) : P_{i} (ν^{+}, ν^{-}) \subset R_{i}} .

Consider the Cartesian product:

P : = \prod_{j = 1}^{K} P_{j} .

Each element (or say choice) $C = (P_{1}, \dots, P_{K}) \in P$ is a vector of length $K$ each of whose entries $P_{i} (ν^{+}, ν^{-})$ is in $P_{i}$ .

Define, for each $i = 1, \dots, K$ ,

V_{i} : = {𝝌 (P_{i} (ν^{+}, ν^{-})) : P_{i} (ν^{+}, ν^{-}) \in P_{i}} .

Let $D$ be the set of all matrices

D_{C} := (\begin{matrix} d_{1} \\ ⋮ \\ d_{K} \end{matrix}) = (\begin{matrix} χ (C_{1}) \\ ⋮ \\ χ (C_{K}) \end{matrix}),

where $𝐝_{i} \in V_{i}$ for each $i = 1, \dots, K$ or, equivalently, $C_{i} \in P_{i}$ . Let $ρ (*)$ be spectral radius, and $ρ_{\min} (D)$ denote the smallest spectral radius of all matrices in $D$ :

ρ_{min} (D) := min {ρ (D) : D \in D} .

Also, define:

D_{\min} : = {𝐃 : ρ (𝐃) = ρ_{\min} (D), 𝐃 \in D} .

If $𝐌$ and all matrices in $D$ are irreducible, we say the iterated graph system is irreducible.

Theorem 2.1. (main theorem). Given any deterministic irreducible IGS $R$ and the associated Gromov–Hausdorff scaling limit $Ξ$ , we have:

\dim_{B} (Ξ) = \dim_{H} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ_{\min} (D)} .

Remark 2.1. For any network with a given algebraic number fractal dimension, we can always directly construct a deterministic iterated graph system that possesses the same box dimension.

In the future, we may define an approximate dimension for finite graphs to address the convergence rate of dimensions.

Example 2.2. Recall the iterated graph system of figure 4. For definition 2.7, we have

M = (\begin{matrix} 2 & 3 \\ 5 & 5 \end{matrix}),

with $ρ (𝐌) \approx 7 . 6533$ .

For definition 2.8, there are $| P_{1} | = 2$ paths in $R_{1}$ , say $P_{1} (ν^{+}, ν^{-})$ and $P_{1}^{'} (ν^{+}, ν^{-})$ , where path $P_{1} (ν^{+}, ν^{-})$ contains two blue edges and one red edge; that is $𝝌 (P_{1} (ν^{+}, ν^{-})) = (2,1)$ , and where path $P_{1}^{'} (ν^{+}, ν^{-})$ contains zero blue and two red edges; that is $𝝌 (P_{1}^{'} (ν^{+}, ν^{-})) = (0,2)$ . In $R_{2}$ , there is also two paths $P_{2} (ν^{+}, ν^{-})$ and $P_{2}^{'} (ν^{+}, ν^{-})$ . $P_{2} (ν^{+}, ν^{-})$ contains one blue edge and four red edges; that is $𝝌 (P_{2} (ν^{+}, ν^{-})) = (1,4)$ . Similarly, $𝝌 (P_{2}^{'} (ν^{+}, ν^{-})) = (4,1)$ . Hence,

V_{1} = {(2, 1), (0, 2)} and V_{2} = {(1, 4), (4, 1)} .

As a result, $D$ contains $| V_{1} | | V_{2} | = 2 \times 2 = 4$ matrices, which are

D = {(\begin{matrix} 2 & 1 \\ 1 & 4 \end{matrix}), (\begin{matrix} 2 & 1 \\ 4 & 1 \end{matrix}), (\begin{matrix} 0 & 2 \\ 1 & 4 \end{matrix}), (\begin{matrix} 0 & 2 \\ 4 & 1 \end{matrix})} .

The smallest spectral radius of these matrices is $ρ_{\min} (D) = \frac{1}{2} \sqrt{33} + \frac{1}{2} \approx 3.3723$ and a matrix in $D$ with this spectral radius is

D_{\min} = {(\begin{matrix} 0 & 2 \\ 4 & 1 \end{matrix})} .

As a conclusion, by theorem 2.1, we obtain that for the demonstrated example

\dim_{B} (Ξ) = \dim_{H} (Ξ) \approx \frac{\log 7.6533}{\log 3.3723} \approx 1 . 6742 .

Modelling the network, we obtain the simulated values given in figure 6. It shows a simulation of the Minkowski dimension of $Ξ^{5}$ , providing an estimated Minkowski dimension $1.6219$ .

See figure 5 for a fractal and scale-free complex network. It illustrates the model from figure 4 in the form of a complex network, created using Python’s NetworkX . According to previous conclusions, this complex network has an approximate Minkowski dimension of $1.6742$ and a degree dimension of $2.9361$ ( Figure 6). The degree dimension refers to the power law’s index of scale-freeness, as defined in Li & Britz [1], and it is calculated by:

Iterated graph. — Figure 5. Iterated graph system in figure 4 as a complex network.

Test of fractality. — Figure 6. Test of fractality when $n = 5$ .

\dim_{D} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ (𝐍)} \approx \frac{\log 7.6533}{\log 2} \approx 2.9361 .

We will later prove theorem 2.1 through the following two theorems.

Theorem 2.2. We will prove in §3c that:

\dim_{B} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ_{\min} (D)} .

Theorem 2.3. We will prove in §3e that:

\dim_{H} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ_{\min} (D)} .

(d) Growth rates of arcs and vertices

This section introduces several necessary tools and properties for the proof of fractality in §3. We will omit the proofs of such results that may be found in [1,24].

Notation 2.2. $\sim$ is defined as asymptotic equivalence. We write $f (x) \overset{x \to x_{0}}{≍} g (x)$ if $\lim_{x \to x_{0}} f (x) / g (x) = c$ , where $c > 0$ and $x_{0}$ may be $\infty$ . We may omit $x \to x_{0}$ if no ambiguity occurs. Let ${[𝐗]}_{i j}$ be the $i$ -row $j$ -column entry of matrix $𝐗$ .

Lemma 2.1. Let $𝐗$ be a irreducible non-negative $k \times k$ matrix with spectral radius $ρ (𝐗)$ . Then, for any non-negative vector $𝐮 \in ℝ_{\geq 0}^{k}$ and for any $n \in ℕ$ ,

c^{- 1} ρ {(𝐗)}^{n} \leq {‖ 𝐮 𝐗^{n} ‖}_{1} \leq c ρ {(𝐗)}^{n},

where $c > 1$ is a constant depending on $𝐮$ and $𝐗$ .

Lemma 2.2. Let $𝐗$ be a irreducible non-negative $k \times k$ matrix with spectral radius $ρ (𝐗)$ . Then, for any non-negative vector $𝐮 \in ℝ_{\geq 0}^{n}$ ,

{‖ 𝐮 𝐗^{n} ‖}_{1} \overset{n \to \infty}{≍} ρ {(𝐗)}^{n} .

Definition 2.9. Let $𝐌^{(n)}$ be a $K \times K$ non-negative matrix where

{[M^{(n)}]}_{i j} := {[χ (S^{n} (Ξ_{i}^{0}))]}_{j},

where $Ξ_{i}^{0}$ is only an $i$ -coloured arc.

This means $𝐌^{(n)} = (m_{i j}^{(n)})$ be the $K \times K$ matrix whose entries $m_{i j}^{(n)}$ equal the number of $j$ -coloured arcs that result from substituting arcs $n$ times, first by substituting an $i$ -coloured arc and then $n - 1$ times substituting the subsequently resulting arcs of all colours.

Lemma 2.3. For each $n \geq 1$ , $𝐌^{(n)} = 𝐌^{n}$ .

Proof. By induction.∎

Lemma 2.4. $| E (Ξ^{n}) | \overset{n \to \infty}{≍} ρ {(𝐌)}^{n}$ .

Proof. By $𝝌 (Ξ^{n}) = 𝝌 (Ξ^{n - 1}) 𝐌$ . ∎

Lemma 2.5. $| V (Ξ^{n}) | \overset{n \to \infty}{≍} ρ {(𝐌)}^{n}$ .

Proof. Define:

V^{*} (Ξ^{n}) : = {v : v \in V (Ξ^{n}), v \notin V (Ξ^{n - 1})} .

Then, $| V (Ξ^{n}) | = \sum_{i = 0}^{n} | V^{*} (Ξ^{i}) |$ . Notice all new vertices $V^{*} (Ξ^{n})$ in $V (Ξ^{n})$ are in fact generated by substituting arcs in $Ξ^{n - 1}$ . Hence, for all $n \in ℕ$ ,

\begin{matrix} | V^{*} (Ξ^{n}) | = 𝝌 (Ξ^{n - 1}) (\begin{matrix} | V (R_{1}) | - 2 \\ ⋮ \\ | V (R_{K}) | - 2 \end{matrix}) . \end{matrix}

Given the initial graph $| V (Ξ^{0}) | = 2$ ,

| V (Ξ^{n}) | = 2 + \sum_{i = 1}^{n} (χ (Ξ^{i - 1})) (\begin{matrix} | V (R_{1}) | - 2 \\ ⋮ \\ | V (R_{K}) | - 2 \end{matrix}) .

Since the row vector only contains constants,

\begin{matrix} | V (Ξ^{n}) | & \overset{n \to \infty}{≍} {‖ \sum_{i = 1}^{n - 1} 𝝌 (Ξ^{i - 1}) ‖}_{1} ≍ \sum_{i = 1}^{n - 1} ρ {(𝐌)}^{i} ≍ ρ {(𝐌)}^{n} . \end{matrix}

∎

Definition 2.10. The Gromov–Hausdorff scaling limit $G$ of graph sequence ${(G^{n})}_{n \in ℕ}$ is a sparse graph if the graph density $\lim_{n \to \infty} \frac{| E (G^{n}) |}{| V (G^{n}) | (| V (G^{n}) | - 1)} = 0$ .

Theorem 2.4. $Ξ$ can only be a sparse graph.

Proof.

lim_{n \to \infty} \frac{| E (Ξ^{n}) |}{| V (Ξ^{n}) | (| V (Ξ^{n}) | - 1)} = lim_{n \to \infty} \frac{ρ {(𝐌)}^{n}}{ρ {(𝐌)}^{n} (ρ {(𝐌)}^{n} - 1)} = 0 .

∎

3. Proof of theorem 2.1

This section is devoted to proving theorem 2.1. However, before we are to do so, a few short but technical results are required, especially theorems 3.2 and 3.3.

(a) A combinatorial matrix problem

Lemma 3.1. Suppose that, for any non-negative matrix $𝐃$ and positive row vector $𝐱$ , $min_{i} {[D x]}_{i} / {[x]}_{i} < max_{i} {[D x]}_{i} / {[x]}_{i}$ . Then $max_{i} {[D x]}_{i} / {[x]}_{i} > ρ (D)$ .

Proof. See lemma 8.1 in Li & Britz [1].∎

Recall the defined notation from definition 2.8.

Theorem 3.1. Suppose that all matrices in $D_{\min}$ are irreducible, and let $𝐝_{i} \in V_{i}$ and $𝐃_{\min} \in D_{\min}$ . Let $𝐯_{\min}$ be the corresponding right column Perron–Frobenius vector of $𝐃_{\min}$ . Then,

𝐝_{i} 𝐯_{\min} \geq ρ (𝐃_{\min}) {[𝐯_{\min}]}_{i} .

Proof. Assume that $𝐝_{i} 𝐯_{\min} < ρ (𝐃_{\min}) {[𝐯_{\min}]}_{i}$ . Define $𝐃$ to be the matrix obtained by replacing the $j$ -th row of $𝐃_{\min}$ by $𝐝_{i}$ , and note that $𝐃 \in D$ . Then for each $j \neq i$ ,

{[𝐃 𝐯_{\min}]}_{j} = {[𝐃_{\min} 𝐯_{\min}]}_{j} = ρ (𝐃_{\min}) {[𝐯_{\min}]}_{j}

whereas ${[𝐃 𝐯_{\min}]}_{i} = 𝐝_{i} 𝐯_{\min} < ρ (𝐃_{\min}) {[𝐯_{\min}]}_{i}$ . Therefore,

\min_{j} \frac{{[𝐃 𝐯_{\min}]}_{j}}{{[𝐯_{\min}]}_{j}} = \frac{{[𝐃 𝐯_{\min}]}_{i}}{{[𝐯_{\min}]}_{i}} < ρ (𝐃_{\min}) = \max_{j} \frac{{[𝐃 𝐯_{\min}]}_{j}}{{[𝐯_{\min}]}_{j}} .

By lemma 3.1,

ρ (𝐃) < \max_{j} \frac{{[𝐃 𝐯_{\min}]}_{j}}{{[𝐯_{\min}]}_{j}} = ρ (𝐃_{\min}),

contradicting the definition of $𝐃_{\min}$ .∎

Next is our second auxiliary result.

Theorem 3.2. For any number of matrices $𝐃_{1}, \dots, 𝐃_{n} \in D$ ,

ρ (\prod_{ℓ = 1}^{n} D_{ℓ}) \geq ρ_{min} {(D)}^{n} .

Proof. For each $i$ and $ℓ$ , the row vector ${[𝐃_{ℓ}]}_{i}$ satisfies ${[𝐃_{ℓ}]}_{i} 𝐯_{\min} \geq ρ (𝐃_{\min}) {[𝐯_{\min}]}_{i}$ by theorem 3.1, so

𝐃_{ℓ} 𝐯_{\min} \geq ρ (𝐃_{\min}) 𝐯_{\min} .

Then,

\prod_{ℓ = 1}^{n} D_{ℓ} v_{min} \geq ρ (D_{min}) \prod_{ℓ = 1}^{n - 1} D_{ℓ} v_{min} \geq \dots \geq ρ {(D_{min})}^{n} v_{min},

min_{i} \frac{{[\prod_{ℓ = 1}^{n} D_{ℓ} v_{min}]}_{i}}{{[v_{min}]}_{i}} \geq ρ {(D_{min})}^{n} .

By Collatz–Wielandt formula,

ρ (\prod_{ℓ = 1}^{n} D_{ℓ}) = max_{x > 0} min_{i} \frac{{[\prod_{ℓ = 1}^{n} D_{ℓ} x]}_{i}}{{[x]}_{i}} \geq min_{i} \frac{{[\prod_{ℓ = 1}^{n} D_{ℓ} v_{min}]}_{i}}{{[v_{min}]}_{i}} \geq ρ_{min} {(D)}^{n} .

∎

Remark 3.1. If $D$ is not defined the same way as definition 2.8, then the theorem does not hold. A straight example is given by:

D = {𝐃_{1} = (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}), 𝐃_{2} = (\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix})}

with $ρ (D_{1}) = ρ (D_{2}) \approx 2.6180$ . Then, $5.8284 \approx ρ (D_{1} D_{2}) \leq ρ {(D_{1})}^{2} = ρ {(D_{2})}^{2} \approx 6.8539$ .

However,

D = {𝐃_{1} = (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}), 𝐃_{2} = (\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix}), 𝐃_{3} = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}), 𝐃_{4} = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})}

is the family satisfying theorem 3.2.

The inherent property of this matrix family fundamentally ensures the existence of the Gromov–Hausdorff scaling limit $Ξ$ .

(b) Distance growth between vertices

In Li et al. [24], the authors provided an analysis of the distances between vertices in deterministic IGS, and it was proved that these distances grew with bounded growth rates. However, a feasible formula was not given to calculate these rates; they are indeed difficult to determine.

To illustrate why these distances are difficult to estimate, consider figure 7 in which a deterministic iterated graph system is shown, with just two substitution rules: one for blue arcs and one for red arcs. In the shown graph sequence $Ξ^{0} \to Ξ^{1} \to Ξ^{2}$ , the distance between the initial vertices $a$ and $b$ is 1. In $Ξ^{1}$ , this distance is 2 and is the length of the path $P^{1} (a, b)$ . However, substituting the arcs of $P^{1} (a, b)$ gives paths of length 10 between $a$ and $b$ ; this is larger than 9, the distance between $a$ and $b$ . Rather, the shortest paths between $a$ and $b$ , such as $P^{2} (a, b)$ , here arise disjointly and independently from the arcs of $P^{1} (a, b)$ .

In general, the shortest paths between vertices $a$ and $b$ in each graph $Ξ^{n}$ and the shortest paths between vertices $a$ and $b$ in $Ξ^{(n + 1)}$ may be greatly irrelevant of each other. Nevertheless, it is possible to investigate how distances develop during the substitution process. For this purpose, consider the two vertices $a$ and $b$ in $Ξ^{0}$ and let $a$ and $b$ also denote these two fixed vertices in each subsequent graph $Ξ^{n}$ , as indicated in figure 7. Let $Γ^{n} (a, b)$ denote a shortest path between $a$ and $b$ in $Ξ^{n}$ .

Definition 3.1. In this paper, we without loss of generality let $Ξ^{0}$ be a single arc, and $V (Ξ^{0}) = {a, b}$ . A path $P^{n + 1} (a, b)$ in $Ξ^{(n + 1)}$ is uniform if it arises by successive arc substitutions from paths $P^{0} (a, b), \dots, P^{n} (a, b)$ in $Ξ^{0}, \dots, Ξ^{n}$ , respectively, such that, for each $s = 0, \dots, n$ and each colour $i$ , all arcs of colour $i$ in $P^{s} (a, b)$ when substituted are in $P^{s + 1} (a, b)$ replaced by the same path between $ν^{+}$ to $ν^{-}$ in each $R_{i}$ for all $i$ . For instance, the path $P^{2} (a, b)$ in figure 7 is uniform.

Lemma 3.2. For each $n$ , at least one shortest path $Γ^{n} (a, b)$ is uniform.

Proof. For $n = 1$ , the lemma is trivially true, so assume that some shortest path $Γ^{n} (a, b)$ in $Ξ^{n}$ is uniform. Since $Ξ^{n + 1}$ can be obtained by substituting every $i$ -coloured arc in $Ξ^{1}$ by some $Ξ^{n}$ , each shortest path $Γ^{n + 1} (a, b)$ in $Ξ^{n + 1}$ is obtained by concatenating a sequence of paths $Γ^{n} (a, b)$ in different $Ξ^{n}$ . By choosing the same path $Γ^{n} (a, b)$ for each $i$ -coloured arc, the resulting shortest path $Γ^{n + 1} (a, b)$ will be uniform. Induction completes the proof.∎

Now, we focus on calculating the lengths of uniform paths recursively. Recall from definition 2.8 that $P_{i}$ is the set of subgraphs of $R_{i}$ whose underlying (undirected) graph is a path between $ν^{+}$ and $ν^{-}$ . Each element $C = (P_{1}, \dots, P_{K}) \in P$ is of the Cartesian product

P := \prod_{j = 1}^{K} P_{i} .

Note that if $P^{n} (a, b)$ is a uniform path between $a$ and $b$ , then the subsequent uniform paths $P^{n + 1} (a, b)$ arising from $P^{n} (a, b)$ are obtained by choosing an element $C \in P$ and replacing each $i$ -coloured edge of $P^{n} (a, b)$ by the value of each element in $C$ . For each tuple,

C = (P_{1}, \dots, P_{K}) \in \prod_{i = 1}^{K} P_{i},

define $D_{C}$ to be the matrix,

𝐃_{C} : = (\begin{matrix} 𝝌 (C_{1}) \\ ⋮ \\ 𝝌 (C_{K}) \end{matrix}) .

Note that $𝐃_{C} \in D$ by definition 2.8.

Lemma 3.3.

| Γ^{n} (a, b) | = min_{D_{C} \in D} {‖ χ (Ξ^{0}) \prod_{l = 1}^{n} D_{C} ‖}_{1} .

Proof. Each given tuple $C = (P_{1}, \dots, P_{K})$ determines a unique expected uniform path $P^{n + 1} (a, b)$ based on the given uniform path $P^{n} (a, b)$ . To determine the length of $P^{n + 1} (a, b)$ explicitly, recall the notation from definition 2.8. In particular, $| P^{n + 1} (a, b) | = {‖ 𝝌 (P^{n + 1} (a, b)) ‖}_{1}$ and,

{‖ 𝝌 (P^{n + 1} (a, b)) ‖}_{1} = \sum_{i = 1}^{K} 𝝌 (P^{n} (a, b)) 𝝌 {(P_{i} (a, b))}^{T} = {‖ 𝝌 (P^{n} (a, b)) 𝐃_{C} ‖}_{1} .

If we fix $Ξ^{0}$ , then

{‖ χ (P^{n + 1} (a, b)) ‖}_{1} = {‖ χ (Ξ^{0}) \prod_{l = 1}^{n} D_{C} ‖}_{1} .

As at least one shortest path $Γ^{n} (a, b)$ is proved to be uniform,

| Γ^{n} (a, b) | = min_{D_{C} \in D} {‖ χ (Ξ^{0}) \prod_{l = 1}^{n} D_{C} ‖}_{1} .

∎

Theorem 3.3.

| Γ^{n} (a, b) | \overset{n \to \infty}{≍} ρ_{\min} {(D)}^{n} .

Proof. By lemma 3.3, lemma 2.1 and theorem 3.2,

\begin{aligned} | Γ^{n} (a, b) | & = min_{D_{C} \in D} {‖ χ (Ξ^{0}) \prod_{l = 1}^{n} D_{C} ‖}_{1} \\ \overset{n \to \infty}{≍} min_{D_{C} \in D} ρ (\prod_{ℓ = 1}^{n} D_{C}) = min_{D_{ℓ} \in D} ρ (\prod_{ℓ = 1}^{n} D_{ℓ}) = ρ_{min} {(D)}^{n} . \end{aligned}

∎

(c) Proof of theorem 2.2

Definition 3.2. Let $N_{ℓ}^{*} (\hat{G})$ be the maximum number of node-disjoint boxes of $\hat{G}$ with diameter $ℓ$ . That is, $N_{ℓ}^{*} (\hat{G})$ is the packing number.

Lemma 3.4. $N_{ℓ}^{*} (\hat{G}) \leq N_{ℓ} (\hat{G})$ .

Proof. Choose $N_{ℓ}^{*} (\hat{G})$ vertices whose pairwise distances are greater than $ℓ$ . Since no subgraph of diameter at most $ℓ$ contains more than one of the covering boxes, $N_{ℓ} (\hat{G}) \geq N_{ℓ}^{*} (\hat{G})$ .∎

Notation 3.1. Let $f (x) ⪰ g (x)$ denote $f (x) \geq c \cdot g (x)$ for some given constant $c > 0$ . Similar for $f (x) ⪯ g (x)$ . Recall that $Δ (G)$ denotes the diameter of graph $G$ .

Theorem 3.4.

Δ (Ξ^{n}) \overset{n \to \infty}{≍} ρ_{\min} {(D)}^{n} .

Proof. Let $Δ_{Ξ^{n}} (V (Ξ^{n - k}))$ denote:

\sup {d_{Ξ^{n}} (u, v) : u \in V (Ξ^{n - k}), v \in V (Ξ^{n - k})} .

Note that if $k_{1} \geq k_{2}$ , then $V (Ξ^{n - k_{1}}) \subset V (Ξ^{n - k_{2}})$ , so

Δ_{Ξ^{n}} (V (Ξ^{n - k_{1}})) \leq Δ_{Ξ^{n}} (V (Ξ^{n - k_{2}})) .

Observe that,

\begin{aligned} Δ_{Ξ^{n}} (V (Ξ^{n - k})) \\ \leq Δ_{Ξ^{n}} (V (Ξ^{n - k - 1})) + 2 max {d_{Ξ^{n}} (u, v) : u \in V (Ξ^{n - k - 1}), v \in V^{*} (Ξ^{n - k})} \\ \leq Δ_{Ξ^{n}} (V (Ξ^{n - k - 1})) + 2 max_{i} Δ (R_{i}) | Γ^{k} (a, b) | . \end{aligned}

Let $R = \max_{i} Δ (R_{i})$ . Then,

\begin{aligned} Δ (Ξ^{n}) & \leq Δ_{Ξ^{n}} (V (Ξ^{n - 1})) + 2 R \\ \leq Δ_{Ξ^{n}} (V (Ξ^{n - 2})) + 2 R | Γ^{1} (a, b) | + 2 R \\ \leq \dots \leq Δ_{Ξ^{n}} (V (Ξ^{0})) + 2 R | Γ^{n - 1} (a, b) | + \dots + 2 R | Γ^{1} (a, b) | + 2 R . \end{aligned}

Note that here, $Γ^{n} (a, b)$ in fact refers to various shortest paths given different initial graphs. However, theorem 3.3 sheds light on this problem: all $Γ^{n} (a, b)$ are asymptotically equivalent without regard to some constant times. Hence, we say the right-hand side above:

\begin{aligned} RHS & \leq max {| Γ^{n} (a, b) |} + 2 R \sum_{j = 0}^{n - 1} max {| Γ^{j} (a, b) |} \\ \leq 2 R \sum_{j = 0}^{n} max {| Γ^{j} (a, b) |} \\ ⪯ \sum_{j = 0}^{n} max {| Γ^{j} (a, b) |} . \end{aligned}

By lemma 2.1, $ρ {(𝐃_{\min})}^{n} ⪯ {‖ 𝐱 𝐃_{\min}^{n} ‖}_{1} ⪯ ρ {(𝐃_{\min})}^{n}$ , as a result

\begin{aligned} ρ_{min} {(D)}^{n} ⪯ | Γ^{n} (a, b) | & \leq Δ (Ξ^{n}) \\ ⪯ \sum_{j = 0}^{n} max {| Γ^{j} (a, b) |} ⪯ \sum_{j = 0}^{n} ρ_{min} {(D)}^{j} ⪯ ρ_{min} {(D)}^{n} . \end{aligned}

∎

We now prove theorem 2.2.

Proof. By lemma 3.4,

N_{L}^{*} (Ξ^{n}) \leq N_{L} (Ξ^{n}) .

Set $L = ρ_{\min} {(D)}^{n - k}$ . We can easily find a finite constant $C$ depending on random IGS only such that $N_{L}^{*} (Ξ^{n}) ⪰ | E (Ξ^{k}) |$ in that every arc in $E (Ξ^{n - k})$ turns into a $Ξ^{k}$ in $Ξ^{n}$ . Also, $N_{L} (Ξ^{n}) ⪯ | E (Ξ^{k}) |$ since a constant number of subgraphs with diameter $L$ can cover $Ξ^{n - k}$ . Therefore,

| E (Ξ^{k}) | ⪯ N_{L}^{*} (Ξ^{n}) \leq N_{L} (Ξ^{n}) ⪯ | E (Ξ^{k}) | .

Recall theorem 2.4, providing that for $k \leq n$ ,

N_{ρ_{\min} {(D)}^{n - k}} (Ξ^{n}) \overset{k \to \infty}{≍} | E (Ξ^{k}) | \overset{k \to \infty}{≍} ρ {(𝐌)}^{k} .

Then,

\begin{aligned} \dim_{B} (Ξ) & = lim_{ℓ \to 0} \frac{\log N_{ℓ} ({\hat{Ξ}}^{n})}{- \log ℓ} \\ = lim_{n \to \infty} \frac{\log N_{L} (Ξ^{n})}{- \log \frac{L}{Δ (Ξ^{n})}} \\ = lim_{n \to \infty} \frac{\log ρ {(M)}^{k}}{- \log \frac{ρ_{min} {(D)}^{n - k}}{ρ_{min} {(D)}^{n}}} = \frac{\log ρ (M)}{\log ρ_{min} (D)} . \end{aligned}

∎

(d) Existence of the Gromov–Hausdorff scaling limit for iterated graph systems

This section aims to prove the existence of the Gromov–Hausdorff scaling limit for IGS.

Theorem 3.5. There exists $(\hat{Ξ}, d_{\hat{Ξ}})$ for the Gromov–Hausdorff scaling limit of ${(Ξ^{n})}_{n \in ℕ}$ .

Proof. Let $n \geq k \in ℕ$ . Firstly, we show a significant fact that for any $a, b \in V (Ξ^{k}) \subset V (Ξ^{n})$ , there exists $η : V (Ξ^{k}) \times V (Ξ^{k}) \to [0,1]$ such that:

η (a, b) = \lim_{n \to \infty} d_{{\hat{Ξ}}^{n}} (a, b) .

This is because

\lim_{n \to \infty} d_{{\hat{Ξ}}^{n}} (a, b) = \lim_{n \to \infty} \frac{d_{Ξ^{n}} (a, b)}{Δ (Ξ^{n})} = \lim_{n \to \infty} \frac{c_{1} ρ_{\min} {(D)}^{n - k}}{c_{2} ρ_{\min} {(D)}^{n - k}} = : η (a, b),

where $c_{1}$ is given by theorem 3.3 and $c_{2}$ is given by theorem 3.4.

We now prove that $(⋃_{n = 0}^{\infty} V (Ξ^{n}), η)$ constructs a metric space. As discussed above, $η (a, b) = \frac{c_{1}}{c_{2}} > 0$ for $a \neq b$ and clearly $η (a, b) = η (b, a)$ . As $({\hat{Ξ}}^{k}, d_{{\hat{Ξ}}^{k}})$ is metric space for $k \in ℕ$ , then for $a, b, c \in V ({\hat{Ξ}}^{k})$ ,

\begin{aligned} η (a, c) & = lim_{n \to \infty} d_{{\hat{Ξ}}^{n}} (a, c) \leq lim_{n \to \infty} (d_{{\hat{Ξ}}^{n}} (a, b) + d_{{\hat{Ξ}}^{n}} (b, c)) \\ = lim_{n \to \infty} d_{{\hat{Ξ}}^{n}} (a, b) + lim_{n \to \infty} d_{{\hat{Ξ}}^{n}} (b, c) \\ = η (a, b) + η (b, c) . \end{aligned}

Therefore, we trickily consider the metric space $({\hat{Ξ}}^{n}, η)$ and note that $({\hat{Ξ}}^{n}, η) \neq ({\hat{Ξ}}^{n}, d_{{\hat{Ξ}}^{n}})$ . We now construct a $η$ for nested set by, for $X \subset Y$ , $x \in X$ , $y \in Y$ and $y_{x} \in Y$ :

η (x, y) = {\begin{cases} η_{X \cup Y} (x, y) = 0 & if y \in X, \\ η_{X \cup Y} (x, y) = η_{Y} (y_{x} = x, y) & if y \notin X . \end{cases}

Given that $V (Ξ) = ⋃_{n \in ℕ} V (Ξ^{n})$ is a nested set, the construction is used to show that by theorem 3.4:

\begin{aligned} d_{G H} (({\hat{Ξ}}^{n}, η), (\hat{Ξ}, η)) & = d_{H}^{η} (V ({\hat{Ξ}}^{n}), V (\hat{Ξ}) ∖ V ({\hat{Ξ}}^{n})) \\ = sup_{x \in V ({\hat{Ξ}}^{n})} η (x, V ({\hat{Ξ}}^{n + 1}) ∖ V ({\hat{Ξ}}^{n})) \\ ⪯ \frac{1}{Δ (Ξ^{n})} ⪯ \frac{1}{ρ_{min} {(D)}^{n}} . \end{aligned}

Finally,

0 \leq lim_{n \to \infty} d_{G H} (({\hat{Ξ}}^{n}, η), (⋃_{n = 0}^{\infty} V (Ξ^{n}), η)) \leq lim_{n \to \infty} \frac{1}{ρ_{min} {(D)}^{n}} = 0 .

Writing $\hat{Ξ} := (⋃_{n = 0}^{\infty} V ({\hat{Ξ}}^{n}), η)$ , we obtain the desired result.∎

A dynamical system on metric space $(X, d)$ under mapping $T$ is said to be distal if for any $x \neq y$ , $\inf_{n \in ℕ} d (T^{n} (x), T^{n} (y)) > 0$ .

Corollary 3.1. $(\hat{Ξ^{n}}, d_{{\hat{Ξ}}^{n}})$ and $(\hat{Ξ}, d_{\hat{Ξ}})$ under $S$ are distal.

A topological space $X$ is said to be $T_{6}$ (perfectly normal Hausdorff) if it is normal and every closed subset is a $G_{δ}$ subset. A straight fact is that every metrizable space is perfectly normal Hausdorff.

Corollary 3.2. $(\hat{Ξ}, d_{\hat{Ξ}})$ is a $T_{6}$ space.

(e) Proof of theorem 2.3

This subsection aims to demonstrate a result for the Hausdorff dimension of $Ξ$ . It can be done by showing $Ξ$ is quasi-self-similar and then applying Falconer’s implicit theorem [31]. However, since this subsection will define a slightly different Hausdorff dimension for graphs, we are to present a full proof for the desired result and also a proof of quasi-self-similarity.

There is a substantial amount of literature on the equivalence of box dimension and Hausdorff dimension, particularly in the context of invariant measures in various iterated systems. For instance, see [9,18–20,28].

Federer and Rogers [32,33] have sufficiently investigated Hausdorff measure and dimension on metric spaces. We now introduce a definition of Hausdorff dimension for graphs.

Definition 3.3. Define Vertex Hausdorff measure for graph $G = (V (G), E (G))$ :

H^{s} (V (G)) = lim_{δ \to 0} inf {\sum_{i = 1}^{\infty} Δ {(U_{i})}^{s} : {U_{i}} is a δ_{V} -cover of V (\hat{G})} .

Then, set $\dim_{H} (V (G)) = \inf {s \geq 0 : H^{s} (V (G)) = 0}$ . Here ${U_{i}}$ is a $δ_{V}$ -cover for $V (\hat{G})$ if

V (\hat{G}) \subset ⋃_{i = 1}^{\infty} V (U_{i}) .

Define Edge Hausdorff measure for graphs that,

H^{s} (E (G)) = lim_{δ \to 0} inf {\sum_{i = 1}^{\infty} Δ {(U_{i})}^{s} : {U_{i}} is a δ_{E} -cover of E (\hat{G})} .

Then, set $\dim_{H} (E (G)) = \inf {s \geq 0 : H^{s} (E (G)) = 0}$ . Here ${U_{i}}$ is a $δ_{E}$ -cover for $E (\hat{G})$ if

E (\hat{G}) \subset ⋃_{i = 1}^{\infty} E (U_{i}) .

Let the Hausdorff dimension for graphs be:

\dim_{H} (G) = \max {\dim_{H} (V (G)), \dim_{H} (E (G))} .

Remark 3.2. There is no inequality between $\dim_{H} (V (G))$ and $\dim_{H} (E (G))$ .

An example is exactly IGS. Choosing any $n$ , there is always $| (V (Ξ^{n}) | \geq | (E (Ξ^{n}) |$ . However, $V (Ξ)$ is countable while $E (Ξ)$ is uncountable. Hence, we have $\dim_{H} (V (Ξ)) = 0$ , but uncountably many arcs imply that $\dim_{H} (E (Ξ)) > 0$ . Though this is very much a straight fact, it is occasionally called the paradox of the binary tree.

Theorem 3.6.

\dim_{H} (Ξ) = \dim_{B} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ_{\min} (D)} .

Proof. By theorem 2.2,

\dim_{B} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ_{\min} (D)} .

By remark 3.2, we have $\dim_{H} (V (Ξ)) = 0$ and

\dim_{H} (Ξ) = \dim_{H} (E (Ξ)) .

It is trivial to check that

\dim_{H} (Ξ) \leq \dim_{B} (Ξ) .

Hence, we only need to calculate the lower bound of the Hausdorff dimension.

Fix $n$ and consider $Ξ^{n}$ . Let ${U_{i}}$ be a $δ$ -cover of $E ({\hat{Ξ}}^{n})$ . We define:

k : = \inf {s : \max {| Γ^{s} |} \geq Δ (U_{i}) Δ (Ξ^{n})} .

Accordingly, as theorem 3.3 points out the growth of $| Γ^{k} |$ , we can also have:

\max {| Γ^{k} |} ⪯ Δ (U_{i}) Δ (Ξ^{n}) .

Picking any node $v_{U_{i}} \in U_{i}$ , let

τ_{i} = {v : d_{Ξ^{n}} (v, v_{U_{i}}) \leq \max {| Γ^{k} |}} .

Then, it is clear that $U_{i} \subset τ_{i}$ and thus $| E (U_{i}) | \leq | E (τ_{i}) |$ . Given that $Δ (τ_{i}) Δ (Ξ^{n}) \leq 2 \max {| Γ^{k} |}$ , we can always find a constant $c$ (not depending on $n$ ) such that $τ_{i}$ is a subgraph of some $Ξ^{k + c}$ . This is because substitution networks can be reckoned as a composition of many $Ξ^{k + c}$ (if $n$ is large enough).

As a result,

U_{i} \subset τ_{i} \subset Ξ^{k + c} \subset Ξ^{n}

and hence $| E (U_{i}) | \leq | E (Ξ^{k + c}) |$ . Therefore,

\begin{aligned} {(Δ (U_{i}) Δ (Ξ^{n}))}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}} & ⪰ max {| Γ^{k} |}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}} \\ ⪰ Δ {(Ξ^{k})}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}} \\ ⪰ Δ {(Ξ^{k + c})}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}} \\ ⪰ | E (Ξ^{k + c}) | \geq | E (U_{i}) | \end{aligned}

by lemma 3.3 and theorem 3.4.

Finally, because ${U_{i}}$ is a covering, by lemma 2.5,

\begin{aligned} H^{\frac{\log ρ (M)}{\log ρ_{min} (D)}} (E (\hat{Ξ})) & = lim_{n \to \infty} \sum_{i = 1}^{\infty} Δ {(U_{i})}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}} \\ = lim_{n \to \infty} \sum_{i = 1}^{\infty} {(\frac{Δ (U_{i}) Δ (Ξ^{n})}{Δ (Ξ^{n})})}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}} \\ ⪰ lim_{n \to \infty} \frac{\sum_{i = 1}^{\infty} | E (U_{i}) |}{Δ {(Ξ^{n})}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}}} \\ ⪰ lim_{n \to \infty} \frac{| E (Ξ^{n}) |}{Δ {(Ξ^{n})}^{\frac{\log ρ (M)}{\log ρ_{min} (D)}}} \geq lim_{n \to \infty} \frac{ρ {(M)}^{n}}{ρ {(M)}^{n}} = 1 . \end{aligned}

Hence,

\dim_{H} (Ξ) = \dim_{B} (Ξ) = \frac{\log ρ (𝐌)}{\log ρ_{\min} (D)},

which completes the proof of theorem 2.1.∎

Definition 3.4. A metric space $(X, d)$ is said to be quasi-self-similar if there exists $c \in ℝ$ such that for any $U \subset B \subset X$ with $B$ being a ball, there is a mapping $φ : U \to X$ such that for $x, y \in U$ :

c^{- 1} d (x, y) \leq diam (U) d (φ (x), φ (y)) \leq c d (x, y) .

Theorem 3.7. $\hat{Ξ}$ is quasi-self-similar.

Proof. Recall $V (Ξ) = ⋃_{n = 0}^{\infty} V (Ξ^{n})$ and $V^{*} (Ξ^{n}) : = V (Ξ^{n}) ∖ V (Ξ^{n - 1})$ .

Let $n, m, c_{1} \in ℕ$ and $x, y \in V^{*} (Ξ^{n})$ . By the property of dynamical systems, any $U$ must be a subgraph generated by some arc in $E (Ξ_{1}^{c})$ with $c_{1} \leq K$ , say $e^{*} (U)$ . Hence, we only need to define the mapping from the subgraph generated by $e^{*} (U)$ . Without loss of generality, let $U$ be the graph generated by $e^{*} (U)$ .

By theorem 3.4, we have:

\begin{matrix} diam (U) = \frac{c_{2}}{ρ_{\min}^{m} (D)} . \end{matrix}

(3.1)

Based on $Ξ^{m}$ has $C (e^{*} (U))$ -coloured arc, we can define a natural bijection:

φ : S^{m + n} (e^{*} (U)) \leftrightarrow Ξ^{k + n},

because these two graphs are exactly the same for each $n \in ℕ$ . As a result, for any $x, y \in V^{*} (S^{m + n} (e^{*} (U)))$ , we have by theorem 3.3

\begin{matrix} \frac{c_{3}^{- 1}}{ρ_{\min}^{k + n} (D)} \leq d (φ (x), φ (y)) \leq \frac{c_{3}}{ρ_{\min}^{k + n} (D)} . \end{matrix}

(3.2)

Also by theorem 3.3,

\begin{matrix} \frac{c_{4}^{- 1}}{ρ_{\min}^{m + n} (D)} \leq d (x, y) \leq \frac{c_{4}}{ρ_{\min}^{m + n} (D)} . \end{matrix}

(3.3)

In light of equations (3.1)–(3.3), we obtain:

\begin{aligned} {(c_{2} c_{3} c_{4} ρ_{min}^{c_{1}} (D))}^{- 1} & \leq c_{2} c_{3}^{- 1} c_{4}^{- 1} ρ_{min}^{c_{1}} (D) = c_{2} c_{3}^{- 1} c_{4}^{- 1} \frac{ρ_{min}^{m + n} (D)}{ρ^{m} ρ_{min}^{c_{1} + n} (D)} \\ \leq \frac{d i a m (U) d (φ (x), φ (y))}{d (x, y)} \leq c_{2} c_{3} c_{4} \frac{ρ_{min}^{m + n} (D)}{ρ_{min}^{m} (D) ρ_{min}^{c_{1} + n} (D)} = c_{2} c_{3} c_{4} ρ_{min}^{c_{1}} (D) . \end{aligned}

∎

Corollary 3.3. By [ 31 ], we have $\dim_{H} (Ξ) = \dim,_{B} (Ξ) = \dim_{B} (Ξ)$ .

4. Random iterated graph systems and proof of theorem 4.1

(a) Random iterated graph systems

Definition 4.1. See figure 8 for example.

Let $K \in ℕ$ be the number of colours. $q_{i} \in ℕ$ is the number of seed graphs for colour $i$ where $i \in [1, K] \cap ℕ$ . The Random Iterated Graph System is a quadruple $R = (Ξ^{0}, R, Q, S)$ satisfying

—	$Ξ^{0}$ is a finite directed graph;
—	$R = {R_{i}}_{i = 1}^{K}$ where $R_{i} = {R_{i j}}_{j = 1}^{q_{i}}$ are called seed graphs. In each seed graph $R_{i j}$ , it must contain two planting vertices ${ν_{i j}^{+}, ν_{i j}^{-}} \subset V (R_{i j})$ ;
—	$ϱ_{i}$ is a discrete probability measure $ϱ_{i} : R_{i} \to [0,1]$ for each $i \in [1, K] \cap ℕ$ such that $\sum_{j = 1}^{q_{i}} ϱ_{i} (R_{i j}) = 1$ . Hence, ${(ϱ_{i} (R_{i j}))}_{j = 1}^{q_{i}}$ is a probability vector and $Q = {{(ϱ (R_{i j}))}_{j = 1}^{q_{i}}}_{i = 1}^{K}$ is a family of probability vectors.

Let $C : E (G) \to [1, K] \cap ℤ$ be a colour function. A random substitution operator is defined as

—

$S : e = (a, b) \mapsto R_{C (e) j}$ fixing $ν_{C (e) j}^{+} = a, ν_{C (e) j}^{-} = b$ with probability $ϱ_{C (e)} (R_{C (e) j})$ ,

where $ν^{+}$ and $ν^{-}$ coincide with the starting vertex $a$ and ending vertex $b$ of $e$ respectively. In this paper, we require $d_{R_{i j}} (ν_{i j}^{+}, ν_{i j}^{-}) \geq 2$ .

We now define a discrete time stochastic process of graphs ${(Ξ^{n})}_{n \in ℕ}$ by:

Ξ^{n + 1} : = S (Ξ^{n}) : = ⋃_{e \in E (Ξ^{n})} S (e)

with probability $\prod_{e \in E (Ξ^{n})} ϱ_{C (e)} (R_{C (e) j})$ if such arc $e$ is substituted with $R_{C (e) j}$ in $Ξ^{n + 1}$ .

Let $G^{n + 1}$ be the collection of all possible $Ξ^{n + 1}$ . The discrete probability space $(G^{n + 1}, F_{n + 1}, ℙ_{n + 1})$ is given by $F_{n + 1}$ being a filtration on sigma-algebra $σ (G^{n})$ and $ℙ_{n} : σ (G^{n}) \to [0,1]$ being a discrete probability measure. To be specific,

P (Ξ^{n + 1} | F_{n + 1}) = \prod_{e \in E (Ξ^{n})} ϱ_{C (e)} (R_{C (e) j}) and clearly \sum_{Ξ^{n + 1} \in G^{n + 1}} P (Ξ^{n + 1} | F_{n + 1}) = 1 .

We call the stochastic process of graphs ${(Ξ^{n})}_{n \in ℕ}$ random substitution networks . Let $Ξ$ be the Gromov–Hausdorff scaling limit of some stochastic process ${(Ξ^{n})}_{n \in ℕ}$ and denote the collection of all possible $Ξ$ by $G^{\infty}$ .

By Kolmogorov extension theorem, there exists a unique probability measure $ℙ$ in $(G^{\infty}, F, ℙ)$ . In this paper, we focus on the properties of sample space $G^{\infty}$ with the extended probability measure $ℙ$ defined above.

See figure 8 for example. For each $i = 1, \dots, K$ , set positive integers $q_{i}$ , which is the number of possible rule graphs of colour $i$ . Each directed seed graph $R_{i j}$ has a vertex $ν^{+}$ and a vertex $ν^{-}$ that, respectively, replace the beginning node $ν^{+}$ and ending node $ν^{-}$ of $e$ ; this will determine exactly how $R_{i j}$ replaces $e$ . In addition, in this paper, we always require $d_{R_{i j}} (ν_{i j}^{+}, ν_{i j}^{-}) \geq 2$ for all $i$ and $j$ .

Intuitively, to construct a sequence of growing graphs,

—	start from the initial graph $Ξ^{0}$ , which is usually just a single arc;
—	we construct $Ξ^{1}$ by replacing all $i$ -coloured arcs in $Ξ^{0}$ randomly by a graph in $R_{i}$ , say $R_{i j}$ with probability $ϱ_{i} (R_{i j})$ . Note here, as stated above, that the substitutions regarding node $ν^{+}$ and $ν^{-}$ are unique;
—	we then iteratively replace all $i$ -coloured arcs for all $i = 1, \dots, K$ to obtain $Ξ^{2}$ . In this way, denote the graph after $n \in ℕ$ iterations by $Ξ^{n}$ ; accordingly, we have a stochastic process of graphs ${(Ξ^{n})}_{n \in ℕ}$ called random substitution networks.

(b) Relevant definitions

Definition 4.2. A finite set containing $k \times k$ irreducible matrices $X = {𝐗_{1}, \dots, 𝐗_{m}}$ with a probability vector $(p_{1}, \dots, p_{m})$ is called a random matrices ensemble [34].

Definition 4.3. Let

M = {M = (\begin{matrix} χ (R_{1 j_{1}}) \\ \dots \\ χ (R_{K j_{K}}) \end{matrix}) : j_{i} = 1, \dots, q_{i}}

be with $ℙ (𝐌) = \prod_{i = 1}^{K} ϱ (R_{i j_{i}})$ . Clearly $\sum_{𝐌 \in M} ℙ (𝐌) = 1$ , and hence $M$ is a random matrices ensemble with $| M | = \prod_{i = 1}^{K} q_{i}$ elements.

Definition 4.4. Let $P_{i j} (ν_{i j}^{+}, ν_{i j}^{-})$ be a path between $ν_{i j}^{+}$ and $ν_{i j}^{-}$ in $R_{i j}$ , and $P_{i j} (ν_{i j}^{+}, ν_{i j}^{-})$ be the collection of all possible $P_{i j} (ν_{i j}^{+}, ν_{i j}^{-})$ in $R_{i j}$ . For convenience, we will here write $P_{i j} (ν_{i j}^{+}, ν_{i j}^{-})$ and $P_{i j} (ν_{i j}^{+}, ν_{i j}^{-})$ simply as $P_{i j}$ and $P_{i j}$ .

D = {D = (\begin{matrix} χ (P_{1 j_{1}}) \\ \dots \\ χ (P_{K j_{K}}) \end{matrix}) : j_{i} = 1, \dots, q_{i}} .

By the definition, $D$ is a set containing $| D | = \prod_{i = 1}^{K} q_{i}$ matrices with:

P (D = (\begin{matrix} χ (P_{1 k_{1}}) \\ \dots \\ χ (P_{K k_{K}}) \end{matrix}) | D \in D) = \prod_{i = 1}^{K} ϱ (R_{i k_{i}}) .

In this way, $D$ is a random matrices ensemble.

Let

D = {D : P_{i j_{i}} \in P_{i j_{i}}, i = 1, \dots, K} .

In other words, $D$ is a collection of all possible random matrices ensembles $D$ . Moreover,

| D | = \prod_{i = 1}^{K} \prod_{j = 1}^{q_{i}} | P_{i j} | .

If all matrices in $M$ and $D \in D$ are irreducible, we say the random iterated graph $R$ system is irreducible.

Notation 4.1. Let $L (X)$ be the (maximal) Lyapunov exponent of random matrices ensemble $X$ with probability vector. We will strictly define $L (*)$ in §4c.

Theorem 4.1. (main theorem). Given any random irreducible iterated graph system, for $ℙ$ -almost all $Ξ$ in $G^{\infty}$ , or equivalently:

ℙ (\dim_{B} (Ξ) = \dim_{H} (Ξ) = \frac{L (M)}{\min_{D \in D} L (D)}) = 1 .

Remark 4.1. For any network with a given algebraic number fractal dimension, we can always directly construct a random iterated graph system that possesses the same dimension.

Example 4.1.

M = {(\begin{matrix} 3 & 3 \\ 4 & 2 \end{matrix}), (\begin{matrix} 3 & 3 \\ 2 & 2 \end{matrix}), (\begin{matrix} 0 & 3 \\ 4 & 2 \end{matrix}), (\begin{matrix} 0 & 3 \\ 2 & 2 \end{matrix})},

respectively, with the probability vector $(\frac{1}{12}, \frac{1}{4}, \frac{1}{6}, \frac{1}{2})$ . The Lyapunov exponent:

L (M) \approx 1.4488 .

Hence, in this example, $D$ contains $| P_{11} | \times | P_{12} | \times | P_{21} | \times | P_{22} | = 2 \times 1 \times 3 \times 2 = 12$ random matrices ensembles.

\begin{aligned} D = \\ {{(\begin{matrix} 1 & 2 \\ 1 & 1 \end{matrix}), (\begin{matrix} 1 & 2 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 3 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 3 \\ 1 & 1 \end{matrix})}, {(\begin{matrix} 3 & 1 \\ 1 & 1 \end{matrix}), (\begin{matrix} 3 & 1 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 3 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 3 \\ 1 & 1 \end{matrix})}, \\ {(\begin{matrix} 3 & 1 \\ 2 & 0 \end{matrix}), (\begin{matrix} 3 & 1 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 3 \\ 2 & 0 \end{matrix}), (\begin{matrix} 0 & 3 \\ 1 & 1 \end{matrix})}, {(\begin{matrix} 1 & 2 \\ 2 & 0 \end{matrix}), (\begin{matrix} 1 & 2 \\ 1 & 1 \end{matrix}), (\begin{matrix} 0 & 3 \\ 2 & 0 \end{matrix}), (\begin{matrix} 0 & 3 \\ 1 & 1 \end{matrix})}, \dots} \end{aligned}

all with the probability vector $(1 / 12, 1 / 4, 1 / 6, 1 / 2)$ . The Lyapunov exponents of elements shown in $D$ above are ${0.8717,0.9474,0.9705,0.8900, \dots}$ , respectively. Finding the smallest Lyapunov exponent in $D$ , it is $\min_{D \in D} L (D) \approx 0.8717$ .

By theorem 4.1, we have the theoretical dimension:

\dim_{B} (Ξ) \overset{P -a.e.}{=} \frac{L (M)}{min_{D \in D} L (D)} \approx \frac{1.4488}{0.8717} = 1.6620 .

Similarly modelling the limit graph, we obtain the simulated values given in figure 9 . It shows 10 times of simulating Minkowski dimensions of $Ξ^{5}$ , providing an estimated Minkowski dimension $1.4275$ .

Ten simulations of fractality when n = 5. — Figure 9. Ten simulations of fractality when $n = 5$ .

(c) Lyapunov exponents and stochastic substitution systems

This subsection is devoted to studying the stochastic behaviours of random IGS. We summarize the process of random substitution on graph fractals to so-called stochastic substitution systems, and we prove some properties of the associated Lypunov exponents. Therefore, we shall start by introducing Lyapunov exponents.

Lyapunov exponents regarding products of random matrices were first studied by Bellman [35]. Furstenberg and Kesten [36,37] then developed a couple of famous results of the asymptotic behaviours for products of random matrices. Recently, Pollicott [38,39] presented several impressive works on effective numerical estimates of Lyapunov exponents.

We will continue to use the notations in Pollicott [38] for Lyapunov exponents. Let $X = {𝐗_{1}, \dots, 𝐗_{m}}$ be a random irreducible and invertible matrices set with probability vector $(p_{1}, \dots, p_{m})$ . Consider the sequence space $Σ = {1, \dots, m}^{ℤ^{+}}$ , and $μ$ be the corresponding Bernoulli measure on such space. Choosing $i = {(i_{n})}_{n = 1}^{\infty} \in Σ$ , the Lyapunov exponent of products of random matrices is defined as:

\begin{aligned} L (X) & := lim_{n \to \infty} \frac{1}{n} E (\log ‖ X_{i_{1}} \dots X_{i_{n}} ‖) = lim_{n \to \infty} \frac{1}{n} \int_{\underline{i} \in Σ} \log ‖ X_{i_{1}} \dots X_{i_{n}} ‖ d μ (\underline{i}) . \end{aligned}

(4.1)

Furstenberg & Kesten [36] develop that if $X_{i_{n}}$ is a stationary stochastic process, for almost every $(μ)$ $i \in Σ$ , there is

\begin{matrix} L (X) = \lim_{n \to \infty} \frac{1}{n} \log ‖ 𝐗_{i_{1}} \dots 𝐗_{i_{n}} ‖ = \lim_{n \to \infty} \frac{1}{n} \log {[𝐗_{i_{1}} \dots 𝐗_{i_{n}}]}_{j k}, \end{matrix}

(4.2)

for any $j k$ entry. In this subsection, $‖ * ‖$ is valid for any norm.

In this paper, we will discuss a type of slightly different matrix product, but it will be proved the Lyapunov exponent of such a system coincides with the associated products of random matrices.

Definition 4.5. Let $X$ be a random matrices ensemble with probability vector $Q = (p_{1}, \dots, p_{m})$ . For each $i = 1, \dots, k$ , let $𝐞_{i}$ be the $i$ -th standard basis unit vector of $ℝ^{k}$ .

Define a random operator $ψ : {𝐞_{1}, \dots, 𝐞_{k}} \to ℤ_{+}^{k}$ . Define $k$ identical and independent $ψ (𝐞_{1}), \dots, ψ (𝐞_{k})$ , each with probability function:

ℙ (ψ (𝐞_{i}) = 𝐞_{i} 𝐗_{j}) = p_{j} .

Here, the random operator $ψ$ randomly maps a basis unit vector to some vector by a certain probability distribution. Consider any non-negative vector $𝐱 = {[𝐱]}_{1} 𝐞_{1} + \dots + {[𝐱]}_{k} 𝐞_{k} \in ℤ_{+}^{k}$ , and define the random operator $Ψ : ℤ_{+}^{k} \to ℤ_{+}^{k}$ by:

Ψ (x) = \overset{x_{1}}{\overset{⏞}{ψ (e_{1}) + \dots + ψ (e_{1})}} + \dots + \overset{x_{k}}{\overset{⏞}{ψ (e_{k}) + \dots + ψ (e_{n})}} .

Let $𝜶_{0}$ be a given non-negative vector with integer entries and define a sequence of stochastic vectors ${𝜶_{n}}_{n \geq 1}$ by the iterations:

𝜶_{n} = Ψ (𝜶_{n - 1}) .

We call such the triple $S = (‖ 𝜶_{n} ‖, 𝜶_{0}, X)$ a stochastic substitution system. Let $(Ω, F_{n}, ℙ)$ be a probability space with $Ω$ being a sample space.

Definition 4.6. Let $S = (‖ 𝜶_{t} ‖, 𝜶_{0}, X)$ be a stochastic substitution system. The Lyapunov exponent of $S$ is defined by:

L (S) : = \lim_{n \to \infty} \frac{1}{n} 𝔼 (\log ‖ 𝜶_{n} ‖),

where $𝔼$ is the expectation.

Theorem 4.2. Let $S = (‖ 𝜶_{n} ‖, 𝜶_{0}, X)$ be a stochastic substitution system. Then,

L (S) = L (X) .

Proof. First, $𝜶_{0}$ is a non-negative row vector. By formula (4.2), we have:

\lim_{n \to \infty} \frac{1}{n} \log ‖ 𝐗_{i_{1}} \dots 𝐗_{i_{n}} ‖ = \lim_{n \to \infty} \frac{1}{n} \log ‖ 𝜶_{0} 𝐗_{i_{1}} \dots 𝐗_{i_{n}} ‖ .

Because $X_{i_{n}}$ are all independent, it is found

\begin{aligned} E (\log ‖ α_{0} X_{i_{1}} \dots X_{i_{n}} ‖) & = \log ‖ E (α_{0} X_{i_{1}} \dots X_{i_{n}}) ‖ \\ = \log ‖ E (Φ (α_{0})) E (X_{i_{2}} \dots X_{i_{n}}) ‖ = \log ‖ E (α_{1}) E (X_{i_{2}} \dots X_{i_{n}}) ‖ \\ = \dots = \log ‖ E (α_{n}) ‖ . \end{aligned}

Finally, by the above,

\begin{aligned} L (X) & = lim_{n \to \infty} \frac{1}{n} E (\log ‖ X_{i_{1}} \dots X_{i_{n}} ‖) \\ = lim_{n \to \infty} \frac{1}{n} \log ‖ E (α_{n}) ‖ = lim_{n \to \infty} \frac{1}{n} E (\log ‖ α_{n} ‖) \\ = L (S) . \end{aligned}

∎

Theorem 4.3. For $ℙ$ -almost all $Ξ \in G^{\infty}$

‖ 𝜶_{n} ‖ ≍ \exp {(L (X))}^{n} .

Proof. By formula (4.2) and theorem 4.2.∎

(d) Growths of arcs and vertices

Lemma 4.1. $ℙ$ -almost surely, $| E (Ξ^{n}) | \overset{n \to \infty}{≍} \exp {(L (M))}^{n}$ .

Proof. $(| E (Ξ^{n}) | = {‖ χ (Ξ^{n}) ‖}_{1}, χ (Ξ^{0}), M)$ is clearly a stochastic substitution system because every arc substitution is independent and associated with some matrix in $M$ . Then by theorem 4.3, we obtain the desired result.∎

Lemma 4.2. $ℙ$ -almost surely, $| V (Ξ^{n}) | \overset{n \to \infty}{≍} \exp {(L (M))}^{n}$ .

Proof. This proof is of the form of lemma 2.5, by lemma 4.1 providing that almost surely $| E (Ξ) | \overset{n \to \infty}{≍} \exp {(L (M))}^{n}$ .∎

Theorem 4.4. $Ξ$ is always a sparse graph.

Proof. For all possible $Ξ \in G^{\infty}$ , there are always

\lim_{n \to \infty} \frac{| E (Ξ^{n}) |}{| V (Ξ^{n}) | (| V (Ξ^{n}) | - 1)} = \lim_{n \to \infty} \frac{\exp {(L (M))}^{n}}{\exp {(L (M))}^{n} (\exp {(L (M))}^{n} - 1)} = 0 .

∎

Remark 4.2. Theorem 4.4 holds even if all graphs in $R$ are complete graphs.

(e) Proof of theorem 4.1

For notational convenience, write $L_{\min} (D) : = \min_{D \in D} L (D) .$

Lemma 4.3. $ℙ (| Γ^{n} (a, b) | ≍ \exp {(L_{\min} (D))}^{n}) = 1$ .

Proof. For a certain $D \in D$ , we verify that $({‖ 𝝌 (Γ^{n} (a, b)) ‖}_{1}, 𝝌 (Γ^{0}), D)$ is a stochastic substitution system. This is because for any $i$ -coloured arc in $Γ^{n} (a, b)$ , we can always fix one $P_{i j} (ν_{i j}^{+}, ν_{i j}^{-})$ and the path generated by these paths in $Γ^{n + 1} (a, b)$ is also uniform.

By lemma 3.2, there exists one $D$ such that $Γ^{n} (a, b)$ is almost surely the shortest. In other words, for every rule graph $R_{i j}$ , even though there are (one or) many possible paths between $ν^{+}$ and $ν^{-}$ , lemma 3.2 always guarantees that an optimization can be achieved if we only pick one particular path between $ν^{+}$ and $ν^{-}$ from each $R_{i j}$ .

Hence, the paths between $ν^{+}$ and $ν^{-}$ in $Ξ^{n}$ all possess growth rate $\exp (L (D))$ . Among them, the shortest path $Γ^{n} (a, b)$ should follow the growth rate $\exp (L_{\min} (D))$ .

∎

Lemma 4.4. $ℙ (Δ (Ξ^{n}) ≍ \exp {(L_{\min} (D))}^{n}) = 1$ .

Proof. The analogous proof is established like theorem 3.4, by lemma 4.3.∎

We are now able to prove theorem 4.1.

Proof. We start by verifying the Minkowski dimension. By lemma 4.4, the growth of diameter of $Ξ^{n}$ is almost surely $\exp (L_{\min} (D))$ . It is feasible that we use the tricks in the proof of theorem 2.2 in §3c. Similarly, we obtain that $| E (Ξ^{k}) | ⪯ N_{L}^{*} (Ξ^{n}) \leq N_{L} (Ξ^{n}) ⪯ | E (Ξ^{k}) |$ holds for almost every $Ξ \in G^{\infty}$ . This suffices to have $\dim_{B} (Ξ) = \frac{L (M)}{L_{\min} (D)}$ with probability measure $1$ .

In the sense of the Hausdorff dimension, we also adopt the definition in §3e. With the same techniques to estimate the mass distribution, the result boils down to, $ℙ$ -almost surely, $\dim_{H} (Ξ) = L (M) / L_{min} (D)$ .

Consequently, for $ℙ$ -almost all $Ξ \in G^{\infty}$ ,

\dim_{B} (Ξ) = \dim_{H} (Ξ) = \frac{L (M)}{\min_{D \in D} L (D)},

which completes the final proof.∎

Data accessibility

This article has no additional data.

Declaration of AI use

I have not used AI-assisted technologies in creating this article.

Authors’ contributions

Z.N.: conceptualization, data curation, formal analysis, funding acquisition, investigation, methodology, project administration, resources, software, validation, visualization, writing—original draft, writing—review and editing.

Conflict of interest declaration

I declare I have no competing interests.

Funding

This work was supported by the Additional Funding Programme for Mathematical Sciences, delivered by EPSRC (EP/V521917/1) and the Heilbronn Institute for Mathematical Research. This work was also supported by the EPSRC Centre for Doctoral Training in Mathematics of Random Systems: Analysis, Modelling and Simulation (EP/S023925/1).

Acknowledgements

The author would like to thank his mom Birong Lin for her persistent support. The author would like to thank Thomas Britz and the anonymous reviewers for their precious comments. The author would like to thank Mark Pollicott for his profound suggestions.

Footnotes

Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, provided the original author and source are credited.

VIEW FULL TEXT DOWNLOAD PDF

References

1.
Li NZ, Britz T . 2024 On the scale-freeness of random colored substitution networks. Proc. Amer. Math. Soc. 152 , 1377–1389. (doi:10.1090/proc/16604) Web of Science, Google Scholar
2.
Watts DJ, Strogatz SH . 1998 Collective dynamics of ‘small-world’ networks. Nature 393 , 440–442. (doi:10.1038/30918) Crossref, PubMed, Web of Science, Google Scholar
3.
Barabasi A, Albert R . 1999 Emergence of scaling in random networks. Science 286 , 509–512. (doi:10.1126/science.286.5439.509) Crossref, PubMed, Web of Science, Google Scholar
4.
Song C, Havlin S, Makse HA . 2005 Self-similarity of complex networks. Nature 433 , 392–395. (doi:10.1038/nature03248) Crossref, PubMed, Web of Science, Google Scholar
5.
Rauzy G . 1951 Nombres algébriques et substitutions. Bulletin de la Société mathématique de France 79 , 147–178. (doi:10.24033/bsmf.1957) Crossref, Google Scholar
6.
Thurston WP . 1989 Groups, tilings and finite state automata. AMS colloquium lectures. USA: Geometry Computing Group. Google Scholar
7.
Fogg NP . 2002 Substitutions in dynamics, arithmetics and combinatorics. In Lecture notes in mathematics, vol. 1794. Berlin, Germany: Springer-Verlag. (doi:10.1007/b13861) Google Scholar
8.
Barge M, Kwapisz J . 2006 Geometric theory of unimodular Pisot substitutions. Amer. J. Math. 128 , 1219–1282. (doi:10.1353/ajm.2006.0037) Crossref, Web of Science, Google Scholar
9.
Hutchinson JE . 1981 Fractals and self-similarity. Ind. Univ. Math. J. 30 , 713–747. (doi:10.1512/iumj.1981.30.30055) Crossref, Web of Science, Google Scholar
10.
Mauldin RD, Williams SC . 1988 Hausdorff dimension in graph directed constructions. Trans. Am. Math. Soc. 309 , 811–829. (doi:10.2307/2000940) Crossref, Web of Science, Google Scholar
11.
Edgar GA, Mauldin RD . 1992 Multifractal decompositions of digraph recursive fractals. Proc. Lond. Math. Soc. 65 , 604–628. (doi:10.1112/plms/s3-65.3.604) Crossref, Web of Science, Google Scholar
12.
Fan AH, Lau KS, Ngai SM . 2000 Iterated function systems with overlaps. Asian J. Math. 4 , 527–552. (doi:10.4310/AJM.2000.v4.n3.a3) Crossref, Google Scholar
13.
Lau KS, Ngai SM, Rao H . 2001 Iterated function systems with overlaps and self-similar measures. J. Lond. Math. Soc. 63 , 99–116. (doi:10.1112/S0024610700001654) Crossref, Web of Science, Google Scholar
14.
Sidorov N . 2007 Combinatorics of linear iterated function systems with overlaps. Nonlinearity 20 , 1299–1312. (doi:10.1088/0951-7715/20/5/013) Crossref, Web of Science, Google Scholar
15.
Falconer KJ . 1986 Random fractals. In Mathematical proceedings of the cambridge philosophical society, pp. 559–582, vol. 100 . Cambridge, UK: Cambridge University Press. (doi:10.1017/S0305004100066299) Crossref, Google Scholar
16.
Hutchinson JE, Rüschendorf L . 2000 Self-similar fractals and self-similar random fractals. In Fractal geometry and stochastics II, pp. 109–123. Switzerland: Springer. (doi:10.1007/978-3-0348-8380-1_5) Crossref, Google Scholar
17.
Barnsley MF, Demko S . 1985 Iterated function systems and the global construction of fractals. Proc. R. Soc. Lond. A Math. Phys. Sci. 399 , 243–275. (doi:10.1098/rspa.1985.0057) Link, Web of Science, Google Scholar
18.
Feng DJ, Hu H . 2009 Dimension theory of iterated function systems. Commun. Pure. Appl. Math. 62 , 1435–1500. (doi:10.1002/cpa.20276) Crossref, Web of Science, Google Scholar
19.
Mihailescu E . 2022 Thermodynamic formalism for invariant measures in iterated function systems with overlaps. Commun. Contemp. Math. 24 , 2150041. (doi:10.1142/S0219199721500413) Crossref, Web of Science, Google Scholar
20.
Mihailescu E, Urbański M . 2022 Geometry of measures in random systems with complete connections. J. Geom. Anal. 32 , 162. (doi:10.1007/s12220-022-00899-y) Crossref, Web of Science, Google Scholar
21.
Pesin Y, Weiss H . 1996 On the dimension of deterministic and random Cantor-like sets, symbolic dynamics, and the Eckmann-Ruelle conjecture. Commun. Math. Phys. 182 , 105–153. (doi:10.1007/BF02506387) Crossref, Web of Science, Google Scholar
22.
Xi L, Wang L, Wang S, Yu Z, Wang Q . 2017 Fractality and scale-free effect of a class of self-similar networks. Phys. A 478 , 31–40. (doi:10.1016/j.physa.2017.02.049) Crossref, Web of Science, Google Scholar
23.
Li Z, Yu Z, Xi L . 2018 Scale-free effect of substitution networks. Phys. A 492 , 1449–1455. (doi:10.1016/j.physa.2017.11.072) Crossref, Web of Science, Google Scholar
24.
Li Z, Yao J, Wang Q . 2019 Fractality of multiple colored substitution networks. Phys. A 525 , 402–408. (doi:10.1016/j.physa.2019.03.079) Crossref, Web of Science, Google Scholar
25.
Xi L, Ye Q . 2019 Average distances on substitution trees. Phys. A 529 , 121556. (doi:10.1016/j.physa.2019.121556) Crossref, Web of Science, Google Scholar
26.
Ye Q, Xi L . 2019 Average distance of substitution networks. Fractals 27 , 1950097. (doi:10.1142/S0218348X1950097X) Crossref, Web of Science, Google Scholar
27.
Barnsley MF, Elton JH, Hardin DP . 1989 Recurrent iterated function systems. Constr. Approx. 5 , 3–31. (doi:10.1007/BF01889596) Crossref, Web of Science, Google Scholar
28.
Anttila R, Eriksson-Bique S . On constructions of fractal spaces using replacement and the combinatorial Loewner property. arXiv (doi:arXiv:2406.08062) Google Scholar
29.
Blumberg H . 1920 Hausdorff’s grundzüge der mengenlehre. Bull. Amer. Math. Soc. 27 , 116–129. (doi:10.1090/S0002-9904-1920-03378-1) Crossref, Google Scholar
30.
Gromov M . 1999 Metric structures for Riemannian and non-Riemannian spaces. progress in mathematics. vol. 152. Boston, MA: Birkhäuser Boston, Inc. Google Scholar
31.
Falconer KJ . 1989 Dimensions and measures of quasi self-similar sets. Proc. Am. Math. Soc. 106 , 543–554. (doi:10.2307/2048840) Crossref, Web of Science, Google Scholar
32.
Federer H . 1969 Geometric measure theory. Die grundlehren der mathematischen wissenschaften. New York, NY: Springer-Verlag. Google Scholar
33.
Rogers CA . 1998 Hausdorff measures. Cambridge, UK: Cambridge University Press. Google Scholar
34.
Tao T . 2012 Topics in random matrix theory. vol. 132. American Mathematical Society. Crossref, Google Scholar
35.
Bellman R . 1954 Limit theorems for non-commutative operations. I. Duke Math. J. 21 , 491–500. (doi:10.1215/S0012-7094-54-02148-1) Crossref, Web of Science, Google Scholar
36.
Furstenberg H, Kesten H . 1960 Products of random matrices. Ann. Math. Statist. 31 , 457–469. (doi:10.1214/aoms/1177705909) Crossref, Google Scholar
37.
Furstenberg H . 1963 Noncommuting random products. Trans. Am. Math. Soc. 108 , 377–428. (doi:10.2307/1993589) Crossref, Google Scholar
38.
Pollicott M . 2010 Maximal Lyapunov exponents for random matrix products. Invent. Math. 181 , 209–226. (doi:10.1007/s00222-010-0246-y) Crossref, Web of Science, Google Scholar
39.
Pollicott M . 2021 Effective estimates of Lyapunov exponents for random products of positive matrices. Nonlinearity 34 , 6705–6718. (doi:10.1088/1361-6544/ac15ac) Crossref, Web of Science, Google Scholar

This Issue

Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences cover image

October 2024

Volume 480Issue 2300

Article Information

DOI:https://doi.org/10.1098/rspa.2024.0406
Published by:Royal Society
Online ISSN:1471-2946

History:

Manuscript received28/05/2024
Manuscript accepted31/07/2024
Published online16/10/2024

License:

Citations and impact

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

Keywords

Subjects

Fractal dimensions for iterated graph systems

Abstract

1. Introduction and main results

(a) Introduction

(b) Main results

2. Deterministic iterated graph systems

(a) Minkowski dimension for graphs

(b) Deterministic iterated graph systems

(c) Relevant definitions

(d) Growth rates of arcs and vertices

3. Proof of theorem 2.1

(a) A combinatorial matrix problem

(b) Distance growth between vertices

(c) Proof of theorem 2.2

(d) Existence of the Gromov–Hausdorff scaling limit for iterated graph systems

(e) Proof of theorem 2.3

4. Random iterated graph systems and proof of theorem 4.1

(a) Random iterated graph systems

(b) Relevant definitions

(c) Lyapunov exponents and stochastic substitution systems

(d) Growths of arcs and vertices

(e) Proof of theorem 4.1

Data accessibility

Declaration of AI use

Authors’ contributions

Conflict of interest declaration

Funding

Acknowledgements

Footnotes

References

This Issue

Strictly Necessary Cookies

Functional Cookies

Performance Cookies

Targeting Cookies

Your password must have 8 characters or more and contain 3 of the following:

Fractal dimensions for iterated graph systems

Abstract

1. Introduction and main results

(a) Introduction

(b) Main results

2. Deterministic iterated graph systems

(a) Minkowski dimension for graphs

(b) Deterministic iterated graph systems

(c) Relevant definitions

(d) Growth rates of arcs and vertices

3. Proof of theorem 2.1

(a) A combinatorial matrix problem

(b) Distance growth between vertices

(c) Proof of theorem 2.2

(d) Existence of the Gromov–Hausdorff scaling limit for iterated graph systems

(e) Proof of theorem 2.3

4. Random iterated graph systems and proof of theorem 4.1

(a) Random iterated graph systems

(b) Relevant definitions

(c) Lyapunov exponents and stochastic substitution systems

(d) Growths of arcs and vertices

(e) Proof of theorem 4.1

Data accessibility

Declaration of AI use

Authors’ contributions

Conflict of interest declaration

Funding

Acknowledgements

Footnotes

This Issue