Prominent examples of flip processes

0579756 - ÚI 2025 RIV US eng J - Journal Article
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
R&D Projects: GA ČR(CZ) GX21-21762X; GA ČR(CZ) GJ20-27757Y
Institutional support: RVO:67985807
Keywords : differential equation * graph limit * graph process * random graph processes
OECD category: Pure mathematics
Impact factor: 1, year: 2022
Method of publishing: 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.
Permanent Link: https://hdl.handle.net/11104/0348552