Dynamical Systems seminar - Fractal dimensions for random substitution graph systems

Speaker: Ziyu (Nero) Li (Imperial College London)

Abstract: This work aims to introduce fractal geometry into graph theory. To do this, we present substitution graph systems and define box-counting dimension, Hausdorff dimension and especially degree dimension for graphs.
 
With the definitions, we prove that random substitution graph systems almost surely satisfy fractality and scale-freeness. Moreover, in deterministic cases, the associated box-counting and degree dimensions are analytically derived. For random ones, we obtain box-counting and degree dimensions numerically by the Lyapunov exponents.

In particular, Hausdorff and box-counting dimensions are proven to be consistent regarding substitution graph systems.
 
The random substitution graph systems turn out to be a simple, powerful and promising model either to theoretically study fractal graphs or to generate random fractal-like and scale-free networks.