Consider Reny-Erdos random graph $G(n, p)$. This is graph is well-studied, mostly for the cases where $n$ is sufficiently large, however, I am interested in the case where $n$ is finite and small (like less than 20).
Specifically, I want to prove the following two properties (i.e. find $\alpha(.)$ and $\beta(.)$):
- $P(\text{There is a giant component connects majority of the nodes}) \geq \alpha(n, p)$
- $P(\text{diameter of the giant component} < c \log n) \geq \beta(n, p, c)$
assuming that $n$ is a finite number (i.e. NOT an asymptotic property), and large-enough $p$ (say $p > c' \ln n / n$).
For $n <20$ the quantity $\log n$ is at least $\frac{n}{5}$ and the quantity $\frac{\log n}{n}$ is at least $\frac{1}{5}$. So for $c=2$, the quantity $p$ would be at least .4, and for $c=5$ the quantity $p$ would be 1 e.g., for $n \le 20$ a graph drawn from $G(n,p)$ for $p = \frac{5 \log n}{n}$ would always be the complete graph on $n$ vertices.
Even for $c= 2$: If you work through the calculations a 20-node graph drawn according to the distribution where there is an edge between two vertices w probability $\frac{2 \log n}{n} \ge .4$, has to satisfy the probability of the giant component having small diameter no larger than $4 \le \log 20$. [In fact it is likely connected and the giant component is likely the entire graph]
So the calculations actually get easier for small $n$.