3
$\begingroup$

I am working with $G_{n,p}$ random graphs. Let $p$ (the probability of an edge) be $c/n$, so $c$ is the expected number of neighbors for a vertex when $n$ is large.

Now let $N$ be the number of components with more edges than vertices in the graph. I am trying to find the largest $c$ such that $\mathbb{E}(N)$ tends to zero as $n$ grows large.

$\mathbb{E}(N) = \sum_{k=0}^n {n \choose k} \mathbb{E}(X_k)$,

where $X_k$ is the indicator that we have a component with $k$ vertices and $k+1$ edges or more.

$\mathbb{E}(X_k) = \mathbb{P}(\text{no outgoing edges}) \mathbb{P}(k+1 \text{ edges or more})$

$\mathbb{E}(X_k) = (1-p)^{k(n-k)} \mathbb{P}(\text{Binomial}({k \choose 2}, p) \ge k+1)$

Here I am stuck when trying to find an upper bound for this expression. The inequalities I've tried either diverge or cause trouble in the summation. Hoeffding's inequality looked promising but gave me $k^2$ in the exponent which gave me a hard time with the summation. Any tips?

1 Answers 1

2

The threshold for cycles in $G(n,p)$ is $p=1/n$. The same threshold should work in your case, so the solution is basically $c = 1$.