Skip to main content
Added clarity over what "requries" means here.
Source Link

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.

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$. 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.

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.

Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

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$. 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.