On the largest strongly connected component of randomly oriented divisor graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910107318616064 |
|---|---|
| author | Kim, Jihyung Phillips, Tristan |
| author_facet | Kim, Jihyung Phillips, Tristan |
| contents | We introduce the study of \textit{randomly oriented divisor graphs}. For each $ρ\in [0,1]$, the randomly oriented divisor graph $\mathcal{D}_ρ(N)$ is obtained from the divisor graph on $\{1, 2, \ldots, N\}$ by directing each edge according to divisibility and independently reversing the direction of each edge with probability $ρ$. We study the expected size of the largest strongly connected component, $\textbf{E}[\#Φ(\mathcal{D}_ρ(N))]$. Our main result gives a lower bound for this quantity in terms of the distribution of values of the divisor function $τ(n)$. As a consequence, we show that for any fixed $ρ\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 τ(n)$, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05176 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the largest strongly connected component of randomly oriented divisor graphs Kim, Jihyung Phillips, Tristan Combinatorics Number Theory Primary: 05C80, 11N37, Secondary: 05C20, 11N56, 60C05 We introduce the study of \textit{randomly oriented divisor graphs}. For each $ρ\in [0,1]$, the randomly oriented divisor graph $\mathcal{D}_ρ(N)$ is obtained from the divisor graph on $\{1, 2, \ldots, N\}$ by directing each edge according to divisibility and independently reversing the direction of each edge with probability $ρ$. We study the expected size of the largest strongly connected component, $\textbf{E}[\#Φ(\mathcal{D}_ρ(N))]$. Our main result gives a lower bound for this quantity in terms of the distribution of values of the divisor function $τ(n)$. As a consequence, we show that for any fixed $ρ\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 τ(n)$, which may be of independent interest. |
| title | On the largest strongly connected component of randomly oriented divisor graphs |
| topic | Combinatorics Number Theory Primary: 05C80, 11N37, Secondary: 05C20, 11N56, 60C05 |
| url | https://arxiv.org/abs/2604.05176 |