From flip processes to dynamical systems on graphons
| Authors | |
|---|---|
| Year of publication | 2024 |
| Type | Article in Periodical |
| Magazine / Source | Annales de l'Institut Henri Poincaré, Probabilités et Statistiques |
| MU Faculty or unit | |
| Citation | |
| web | https://doi.org/10.1214/23-AIHP1405 |
| Doi | http://dx.doi.org/10.1214/23-AIHP1405 |
| Keywords | Random graph processes; Evolving networks; Graph limits |
| Description |
We introduce a class of random graph processes, which we call flip processes. Each such process is given by a function R : H-k -> 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),& mldr;,v(k) of G(i-1) and replacing the induced graph F:=G(i-1)[v(1),& mldr;,v(k)] by R(F). This class contains several previously studied processes including the Erd & odblac;s--R & eacute;nyi random graph process and the triangle removal process. Actually, our definition of flip processes is more general, in that R(F) is a probability distribution on Hk, thus allowing randomised replacements. Given a flip process with a rule R, we construct time-indexed trajectories Phi:W(0)x[0,infinity)-> W0 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. |
| Related projects: |