On the largest strongly connected component of randomly oriented divisor graphs

We introduce the study of $\mathit{\text{randomly}}\mathit{\text{oriented}}\mathit{\text{divisor}}\mathit{\text{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, $\mathbf{\text{E}}[\mathrm{\#}\mathrm{\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.