0558489 - ÚI 2023 US eng V - Research Report
Campos Araújo, Pedro - Hladký, Jan - Hng, Eng Keat - Šileikis, Matas
Prominent examples of flip processes.
Cornell University, 2022. 39 s. arXiv.org e-Print archive, arXiv:2206.03884.
R&D Projects: GA ČR(CZ) GX21-21762X; GA ČR(CZ) GJ20-27757Y
Institutional support: RVO:67985807
Result website:
https://arxiv.org/abs/2206.03884DOI: https://doi.org/10.48550/arXiv.2206.03884

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:Hk→Hk from all labelled graphs of a fixed order k into itself. The process starts with an arbitrary given n-vertex graph G0. In each step, the graph Gi is obtained by sampling k random vertices v1,…,vk of Gi−1 and replacing the induced graph Gi−1[v1,…,vk] by R(Gi−1[v1,…,vk]). 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: http://hdl.handle.net/11104/0332132