Prominent examples of flip processes

DOI10.1002/RSA.21192MaRDI QIDQ6201039zbMATH OpenOpenAlexFDO

Authors Pedro Araújo, Jan Hladký, Eng Keat Hng, M. Şileikis

Publication date 25 March 2024

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2206.03884

zbMATH Keywords

differential equationgraph limitrandom graph processesgraph process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Flip processes, introduced in [Garbe, Hladk'y, v{S}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 $mathcalR:mathcal{H}_{k}ightarrowmathcal{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 $mathcalR(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 $mathcalR(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 $mathcalR(H)$ does not depend on $H$.

Recommendations

• From flip processes to dynamical systems on graphons
• Edge flipping in graphs
• Edge flipping in the complete graph
• Front propagation in flipping processes

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• A limit theorem for small cliques in inhomogeneous random graphs
• A new proof of the graph removal lemma
• Achlioptas process phase transitions are continuous
• Asymptotic behavior of the chromatic index for hypergraphs
• Asymptotic packing via a branching process
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Dynamic concentration of the triangle‐free process
• Explosive percolation in random networks
• Graph Theory and Additive Combinatorics
• Large networks and graph limits
• Limits of dense graph sequences
• Nonlinear dispersive equations. Local and global analysis
• On a packing and covering problem
• Random maximalH-free graphs
• Random triangle removal
• Szemerédi's lemma for the analyst
• Testing subgraphs in large graphs
• The C_ℓ‐free process
• The early evolution of the \(H\)-free process
• The evolution of subcritical Achlioptas processes
• The triangle-free process and the Ramsey number \(R(3,k)\)
• To Prove and Conjecture: Paul Erdos and His Mathematics

Cited in

(2)

• Characterization of flip process rules with the same trajectories
• From flip processes to dynamical systems on graphons

This page was built for publication: Prominent examples of flip processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201039)