Let $G(n,p)$ denote the [Erdős–Rényi model][1] of random graph. For a given function $p = p(n)$ we say that $G \in G(n,p)$ asymptotically almost surely has property $\mathcal{P}$ if $$\mbox{Pr}[G \mbox{ has property } \mathcal{P}] \to 1 $$ as $n \to \infty$.

The property $\mathcal{P}$ I am interested in is the following:

For every vertex $v$ there exist vertices $p,q$ such that $N(p) \cap N(q) = v$. (Here $N(x)$ denote the set of neighbors of $x$.)

Note that this is not a monotone graph property. For random graphs it is fairly clear that $\mathcal{P}$ does not hold once $$p \ge \left( \frac{2 \log n + C \log \log n }{n} \right)^{1/2} ,$$ for some large enough constant $C>0$ for example, because at that point, every pair $p,q$ has large neighborhood intersection $N(p) \cap N(q)$.

On the other hand, the property also does not hold for small $p$. In particular if $$p \le \frac{\log n - \omega}{n}$$ where $\omega \to \infty$, then $G(n,p)$ has isolated vertices $v$.

My guess is that $\mathcal{P}$ a.a.s. holds nearly the whole way between the thresholds for the monotone properties "minimum-degree-$2$", at about $$p = \frac{\log n + \log \log n }{n}, $$ and "for every pair $p,q$, $N(p) \cap N(q) \neq 0$" given above.

I am more interested in the upper threshold. So the question I would most like to hear the answer to is

What is the largest function $p = > p(n)$ we can write down so that $G \in > G(n,p)$ a.a.s. has property $\mathcal{P}$?

I am also interested in how sharp this upper threshold is, and in particular whether the threshold is sharp in the sense of Friedgut and Kalai.

Finally, we could call this property $\mathcal{P}_2$ since it is about intersecting pairs of neighborhoods, and say that a graph has property $\mathcal{P}_k$ if for every $v$ there exist $p_1, p_2, \dots, p_k$ such that $$\bigcap_i N(p_i) = v,$$ and I'm also interested in this more general setting. [1]: http://en.wikipedia.org/wiki/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model$\mathcal{P}$?

Let $G(n,p)$ denote the [Erdős–Rényi model][1] of random graph. For a given function $p = p(n)$ we say that $G \in G(n,p)$ asymptotically almost surely has property $\mathcal{P}$ if $$\mbox{Pr}[G \mbox{ has property } \mathcal{P}] \to 1 $$ as $n \to \infty$.

The property $\mathcal{P}$ I am interested in is the following:

For every vertex $v$ there exist vertices $x, y$ such that $N(x) \cap N(y) = v$. (Here $N(x)$ denote the set of neighbors of $x$.)

Note that this is not a monotone graph property. For random graphs it is fairly clear that $\mathcal{P}$ does not hold once $$p \ge \left( \frac{2 \log n + C \log \log n }{n} \right)^{1/2} ,$$ for some large enough constant $C>0$ for example, because at that point, every pair $x,y$ has large neighborhood intersection $N(x) \cap N(y)$.

On the other hand, the property also does not hold for small $p$. In particular if $$p \le \frac{\log n - \omega}{n}$$ where $\omega \to \infty$, then $G(n,p)$ has isolated vertices $v$.

My guess is that $\mathcal{P}$ a.a.s. holds for most of the way between the thresholds for the monotone properties "minimum-degree-$2$", at about $$p = \frac{\log n + \log \log n }{n}, $$ and "for every pair $x, y$, $N(x) \cap N(y) \neq 0$" given above.

I am more interested in the upper threshold. So the question I would most like to hear the answer to is:

What is the largest function $p = > p(n)$ such that $G \in > G(n,p)$ a.a.s. has property $\mathcal{P}$?

I am also interested in how sharp this upper threshold is, and in particular whether the threshold is sharp in the sense of Friedgut and Kalai.

Finally, we could call this property $\mathcal{P}_2$ since it is about intersecting pairs of neighborhoods, and say that a graph has property $\mathcal{P}_k$ if for every $v$ there exist $x_1, x_2, \dots, x_k$ such that $$\bigcap_i N(x_i) = v,$$ and I'm also interested in this more general setting. [1]: http://en.wikipedia.org/wiki/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model$\mathcal{P}$?