The Mathematics

Definition

A finite set of maps T₁, ... T_d from a finite set V onto itself defines a finite simple graph G=(V,E), where E={ (x,y) | x ≠ y, exists k such that T_k x=y }.

Why look at them?

These dynamical graphs show interesting structures and bring arithmetic structures to live.
Their statistical properties of path length, global cluster and vertex degree are interesting.
Some examples lead to deterministic small world examples with small diameter and large cluster.
The graphs display rich-club phenomena, where high degree nodes are more interconnected.
They feature garden of eden states, unreachable configurations like transient trees.
They can feature attractors like cycle sub graphs but also more complex structures.
By definition, these graphs are factors of Cayley graphs on the permutation group of V.
While arithmetic graphs are the focus they are universal: any finite simple graph is obtained.

Examples:

V is a ring and T_k are polynomials. For example, if T₁(x) = x² + a and T₂(x) = x² + b.
If V is a group and T_i x = a_i x, then G is the Cayley graph of the finite presentation of V.
if V is the group Z_n T₁x=x² and T₂ x = x³ then the graph G is connected if and only if n is a Pierpont prime, a prime of the form 2^t 3^u+1.

Deterministic Small world

Deterministic rewiring:


n=20, k=2	n=20, k=4	n=200, k=4