Flip processes on finite graphs and dynamical systems they induce on graphons

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). Now, 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 $G_{i-1}[v_1,\ldots,v_k]$ by $\mathcal{R}(G_{i-1}[v_1,\ldots,v_k])$. This class contains several previously studied processes including the Erdos-Renyi random graph process and the random triangle removal.

Given a flip processes with a rule $\mathcal{R}$ we construct time-indexed trajectories $\Phi:\mathcal{W}\times [0,\infty)\rightarrow\mathcal{W}$ in the space of graphons. We prove that with high probability, starting with a large finite graph $G_0$ which is close to a graphon $W_0$ in the cut norm distance, the flip process will stay in a thin sausage around the trajectory $(\Phi(W_0,t))_{t=0}^\infty$ (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. We prove that two trajectories cannot form a confluence, give an example of a process with an oscilatory trajectory, and address the question of existence and stability of fixed points and periodic trajectories.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).