1
$\begingroup$

In "Sharp threshold phenomena in statistical physics", H. Duminil-Copin, Japanese J. of Math. 14, 2019, a sharp transition of a boolean function is defined as follows:

A sequence of increasing boolean functions $(\mathbf{f_n})$ undergoes a sharp threshold at $(p_n)$ if there exists a $(\delta_n)$ tending to 0 such that $f_n(p_n - \delta_n) \to 0$ and $f_n(p_n + \delta_n) \to 1$.

An example is $p_n = 1/n$, for the indicator $f=\mathbb{1}_{\text{giant component}}$ of the random graph.

What if I write $p_n = n^{-c}$, for $c<1$ and $c>1$, and consider this the threshold point for $\mathbb{1}_{\text{giant component}}$? Have I followed the correct definition of a sharp threshold above? That is, if I show that the limit of the indicator $\mathbb{1}_{\text{giant component}}$ is either 0 or 1 for $c<1$ or $c>1$, have completed an equivalent task to the above definition?

How are these two formulations (the adding $\delta_n$ method and the use of a power $c$) of the threshold related? Perhaps, I can write $f(n^{-c}) = f(n^{-1} ± \Delta_n(c))$, and find the corresponding sequence $(\Delta_n(c))$, and therefore show the two limits above are 0 or 1?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

The parameters $p_n$ are not arbitrary numerical parameters. They represent the expectation of one binary variable in a product space. Changing them additively is very different from changing the power in the expression $n^{-c}$.

I believe definition 1.1 in the cited paper has a typo, and for $p_n$ tending to 0, we should require $\delta_n/p_n \to 0$ for a sharp threshold, and not just $\delta_n \to 0$. That is the requirement in the key papers that consider $p_n \to 0$, e.g. [1].

For the Erdos-Renyi graph $G(n,p)$ and a fixed vertex $v$, consider the property $$A_n:=\{\, \text{deg} (v) \ge 1\,\}.$$ Then $A_n$ is an increasing property, and $$f_n(p)=P_p(A_n)=1-(1-p)^{n-1}$$ satisfies $$\lim_n f_n(c/n) =1-e^{-c}$$ so it definitely does not satisfy the definition of sharp threshold that requires $\delta_n/p_n \to 0$ (i.e. given that definition of "sharp", since small changes in $c$ don't have the required effect). However, $\lim_n f_n(n^{-c})=0$ for $c>1$ and $\lim_n f_n(n^{-c})=1$ for $c<1$.

[1] Friedgut, Ehud, and Jean Bourgain. "Sharp thresholds of graph properties, and the 𝑘-sat problem." Journal of the American mathematical Society 12, no. 4 (1999): 1017-1054.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What explicitly are $p_n$ and $\delta_n$ in this case of $A_n$ (i.e. that a vertex is not isolated)? With $f_{n}(c/n)$, can I instead write the equivalent $f_{n}(1/n + (c-1)/n)$, so that $p_n = 1/n$ and $\delta_n = (c-1)/n$? But, then we have $\delta_n / p_n = c-1$, which is not going to zero with $n$. Unless c=1. $\endgroup$
    – apg
    Commented Jul 22, 2022 at 21:19
  • $\begingroup$ i.e. c=1 is the only case where $\delta_n / p_n$ would need to go to zero with $n$, so the condition is indeed satisfied. Overall, I need to evaluate the width of the critical window to prove we have a sharp transition, not just that you can go arbitrarily close to the transition point from either side, and keep the zero/one nature of the order parameter. I think that's what is meant by the condition $\delta_n / p_n \to 0$ which you clarify. $\endgroup$
    – apg
    Commented Jul 22, 2022 at 21:48
  • 1
    $\begingroup$ Exactly, this $A_n$ is an example of a local event that does not have a sharp threshold. $\endgroup$
    – Yuval Peres
    Commented Jul 22, 2022 at 23:49
  • $\begingroup$ Also, just to clarify something, since every monotone graph property has a sharp threshold, does that mean $A_n$ is not a monotone graph property (since there is no sharp threshold)? It would seem $A_n$ was monotone, as adding edges can only preserve the non-isolated nature of a vertex. Perhaps I am missing something about the definition of monotone property. $\endgroup$
    – apg
    Commented Jul 23, 2022 at 0:30
  • 1
    $\begingroup$ The theorem "every monotone graph property has a sharp threshold" is describing a weaker type of sharp threshold, where one just requires $\delta_n \to 0$. This is appropriate when $p_n$ are bounded away from 0 and 1. $\endgroup$
    – Yuval Peres
    Commented Jul 23, 2022 at 1:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .