10
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ You really want to use $p$ and $q$ for vertices, in a question dealing with probability? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Oct 19, 2011 at 17:57
  • $\begingroup$ Ori, you're right, that was a poor choice of notation --- I changed it. $\endgroup$
    – Matthew Kahle
    Commented Oct 19, 2011 at 19:58
  • $\begingroup$ Under the parameterization for $p$ in Ori Gurel-Gurevich's answer the expected number of pairs of vertices having $|N(x) \cap N(y)|=1$ is $\binom{n}{2} (np^2(1-p^2)^{n-2}) \approx \alpha/2 \log n n^{2-\alpha}$. If $\alpha>1$ there aren't enough such pairs to cover every $v$, while if $\alpha<1$ there's plenty. One (perhaps overly optimistic) hypothesis might be that near the threshold the "targets" for each such pair might be nearly independent, and the threshold behavior would be like that of the coupon collector problem with $n^3/2 p^2 (1-p^2)^n$ coupons. $\endgroup$
    – Kevin P. Costello
    Commented Oct 19, 2011 at 23:23
  • $\begingroup$ I'm not confident this condition is likely for any $p=p(n)$. As random edges are added one at a time, for each $v$ there will probably be some interval of time (or several intervals) when it is the unique common neighbour of two of its neighbours, but I don't know why these intervals should overlap. $\endgroup$
    – Brendan McKay
    Commented Oct 20, 2011 at 9:26
  • $\begingroup$ After some simulations, I think there is indeed a range of $p$ values for which most graphs have the desired property. $\endgroup$
    – Brendan McKay
    Commented Oct 20, 2011 at 11:03

1 Answer 1

Reset to default
7
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ori, all I can say in a few words re: motivation is that this graph parameter bounds another one that I'm actually interested in. I thought about it a bit more, and decided that you're right, $\alpha=1$ is the right answer. Rather than finding disjoint pairs of vertices, we can use all the pairs since most pairs are independent -- extended Janson inequality makes it work... $\endgroup$
    – Matthew Kahle
    Commented Oct 20, 2011 at 20:50
  • $\begingroup$ Indeed, that was the reason why I thought $\alpha=$ is right. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Oct 21, 2011 at 2:16

You must log in to answer this question.

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