Random graph $G(n,p(n))$ and graph $H$, which shown below, are given.
I'm in need to find $f(x) : f(x) > 0$, such as:
- if $lim_{n \to \infty}p(n)f(n) = 0$, then asymptotically almost surely G don't contain subgraph, isomorphic to $H$
- $lim_{n \to \infty}p(n)f(n) = \infty$, then asymptotically almost surely G contains subgraph, isomorphic to $H$
Thank you for your suggestions.
I don't know if I really understood the question, so tell me what you think about this "solution". (If you already have one, please, let me know!)
Fix 6 vertices and put on them an order (label them). Suppose the first six vertices $\{1,2,..,6\}$. Then, the probability that exists a subgraph isomorphic to $H$ using these 6 vertices is bounded by $6!p^7$. You force the seven connections and permute theirs labels.
So, $P( \exists H \subset G(n,p(n)) \le 6!\binom{n}{6}p(n)^7$. Here you get a candidate to $f(n)$. Take $f(n)=6!\binom{n}{6}p(n)^6$ and you have that $\lim_n f(n)p(n) = 0$ implies $G(n,p(n))$ doesn't have a $H$ a.a.s.
On the other hand, put again the vertices in order and force the existence of a $H$ using only 6 disjoint vertices. I mean, form $\lfloor \frac{n}{6} \rfloor$ sets of 6 vertices. Then $P( \exists H \subset G(n,p(n)) \ge \lfloor \frac{n}{6} \rfloor p(n)^7$. And now, take $f(n) = \frac{1}{p(n)(\lfloor \frac{n}{6} \rfloor p(n)^7 -1)}$.
And then you get $\lim_n f(n)p(n) = \infty$ implies $G(n,p(n))$ has a $H$ a.a.s.