Let $G \sim G_{n,p}$ be a binomial random graph and consider a sequence of graphs $\{H_n\}_n$. When $|H_n|=\mathcal{O}(1)$, then one knows the exact threshold $p_0$ for embeddabiliy of $H_n$ in $G$.

When $|H_n|\geq (1-o(1))n$, however, no general results are known, but only special cases (matchings, packings, Hamilton cycles).

I wonder what happens in between: Say for example that $|H_n|=\Theta(n)$ or $|H_n|=\log n$. Do we know the exact threshold for all such graphs of this size or only for special graphs $H_n$?

I would appreciate any information, link or even a "name" of the problem. Thank you very much.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.