4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.