Critical behavior of two-choice rules: a class of Achlioptas processes

arXiv2305.05837MaRDI QIDQ6436022FDOQ6436022

Publication date: 9 May 2023

Abstract: Achlioptas processes are a class of dynamically grown random graphs where on each step several edges are chosen at random but only one is added. The sum rule, product rule, and bounded size rules have been extensively studied. Here we introduce a new collection of rules called two-choice rules. In these systems one first pick

m

vertices at random from the graph and chooses a vertex

v

according to some rule based on their cluster sizes. The procedure is then repeated with a second independent sample to pick a vertex

v^{'}

and we add an edge from

v

and

v^{'}

. These systems are tractable because the cluster size distribution satisfies an analog of the Smoluchowski equation. We study the critical exponents associated with the phase transitions in five of these models. In contrast to the situation for

d

-dimensional percolation we show that all of the critical exponents can be computed if we know

, the exponent associated with the size of the giant component. When

all the critical exponents are the same as for the ER graph.

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35)

This page was built for publication: Critical behavior of two-choice rules: a class of Achlioptas processes

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