# 3/22/2022 – Combinatorics, Physics and Probability Seminar

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).