Let G(N,p) be an Erdos-Renyi graph, where N is the number of vertices, and p is the probability that two distinct vertices form an edge. If I plot 1-b0/N over log(p), then I obtain a curve which looks like a logistic function, where b0 is the number of connected components of G(N,p), and p is in (0,1). If p is not too close to zero, then a logistic function has a very good fit. If this were the true model, then the expected value for b0 would be
E(b0) = N/(1+(pN)^k)
with k = k(N) in (0,1), and at least for p not too close to 0. How can one prove this observation? And what can be said about k(N)? One consequence would be that at the percolation point p = 1/N, one has
E(b0) = N/2.
See http://snap.stanford.edu/class/cs224w-readings/erdos59random.pdf or http://www.leonidzhukov.net/hse/2016/sna/papers/erdos-1960-10.pdf for a detailed asymptotic probabilistic description of the number of connected components in a certain regime of p's.
Thanks for the links, Christoph. I see (your second link) that this is one of the results for the model with fixed number of edges which are also true for the model G(N,p).
There is also this paper by Jansen, Knuth, Luczak and Pittel from 1993: it does a fantastic job of really nailing everything down. https://arxiv.org/abs/math/9310236
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Probability