On the largest strongly connected component of randomly oriented divisor graphs

Abstract

We introduce the study of \textit{randomly oriented divisor graphs}. For each $\rho \in [0,1]$, the randomly oriented divisor graph ${\mathcal{D}}_{\rho }(N)$ is obtained from the divisor graph on $\{1,2,\dots ,N\}$ by directing each edge according to divisibility and independently reversing the direction of each edge with probability $\rho$. We study the expected size of the largest strongly connected component, $\text{E}[\#\Phi ({\mathcal{D}}_{\rho }(N))]$. Our main result gives a lower bound for this quantity in terms of the distribution of values of the divisor function $\tau (n)$. As a consequence, we show that for any fixed $\rho \in (0,1)$, the largest strongly connected component has expected size asymptotic to $N$. To obtain explicit bounds, we prove an effective version of a theorem of Hardy and Ramanujan on the normal order of $\log \tau (n)$, which may be of independent interest.

15 pages, 5 figures, 2 tables. Refined Theorem 3. Comments welcome!