اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNucleation scaling in jigsaw percolation
108
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Jigsaw percolation is a nonlocal process that iteratively merges connected clusters in a deterministic puzzle graph by using connectivity properties of a random people graph on the same set of vertices. We presume the Erdos--Renyi people graph with edge probability p and investigate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. In some generality, for puzzle graphs with N vertices of degrees about D (in the appropriate sense), this probability is close to 1 or small depending on whether pD(log N) is large or small. The one dimensional ring and two dimensional torus puzzles are studied in more detail and in many cases the exact scaling of the critical probability is obtained. The paper settles several conjectures posed by Brummitt, Chatterjee, Dey, and Sivakoff who introduced this model.
قيم البحث
اقرأ أيضاً
We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are `jointly connected. Bollobas, Riordan, Slivken and Smith proved that when the two graphs are independent binomial random graphs
, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $Thetaleft( frac{1}{nln n} right)$. We show that this threshold is sharp, and that it lies at $frac{1}{4nln n}$.
In bootstrap percolation it is known that the critical percolation threshold tends to converge slowly to zero with increasing system size, or, inversely, the critical size diverges fast when the percolation probability goes to zero. To obtain higher-
order terms (that is, sharp and sharper thresholds) for the percolation threshold in general is a hard question. In the case of two-dimensional anisotropic models, sometimes correction terms can be obtained from inversion in a relatively simple manner.
We consider two-dimensional dependent dynamical site percolation where sites perform majority dynamics. We introduce the critical percolation function at time t as the infimum density with which one needs to begin in order to obtain an infinite open
component at time t. We prove that, for any fixed time t, there is no percolation at criticality and that the critical percolation function is continuous. We also prove that, for any positive time, the percolation threshold is strictly smaller than the critical probability for independent site percolation.
We consider a dynamical process on a graph $G$, in which vertices are infected (randomly) at a rate which depends on the number of their neighbours that are already infected. This model includes bootstrap percolation and first-passage percolation as
its extreme points. We give a precise description of the evolution of this process on the graph $mathbb{Z}^2$, significantly sharpening results of Dehghanpour and Schonmann. In particular, we determine the typical infection time up to a constant factor for almost all natural values of the parameters, and in a large range we obtain a stronger, sharp threshold.
The existence (or not) of infinite clusters is explored for two stochastic models of intersecting line segments in $d ge 2$ dimensions. Salient features of the phase diagram are established in each case. The models are based on site percolation on ${
mathbb Z}^d$ with parameter $pin (0,1]$. For each occupied site $v$, and for each of the $2d$ possible coordinate directions, declare the entire line segment from $v$ to the next occupied site in the given direction to be either blue or not blue according to a given stochastic rule. In the one-choice model, each occupied site declares one of its $2d$ incident segments to be blue. In the independent model, the states of different line segments are independent.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
