From flip processes to dynamical systems on graphons

MaRDI QIDQ6389500zbMATH OpenFDO

Authors Frederik Garbe, Jan Hladký, M. Şileikis, Fiona Skerman

Publication date 28 January 2022

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 a function $mathcalR:mathcal{H}_{k}ightarrowmathcal{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 $mathcalR(F)$. This class contains several previously studied processes including the ErdH{o}s--R'enyi random graph process and the triangle removal process. Actually, our definition of flip processes is more general, in that $mathcalR(F)$ is a probability distribution on $mathcal{H}_k$, thus allowing randomised replacements. Given a flip process with a rule $mathcalR$, we construct time-indexed trajectories $Phi:mathcal{W}_{0}imes[0,infty)ightarrowmathcal{W}_0$ 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 topics, we study continuity properties of these trajectories with respect to time and 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 page was built for publication: From flip processes to dynamical systems on graphons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6389500)