From flip processes to dynamical systems on graphons

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F24%3A00581049" target="_blank" >RIV/67985840:_____/24:00581049 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/67985807:_____/24:00581049 RIV/00216224:14330/24:00139103

Výsledek na webu

<a href="https://doi.org/10.1214/23-AIHP1405" target="_blank" >https://doi.org/10.1214/23-AIHP1405</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1214/23-AIHP1405" target="_blank" >10.1214/23-AIHP1405</a>

Jazyk výsledku

angličtina

Název v původním jazyce

From flip processes to dynamical systems on graphons

Popis výsledku v původním jazyce

We introduce a class of random graph processes, which we call flip processes. Each such process is given by a rule which is a function R:H(k)→H(k) from all labeled 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,…,v_k of G(i−1) and replacing the induced graph F:=G(i−1)[v_1,…,v_k] by R(F). This class contains several previously studied processes including the Erdős-Ré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 H(k), thus allowing randomised replacements. Given a flip process with a rule R, we construct time-indexed trajectories Φ:W×[0,∞)→W in the space W of graphons. We prove that for any T>0 starting with a large finite graph G(0) which is close to a graphon U in the cut norm, with high probability the flip process will stay in a thin sausage around the trajectory Φ(U,t) for 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.

Název v anglickém jazyce

From flip processes to dynamical systems on graphons

Popis výsledku anglicky

We introduce a class of random graph processes, which we call flip processes. Each such process is given by a rule which is a function R:H(k)→H(k) from all labeled 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,…,v_k of G(i−1) and replacing the induced graph F:=G(i−1)[v_1,…,v_k] by R(F). This class contains several previously studied processes including the Erdős-Ré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 H(k), thus allowing randomised replacements. Given a flip process with a rule R, we construct time-indexed trajectories Φ:W×[0,∞)→W in the space W of graphons. We prove that for any T>0 starting with a large finite graph G(0) which is close to a graphon U in the cut norm, with high probability the flip process will stay in a thin sausage around the trajectory Φ(U,t) for 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Annales de L Institut Henri Poincare-Probabilites Et Statistiques

ISSN

0246-0203

e-ISSN

—

Svazek periodika

60

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

45

Strana od-do

2878-2922

Kód UT WoS článku

001364407800018

EID výsledku v databázi Scopus

2-s2.0-85211340202