0
$\begingroup$

I want to express the excepted size of the component for a randomly chosen node in the random Erdos-Renyi graph $G(n,p)$. I already read this thread, but I want to express it asymptotically.

Let $p = \dfrac{c}{n}$. Let $S$ be the random variable which gives us the size of the considered node.

The results I want to show (as $n \rightarrow \infty$) :

  • For $c<1$ : $\Bbb E[S] < \log(n)$
  • For $1<c < \log (n)$ : $\Bbb E [S] = qqn + (1-q)\log(n)$
  • For $c>1$ : $\Bbb E[S] = n$

Where $ q $ denotes the fraction of nodes in the giant component of the graph.

The results I already know:

  • If $np < 1$, then a graph in $G(n, p)$ will almost surely have no connected components of size larger than $O(\log(n))$.

  • If $np = 1$, then a graph in $G(n, p)$ will almost surely have a largest component whose size is of order $n^{2/3}$.

  • If $np → c > 1$, where $c$ is a constant, then a graph in $G(n, p)$ will almost surely have a unique giant component containing a positive fraction of the vertices. No other component will contain more than $O(\log(n))$ vertices.

  • If $p<\tfrac{(1-\epsilon)\ln n}{n}$, then a graph in $G(n, p)$ will almost surely contain isolated vertices, and thus be disconnected.

  • If $p>\tfrac{(1+\epsilon) \ln n}{n}$, then a graph in $G(n, p)$ will almost surely be connected.

  • Thus $\tfrac{\ln n}{n}$ is a sharp threshold for the connectedness of $G(n, p)$.

(Quote of the "Did"'s answer here)

What I tried: (the case $c<1$) We note $ k_n = a\log(n) $, with $a$ verifying $ \Bbb P(|C_{max}| \geq a\log(n)) \rightarrow 0$ where $|C_{max}|$ is the size of the biggest component. $$\begin{align} \Bbb E[S] &= \sum_{k=1}^n k\Bbb P(S=k)\\ & = \sum_{k=1}^{\lfloor k_n \rfloor} k\Bbb P(S=k) + \sum_{k\geq k_n}^n k\Bbb P(S=k) \\ & \leq \sum_{k=1}^{\lfloor k_n \rfloor} k\Bbb P(S=k) + n\times \sum_{k\geq k_n}^n\Bbb P(S=k)\\ & \leq \sum_{k=1}^{\lfloor k_n \rfloor} k\Bbb P(S=k) + n\times \Bbb P(|C_{max}| \geq a\log(n)) \end{align}$$

I don't know how to continue.

$\endgroup$
0
$\begingroup$

I would recommend the following book: https://www.math.cmu.edu/~af1p/BOOK.pdf, Chapter 2 regarding the evolution of random graphs: it is all there and it is explained very well.

Regarding connectedness, Chapter 4 of that book or, page 265 of https://www.cs.cornell.edu/jeh/book.pdf, which is also an excellent resource.

In particulat for $c<1$, $E(S)=O(\log n)$ is theorem 2.9 which is broken down in 3 different theorems to show that with high probability for $c<1$ then $E(S)=O(\log n)$.

Now Theorem 2.10 shows that with high probability, for $c<1$ every component in the random graph has at most one cycle.

Then Theorem 2.11 shows that indeed if you check the size of components with exactly one cycle, with high probability the number of vertices on those components is $O(w(n))$, with $w(n)$ being any growing function $w$, hence the size of components with exactly one cycle are if you will $o(\log \log n)$.

It remains then to check the order of components with no cycles, i.e. trees.

Now Theorem 2.12 is a bit more general, since it works for any $c \neq 1$, but in particular it works for $c<1$, which is what you want.

In there they show that with high probability the largest component in a random graph is an isolated tree with number of vertices $O(\log n)$. How do they show it? They show first that with high probability there is an isolated tree with $k_{-}$ vertices, where $k_{-} \leq a \log n$ (see details in the book). But is also shows that there is no isolated tree of order at least $k_{+}>k_{-}$, where $k_{+} \leq b \log n$, for some $b>a$, hence the order of the largest component is with high probability a tree of order $O(\log n)$.

$\endgroup$
  • $\begingroup$ I can't find the results I want to show in your books. But I found the results I already know. (But thanks for the references) $\endgroup$ – MiKiDe May 26 '18 at 16:41
  • $\begingroup$ It should be theorem 2.9 which is then broken down in the next 3 theorems: first 2.10 shows that for c<1 then with high probability, the random graph contains at most one cycle. Then 2.11 shows that indeed wth high probability, any component with exactly one cycle has basically a $O(w(n))$ of vertices, where $w$ goes to infinity as slow as you want, so thereofe you know that in practice the number of vertcies on those type of components are $o(log log (n)) for example. And finally 2.12 finally shows that for any $c$ so in particular for $c<1$ there is a tree with $O(\log n)$ component $\endgroup$ – Marco Bellocchi May 26 '18 at 16:47
  • $\begingroup$ It's part of the results that I said to be already known. The only results I want to show are those about $\Bbb E [S]$. Maybe it is the same results, but I can't get the link with the expected value. $\endgroup$ – MiKiDe May 26 '18 at 16:51
  • $\begingroup$ But theorem 2.12 does show $E(S)=O(\log n)$ no? $\endgroup$ – Marco Bellocchi May 26 '18 at 16:53
  • $\begingroup$ Does it? I just see bounds on the size of some trees. Maybe could you show me that $\Bbb E (S) = O(\log n)$ using 2.12? (I think I just can't see the link..) $\endgroup$ – MiKiDe May 26 '18 at 17:04

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.