# Prime number density vs. connectedness threshold: coincidence?

(1) $\pi(n)$, the number of primes at most $n$, is asymptotic to $n / \ln n$.

(2) In the Erdős-Rényi random graph model, $p = \ln n / n$ is a sharp threshold for the connectedness of the graph $G(n,p)$ on $n$ vertices with edge-probability $p$.

Is there any connection between these two, or is the ratio $n / \ln n$ natural enough to arise in several unrelated circumstances by happenstance?

(I ask as neither an expert in random graphs nor in number theory.)

-
It'd pretty natural, I have no reason to expect a connection. – Charles Sep 18 '11 at 22:31
@Charles: I thought perhaps that was a pun :-). You are likely correct, but it would be more interesting if there were a connection. However, desiring will not make it so. – Joseph O'Rourke Sep 18 '11 at 23:21
I imagine the relationship is much like the one offered in this answer mathoverflow.net/questions/53122/mathematical-urban-legends/… . Gerhard "Ask Me About Symbolic Relationships" Paseman, 2011.09.18 – Gerhard Paseman Sep 18 '11 at 23:29

1. $\pi(n)$ is a cardinality, whereas $p$ is a density; one is comparing apples and oranges. The density of the primes is $1/\log n$, which is quite different from $\log n/n$. (It is true that the average number of divisors $\tau(n)$ of a natural number $n$ is $\log n$, which at first glance seems to match the average degree of a Erdos-Renyi graph of density $\log n/n$, but $\tau(n)$ is very irregularly distributed (its variance is comparable to $\log^3 n$, for instance), in contrast to the Erdos-Renyi degree which obeys a central limit theorem, so this does not seem to be a good match.)
3. In an Erdos-Renyi graph, n is fixed, and all vertices are given equal weight. For the primes, it is much more natural to work on all the natural numbers at once, and give each natural number n a different weight ($1/n^s$ being a particularly good choice). This pulls the numerology of the two settings even further apart.