Existence of threshold functions for monotone graph properties

Let $G_{n,p,d}$ denote the class of $d$-dependent random graph distributions on graphs with $n$ vertices and marginal edge probability $p$. Let $d4ab$ be a monotone graph property, and suppose $d=O(n/\ln(n))$. For functions $L(n,d)$ and $U(n,d)$, write $p\ll L(n,d)$ when $p/L(n,d)\to 0$ and $p\gg U(n,d)$ when $p/U(n,d)\to\infty$. Existence of threshold functions. For every monotone graph property $\mathcal{P}$ and all $d=O(n/\ln(n))$, there exist functions $L(n,d)$ and $U(n,d)$ such that: (i) if $p\ll L(n,d)$, then every $d$-dependent random graph distribution $G\sim G_{n,p,d}$ almost surely does not have property $\mathcal{P}$; (ii) if $p\gg U(n,d)$, then every such $G$ almost surely has property $\mathcal{P}$; and (iii) if $L(n,d)\ll p\ll U(n,d)$, then there exist $d$-dependent random graph distributions $H_1$ and $H_2$ such that $H_1$ almost surely has property $\mathcal{P}$ and $H_2$ almost surely does not have property $\mathcal{P}$. This proposes lower and upper thresholds that capture the range of behavior possible under local dependence, in contrast with the tight thresholds of the Erdős–Rényi model. The source presents it as an open question, and the stated parser status is unknown.