Prominent examples of flip processes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913577459253248 |
|---|---|
| author | Araújo, Pedro Hladký, Jan Hng, Eng Keat Šileikis, Matas |
| author_facet | Araújo, Pedro Hladký, Jan Hng, Eng Keat Šileikis, Matas |
| contents | 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 $\mathcal{R}:\mathcal{H}_k\rightarrow \mathcal{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,\ldots,v_k$ of $G_{i-1}$ and replacing the induced graph $G_{i-1}[v_1,\ldots,v_k]$ by $\mathcal{R}(G_{i-1}[v_1,\ldots,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 $\mathcal{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 $\mathcal{R}(H)$ does not depend on $H$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_03884 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Prominent examples of flip processes Araújo, Pedro Hladký, Jan Hng, Eng Keat Šileikis, Matas Combinatorics Probability 05C80 G.2.2 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 $\mathcal{R}:\mathcal{H}_k\rightarrow \mathcal{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,\ldots,v_k$ of $G_{i-1}$ and replacing the induced graph $G_{i-1}[v_1,\ldots,v_k]$ by $\mathcal{R}(G_{i-1}[v_1,\ldots,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 $\mathcal{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 $\mathcal{R}(H)$ does not depend on $H$. |
| title | Prominent examples of flip processes |
| topic | Combinatorics Probability 05C80 G.2.2 |
| url | https://arxiv.org/abs/2206.03884 |