Prominent examples of flip processes

0579756 - ÚI 2025 RIV US eng J - Článek v odborném periodiku
Campos Araújo, Pedro - Hladký, Jan - Hng, Eng Keat - Šileikis, Matas
Prominent examples of flip processes.
Random Structures and Algorithms. Roč. 64, č. 3 (2024), s. 692-740. ISSN 1042-9832. E-ISSN 1098-2418
Grant CEP: GA ČR(CZ) GX21-21762X; GA ČR(CZ) GJ20-27757Y
Institucionální podpora: RVO:67985807
Klíčová slova: differential equation * graph limit * graph process * random graph processes
Obor OECD: Pure mathematics
Impakt faktor: 1, rok: 2022
Způsob publikování: Open access
https://doi.org/10.1002/rsa.21192

Flip processes, introduced in [Garbe, Hladký, Šileikis, Skerman: From flip processes to dynamical systems on graphons], are a class of random graph processes defined using a rule which is just a function R : H_k -> H_k from all labelled graphs of a fixed order k into itself. The process starts with an arbitrary 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 G_{i-1}[v_1, ... ,v_k] by R(G_{i-1}[v_1, ... ,v_k]). Using the formalism of dynamical systems on graphons associated to each such flip process from ibid. we study several specific flip processes, including the triangle removal flip process and its generalizations, 'extremist flip processes' (in which R(H) is either a clique or an independent set, depending on whether e(H) has less or more than half of all potential edges), and 'ignorant flip processes' in which the output R(H) does not depend on H.
Trvalý link: https://hdl.handle.net/11104/0348552