5
$\begingroup$

Consider a random $G(n,p)$ graph where $p=\omega(\frac 1n)$, and let $x$ denote the probability that the graph has a connected component of size linear in $n$.

It is well known that $x$ tends to $1$ as $n\to \infty$, even if $p\geq \frac {1+\epsilon}{n}$. However, I am looking for a more exact statement: Something of the form $$x\geq 1-O(f(n,p))$$ where $f$ is some small function of $n$ and $p$.

I'm sure that a reference exists somewhere, but I have yet to find it.

Thanks!

$\endgroup$
4
$\begingroup$

In "On tree census and the giant component in sparse random graphs, B. Pittel proves the following (see Gap Theorem and Lemma 4): for $c>1,$ any $a>0$ and any $\omega \to \infty$ however slowly, \begin{equation*} P(|\# \text{ of vertices in largest component}-\theta n |> \omega \sqrt{ n \ln n})\leq n^{-a}, \end{equation*} where $\theta$ is the unique positive root of $1-\theta = e^{-c \theta}$. So definitely you can choose $f(n,p)=n^{-a}$ for whichever $a>0$ you want. I imagine that one can mimic the proof to get a better bound when $np \to \infty$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.