Graph Processes Modelled as Dynamical Systems on Banach Spaces

We consider the following broad class of graph processes called flip processes. Given a large graph $G$, we sample an ordered $k$-tuple of vertices uniformly at random and replace the induced subgraph with another graph on $k$ vertices according to a predetermined---possibly randomized---rule. This rule can be described by a transition matrix on the set of all labelled graphs on $k$ vertices, where each entry specifies the probability of replacing a particular sampled subgraph with a particular replacement graph. Our aim is to model the evolution of such processes.

In the early 2000s, Borgs, Chayes, Lovász, Sós, Szegedy, and Vesztergombi initiated a limit theory for dense graphs, leading to the introduction of graphons: symmetric measurable functions $W:[0,1]^2\rightarrow[0,1]$ which, equipped with the graph-theoretically motivated cut norm, form a complete metric space.