Number of the records: 1
Prominent examples of flip processes
- 1.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: 0.9, year: 2023
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
Number of the records: 1