From flip processes to dynamical systems on graphons

Result code in 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>

Alternative codes found

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

Result on the web

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

Result language

angličtina

Original language name

From flip processes to dynamical systems on graphons

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Name of the periodical

Annales de L Institut Henri Poincare-Probabilites Et Statistiques

ISSN

0246-0203

e-ISSN

—

Volume of the periodical

60

Issue of the periodical within the volume

4

Country of publishing house

US - UNITED STATES

Number of pages

45

Pages from-to

2878-2922

UT code for WoS article

001364407800018

EID of the result in the Scopus database

2-s2.0-85211340202