Let $G(n,p)$ denote the Erdős–Rényi model 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.



For what range of edge probability does the following property hold for random graphs?
For every $v$, we have $|N(v)|\approx np$ (I assume $p$ is not very small so the fluctuations are small enough to ignore). You want two of these such that $N(x)\cap N(y)=\{v\}$, or in other words, if you now forget about $v$ itself, you want these two sets to be disjoint.


For any specific $x$ and $y$ the probability of this is roughly $(1-p^2)^n \approx e^{-np^2}$. If we take $p=\sqrt{\alpha \log n / n}$ then we get $n^{-\alpha}$. There are $np/2$ disjoint pairs of vertices in $N(v)$ and the choices are independent (well, almost, I'll leave it for you to sort it out). Hence, the probability of not seeing such a pair is bounded by
$$(1-n^{-\alpha})^{np/2}\approx e^{-n^{1-\alpha}p/2}=e^{-n^{\frac12-\alpha}\sqrt{\alpha \log n}}$$.


Taking $\alpha<\frac12$ we get that the failure probability is less than polynomially small, and then union bound over all $v$ is enough.


If I had to bet, I'd say the right $\alpha$ is 1, but I don't have to bet.


What is the motivation for the question, if I may ask?


