Flip processes

03/22/2022 9:30 am - 10:30 am

Abstract: We introduce a class of random graph processes, which we call \emph{flip processes}. Each such process is given by a \emph{rule} which is just a function $\mathcal{R}:\mathcal{H}_k\rightarrow \mathcal{H}_k$ from all labelled $k$-vertex graphs into itself ($k$ is fixed). The process starts with a given $n$-vertex graph $G_0$. In each step, the graph $G_i$ is obtained by sampling $k$ random vertices $v_1,\ldots,v_k$ of $G_{i-1}$ and replacing the induced graph $F:=G_{i-1}[v_1,\ldots,v_k]$ by  $\mathcal{R}(F)$. This class contains several previously studied processes including the Erd\H{o}s–R\’enyi random graph process and the triangle removal process.

Given a flip process with a rule $\mathcal{R}$, we construct time-indexed trajectories $\Phi:\Gra\times [0,\infty)\rightarrow\Gra$ in the space of graphons. We prove that for any $T > 0$ starting with a large finite graph $G_0$ which is close to a graphon $W_0$ in the cut norm, with high probability the flip process will stay in a thin sausage around the trajectory $(\Phi(W_0,t))_{t=0}^T$ (after rescaling the time by the square of the order of the graph).

These graphon trajectories are then studied from the perspective of dynamical systems. Among others, we study continuity properties of these trajectories with respect to time and the initial graphon, existence and stability of fixed points and speed of convergence (whenever the infinite time limit exists). We give an example of a flip process with a periodic trajectory. This is joint work with Frederik Garbe, Matas \v Sileikis and Fiona Skerman (arXiv:2201.12272).

We also study several specific families flip processes. This is joint work with Pedro Ara\’ujo, Eng Keat Hng and Matas \v{S}ileikis (in preparation).
A brief introduction to the necessary bits of the theory of graph limits will be given in the talk.