This article presents a two-dimensional extension of divisibility networks, constructed on generalized integer lattice, and developed to explore their applications in inequality structures. Edges join nodes that share either the same multiple index \(n\) or the same divisor index \(k\), which form a rook–divisibility network that unites arithmetic structure and graph topology within a deterministic grid. The resulting finite graph \(G_N=\{(k,n)\in\mathbb{N}^2:1\le n\le N,\,k\mid n\}\) admits exact analysis of its main invariants. Closed forms are derived for the local degree \(\deg(k,n)\) and clustering coefficient \(C(k,n)\); they reveal how small \(k\) columns act as hubs and highly composite rows yield strong local cohesion. A constructive proof via projection maps establishes global connectivity for all \(N\), and asymptotic evaluation shows that the average degree grows as \(\langle k\rangle_N\!\sim\!(\pi^2/6)\,N/\log N\), much faster than in the one-dimensional divisor network. The results provide a heavy–tailed degree distribution governed by a logarithmic factor, while empirical simulations and log-binned spectra confirm close agreement between measured and analytic clustering across degree ranges. Further visual analyses illustrate the emergence of hubs, stretching similarity, and stable scaling of local clustering. In addition, the rook-divisibility framework is shown to generate new forms of discrete and fractional inequalities. By interpreting row- and column-averaging operations as convex and fractional mean processes, the model yields Hermite-Hadamard-Mercer-type bounds and degree-clustering inequalities.
Arithmetic networks, such as graphs built from divisibility relations, offer a deterministic, interpretable setting for studying phenomena that also appear in complex networks (heterogeneous degrees, community structure, and nontrivial clustering). Moving from one-dimensional sequences on \(\mathbb{N}\) to lattice-indexed settings on \(\mathbb{R}_{+}^{2}\) broadens this lens to bi-indexed interactions, where row-wise and column-wise effects can be examined separately and compared. Such grid-embedded constructions naturally connect number-theoretic quantities (e.g., divisor counts and distributions of multiples) with graph invariants (degree, clustering, paths), enabling qualitative insights alongside the possibility of closed-form counting arguments and asymptotic analysis. This makes the setting a useful bridge between discrete mathematics and network science, where structure is explicit and parameters are transparent.
From an applications standpoint, lattice-indexed graphs provide faithful abstractions for systems with two intrinsic indices—scale-location decompositions, channel-token interactions in signal processing and learning, or stencil couplings in numerical PDEs. Casting these dependencies as networks clarifies sparsity patterns, highlights potential hubs and bottlenecks, and yields reproducible benchmarks for algorithms on structured topologies. Because the underlying rules are simple and visualizations can be made clear (grid or spring layouts), the framework supports rigorous comparison across sizes and variants without heavy simulation or tuning, offering value for theory, computation, and modeling across domains.
Before proceeding, we briefly clarify the term rook–divisibility used throughout the paper. The name comes from the way a rook moves in chess—only horizontally or vertically. In our framework, vertices are placed on a two–dimensional grid indexed by pairs \((k,n)\), and connections are allowed only along rows or columns. Two vertices are therefore linked when they share a row or a column and satisfy a divisibility relation. In simple terms, rook– divisibility describes an arithmetic network where interactions are restricted to these rowwise and columnwise directions, making the underlying structure easy to visualize while remaining fully determined by number–theoretic rules.
We begin by recalling key arithmetic and graph-theoretic notions that will serve throughout the analysis. Let \(\mathbb{N}\) denote the set of positive integers and \(\mathbb{R}_+^2\) the positive quadrant of the Euclidean plane. For any \(n \in \mathbb{N}\), denote by \(\tau(n)\) the number of positive divisors of \(n\), and by \[D(n) = \{ k \in \mathbb{N} : k \mid n \},\] its divisor set. The set of ordered pairs satisfying the divisibility condition is \[S_N = \{ (k,n) \in \mathbb{N}^2 : 1 \leq n \leq N,\; k \mid n \}.\]
Each pair \((k,n)\) will correspond to a vertex in our network representation, with arithmetic quantities \(k\) and \(n\) playing distinct yet complementary structural roles: \(k\) controls column connectivity (multiples), while \(n\) controls row connectivity (divisors).
Given a finite set \(V_{N} = S_N\), we define an undirected simple graph \(G_N = (V_{N},E_N)\) where an edge connects two distinct vertices \((k_1,n_1)\) and \((k_2,n_2)\) whenever either \[n_1 = n_2 \quad \text{or} \quad k_1 = k_2.\]
Thus, nodes on the same row \(n\) (sharing a common multiple) form a divisor clique, while nodes on the same column \(k\) (sharing a common divisor) form a multiple clique. The network can therefore be viewed as the superposition of overlapping complete subgraphs arranged along the grid \(\mathbb{N}^2\), with intersection points corresponding to shared \((k,n)\) vertices.
For each fixed \(k \le N\), denote by \[M_k(N) = \Big\lfloor \frac{N}{k} \Big\rfloor,\] the number of multiples of \(k\) not exceeding \(N\). Consequently, each column \(k\) of the lattice contains \(M_k(N)\) nodes. These basic quantities drive the combinatorial structure of \(G_N\): the degree, clustering, and higher-order motifs depend jointly on \(\tau(n)\) and \(M_k(N)\), coupling divisor and multiple statistics in an explicitly analyzable form.
Throughout the paper, \(V_{N}\) denotes the vertex set, \(E_N\) the edge set, \(\deg(k,n)\) the degree of vertex \((k,n)\), and \(C(k,n)\) its local clustering coefficient. Unless otherwise stated, all asymptotic statements refer to the limit \(N \to \infty\) and make use of classical divisor-sum estimates, \[\sum\limits_{n\le N} \tau(n) = N \log N + (2\gamma – 1)N + o(N),\] where \(\gamma\) is the Euler-Mascheroni constant. These preliminaries provide the arithmetic foundation for the network-theoretic analysis developed in the next section.
The analysis of the rook–divisibility network relies on a combination of arithmetic and combinatorial constructions on lattice-indexed sets. We collect here the essential notations and conventions used throughout the paper.
Let \(\mathbb{N}\) denote the set of positive integers and \(\mathbb{N}^2_+\) the positive integer lattice embedded in \(\mathbb{R}^2_+\). For a given cutoff \(N \in \mathbb{N}\), define the arithmetic subset \[S_N = \{ (k,n) \in \mathbb{N}^2 : 1 \le n \le N,\; k \mid n \}.\]
Each element \((k,n)\) encodes a divisor–multiple pair and serves as a vertex in our network. The first coordinate \(k\) indexes a column of fixed divisor value, while the second coordinate \(n\) indexes a row corresponding to all divisors of \(n\). Hence, \(S_N\) forms a rectangular grid of divisibility-constrained points on \(\mathbb{Z}^2\), dense along the lower diagonal and sparse toward the upper right.
Given \(S_N\), we construct a deterministic graph \(G_N = (V_{N},E_N)\) by declaring that two vertices \((k_1,n_1),(k_2,n_2)\in S_N\) are adjacent if and only if \[n_1=n_2 \quad \text{or} \quad k_1=k_2,\] mirroring the movement of a rook in chess. Each horizontal line \(n=\mathrm{const}\) induces a complete row clique of size \(\tau(n)\), and each vertical line \(k=\mathrm{const}\) induces a column clique of size \(M_k(N) = \lfloor N/k \rfloor\). These two families of cliques intersect orthogonally, yielding a grid of overlapping complete subgraphs and producing a deterministic small-world topology with analytically traceable structure.
For fixed \(n\), divisors \(k\) satisfy \(k \le \sqrt{n}\) or \(k \ge \sqrt{n}\) symmetrically; the mapping \(k \mapsto n/k\) induces a reflection across the main diagonal. Consequently, the divisibility domain inherits a discrete mirror symmetry \[(k,n) \longleftrightarrow (n/k,\,n),\] suggesting a geometric factorization surface embedded in \(\mathbb{R}^2\). This symmetry ensures that the local degree and clustering statistics are invariant under inversion of \(k\) within the same row, up to integer truncation effects. The “rook” connections thus respect both multiplicative hierarchy and geometric reflection.
We will frequently employ standard asymptotic notation: \[f(N) = O(g(N)), \quad f(N) \sim g(N), \quad \text{and} \quad f(N) = \Theta(g(N)),\] in the limit \(N \to \infty\). The divisor function satisfies \[\sum\limits_{n\le N}\tau(n) = N \log N + (2\gamma – 1)N + o(N),\] where \(\gamma\) denotes the Euler-Mascheroni constant. The harmonic sums \(\sum\limits_{k\le N} \lfloor N/k \rfloor\) and \(\sum\limits_{k\le N}\lfloor N/k \rfloor^2\) are used to express total degree and clustering counts, linking discrete arithmetic averages to analytic estimates via Dirichlet hyperbola methods.
Construction of \(G_N\) proceeds by computing the divisor sets \(D(n)\) for \(1\le n\le N\), leading to a total vertex count \[V_{N} = \sum\limits_{n\le N} \tau(n) = O(N\log N).\]
Because each \(D(n)\) induces a clique and every column requires updates proportional to \(\lfloor N/k \rfloor\), the total edge count satisfies \(E_{N} = \Theta(N^2/\log N)\) asymptotically. Thus, the model interpolates between sparse (\(\log N\) scaling of 1D divisibility graphs) and dense (\(N\) scaling) regimes, producing a rich combinatorial-analytic crossover.
The rook-divisibility network therefore inhabits a two-dimensional arithmetic lattice with a precisely defined local geometry, mirrored factorization symmetry, and predictable growth laws. These preliminaries lay the foundation for the closed-form local statistics and scaling results derived in the subsequent sections.
There is now a substantial literature at the intersection of number theory and network science that models divisibility structure with graphs. Early work on the divisor graph—with vertices the positive integers and edges between \(a,b\) when one divides the other—focused on extremal path problems and large-scale structure [1– 4]. In parallel, algebraic and arithmetic graph variants have been studied, such as graphs built from proper divisors of a fixed integer \(n\) [5] and survey-style accounts that synthesize structural properties across many divisor-graph flavors [6]. From the complex-networks perspective, Shekatkar, Bhagwat, and Ambika analyzed the undirected divisibility network on \(\{1,\dots,N\}\) and reported heavy-tailed degree, nontrivial clustering, and smooth finite-size scaling of global statistics [7]. Complementary constructions isolate primes versus composites using bipartite or dynamical models [8], while multiplex formulations replace divisibility by congruence layers to study controllability and chain structures [9]. Methodologically, these studies borrow the standard toolkit of network science—small-world and scale-free baselines [10, 11], statistical inference for power laws [12], and general modeling/measurement frameworks [13, 14].
While much of the prior literature on deterministic scale-free or hierarchical graphs focuses on recursive growth models, our approach is distinct in its arithmetic lattice embedding. In particular, Iguchi & Yamada showed an exactly solvable deterministic network with closed-form degree and clustering laws [15], and Jiao et al. [16] studied spectral scaling in deterministic models, which is relevant to potential extensions of our framework. The pseudofractal scale-free web by Dorogovtsev et al. [17] is another classical analytical model combining scale-free distribution and hierarchical structure.
On the graph-limit and continuum side, theories of sparse graph convergence [18] and probability‐graphons [19, 20] provide a context in which our finite lattice network might converge (or embed) into a limiting kernel. For example, recent work on dynamics on graph limits [21] and mean-field limits in non-exchangeable systems [22] offers theoretical motivation for analyzing diffusion, spectral, or flow processes on our deterministic network in a continuum regime.
More recent number-theoretic network papers refine local/global measures and seek arithmetic interpretations. For instance, explicit formulas for degree, clustering, and centrality in divisibility graphs reveal clear signatures at prime vertices and track trends as \(N\) grows [7]. Path-partition and covering problems in the divisor graph connect to classical questions on primitive sets and related combinatorial number theory [3, 4]. Collectively, this body of work establishes that divisibility-induced graphs over \(\mathbb{N}\) are rich testbeds where network statistics mirror arithmetic structure, and vice versa [7– 9]. To the best of the authors’ knowledge, however, existing studies focus almost exclusively on single-indexed integer networks and do not address two-dimensional divisibility networks whose nodes are ordered pairs endowed with “row/column” adjacencies within a rectangular lattice of labels.
The literature above models divisibility on \(\mathbb{N}\) or within algebraic variants, but it does not consider networks whose nodes are ordered pairs \((k,n)\in\mathbb{R}_+^2\cap\mathbb{N}^2\) endowed with natural rook-type (same row/column) adjacencies alongside divisibility relationships. Introducing pair-labeled nodes opens new axes: interactions within rows \((k,\cdot)\), within columns \((\cdot,n)\), and across them via divisibility constraints (e.g., \(k\mid n\)). This two-dimensional setting enables questions about anisotropy between row- and column-induced neighborhoods, factorization geometry across slices, and how classical statistics (degree, clustering, assortativity, path covers) reorganize when divisibility is embedded in a grid-like label space. Filling this gap provides a principled framework to compare one-dimensional integer networks with their two-dimensional extensions and may reveal finer structural correspondences between local arithmetic constraints and mesoscopic network organization.
Divisibility graphs have emerged as a deterministic yet rich testing ground for questions in complex networks. The classical model places nodes at the natural numbers \(1,2,3,\dots\) and connects two numbers when either divides the other; despite its simplicity it displays heavy–tailed degree, nontrivial clustering, and arithmetic regularities. Here we develop a two–dimensional generalization aligned with applications where interactions are naturally indexed by pairs (e.g., frequency–scale, space–time, channel–token, or row-column couplings).
We embed the network in the positive quadrant \(\mathbb{R}^2_{+}\) by taking the integer lattice subset \[S_N=\{(k,n)\in \mathbb{N} ^2:\; 1\le n\le N ,\; k\mid n\}\subset \mathbb{R}^2_{+},\] and we study graphs on \(S_N\) generated by divisibility rules. Our primary focus is the rook–divisibility graph, where edges appear along rows and columns: two nodes \((k_1,n_1)\) and \((k_2,n_2)\) are adjacent iff \(n_1=n_2\) (same row) or \(k_1=k_2\) (same column). Intuitively, each row forms a clique of the divisors of \(n\), each column forms a clique of the multiples of \(k\), and the full network is their union with overlaps at the intersection nodes.
This perspective turns number-theoretic data \((k\mid n)\) into a geometrically structured complex network with tunable size parameter \(N\). We obtain exact local formulas, simple connectivity proofs, and interpretable asymptotics for average degree and clustering when \(N\) grows.
Definition 1(Finite rook-divisibility network).Fix \(N\in\mathbb{N}\). Define the vertex set \[V_{N}=\{(k,n)\in\mathbb{N}^2:\ 1\le n\le N,\ k\mid n\}.\]
Two distinct vertices \(u=(k_1,n_1)\) and \(v=(k_2,n_2)\) are joined by an undirected edge iff \[n_1=n_2 \quad\text{or}\quad k_1=k_2.\]
We denote the resulting graph by \(G_{N}=(V_{N},E_{N})\).
It is convenient to view \(G_{N}\) as a growing network. At discrete time \(t=1,2,\dots,N\):
1. Add the row \(t\) by creating one node \((k,t)\) for each divisor \(k\mid t\).
2. Make the row clique: join all \((k,t)\) pairwise (they share the same \(t\)).
3. For each new node \((k,t)\), connect it to all existing nodes with the same \(k\) (i.e., \((k,m)\) for multiples \(m< t\)).
This updates the column clique for \(k\). The network at time \(t\) equals \(G_t\).
Proposition 1(Connectivity).For every \(N\ge1\), the graph \(G_{N}\) is connected.
Proof. For any \(n\), \((1,n)\) exists and is adjacent to \((1,1)\); every \((k,n)\) is adjacent to \((1,n)\) (same row). Thus all nodes connect to \((1,1)\). ◻
Lemma 1(Connectivity via projection maps).Let \(G_N=(V_{N},E_N)\) be the rook–divisibility graph on \(V_{N}=\{(k,n)\in\mathbb{N}^2:1\le n\le N,\;k\mid n\}\) in which two distinct vertices are adjacent iff they share the same row \(n\) or the same column \(k\). Then \(G_N\) is connected. Moreover, \(G_N\) admits a graph retraction onto the induced subgraph on the spine \(\{(1,n):1\le n\le N\}\), which is a clique of size \(N\).
Proof. Define the row- and column-projections \[\pi_{\mathrm{row}}(k,n):=(1,n),\qquad \pi_{\mathrm{col}}(k,n):=(k,1).\]
For any \((k,n)\in V_{N}\), the vertices \((k,n)\) and \((1,n)\) are adjacent since they lie on the same row. Hence every vertex is at graph distance \(1\) from its image under \(\pi_{\mathrm{row}}\). Because \(1\mid m\) for every \(1\le m\le N\), all vertices \((1,1),\dots,(1,N)\) exist and, by sharing the same column \(k=1\), they form a clique. It follows that the induced subgraph on \(\{(1,n):1\le n\le N\}\) is connected, and in fact complete.
Now consider the map \(r:V_{N}\to V_{N}\) given by \(r:=\pi_{\mathrm{row}}\). For any edge \(u\sim v\), either \(u\) and \(v\) share their row (in which case \(r(u)=r(v)\)) or they share their column (in which case \(r(u)\) and \(r(v)\) lie in the same column \(k=1\) and are therefore adjacent). Thus \(r\) is a graph homomorphism that fixes every vertex of the spine, so it is a graph retraction onto the induced clique on \(\{(1,n)\}\). In particular, every \((k,n)\) connects to \((1,n)\) (one step), and any two vertices connect via the spine within two steps, proving connectivity.
This refines the one-line connectivity observation already noted in the paper by exhibiting an explicit retraction onto a canonical connected subgraph (the \(k=1\) column). ◻
Write \(\tau(n)\) for the number of positive divisors of \(n\). Let \(M_k(N)=\big\lfloor N /k\big\rfloor\) be the number of multiples of \(k\) in \(\{1,\dots,N\}\).
Proposition 2(Degree). For a vertex \((k,n)\in V_{N}\), \[\deg(k,n)=\underbrace{\big(\tau(n)-1\big)}_{\text{same row}}+\underbrace{\big(M_k(N)-1\big)}_{\text{same column}} =\tau(n)+\big\lfloor N /k\big\rfloor-2.\]
Proposition 3(Triangles and local clustering).Let \(r=\tau(n)-1\) and \(c=M_k(N)-1\). The neighbors of \((k,n)\) split into two cliques of sizes \(r\) and \(c\) (row and column), sharing only the center \((k,n)\). Hence the number of triangles incident to \((k,n)\) is \[T(k,n)=\binom{r}{2}+\binom{c}{2},\] and the local clustering coefficient equals \[C(k,n)=\frac{T(k,n)}{\binom{r+c}{2}} =\frac{\binom{\tau(n)-1}{2}+\binom{\left\lfloor N /k\right\rfloor-1}{2}} {\binom{\tau(n)+\left\lfloor N /k\right\rfloor-2}{2}}\, .\]
Remark 1(Network size and averages).The vertex count is \(\lvert V_{N}\rvert=\sum\limits_{n\le N }\tau(n)\). Averaging the explicit degree formula yields \[\begin{aligned} \frac{1}{\lvert V_{N}\rvert}\sum\limits_{(k,n)\in V_{N}}\operatorname{deg}(k,n) = \frac{1}{\lvert V_{N}\rvert}\sum\limits_{n\le N}\sum\limits_{k\mid n} \Big(\tau(n)+\left\lfloor \frac{N}{k} \right\rfloor – 2\Big). \end{aligned} \tag{1}\] which separates into a row term (divisor statistics of \(n\)) and a column term (harmonic sum over \(k\) via \(N/k\)). As \(N\to\infty\) the column term induces heavy tails since small \(k\) produce many multiples.
We evaluate the degree distribution of the rook-divisibility network on ordered pairs \(V_{N}=\{(k,n)\in\mathbb{N}^2:\ 1\le n\le N,\ k\mid n\}\). For each vertex \((k,n)\) the degree decomposes additively into a row term and a column term, \[\deg(k,n)=\tau(n)+\Big\lfloor\frac{N}{k}\Big\rfloor-2,\] so hubs arise along small-\(k\) columns while composite rows increase local density. To visualize the distribution we use logarithmic bins whose edges are successive powers of two, \(2^0,2^1,2^2,\dots\), and plot the mass per unit degree by dividing counts in each bin by the bin width. Zero-degree vertices (which occur at \((p,p)\) when \(p\) is prime and \(p>N/2\)) are omitted from the log-log plot.
We fit the tail to a power law \(p(k)\sim k^{-\alpha}\) by maximum likelihood following [12]: for each candidate threshold \(k_{\min}\) we estimate \(\hat\alpha=1+ n\big/\sum\limits_{i=1}^{n}\log\!\big(k_i/(k_{\min}-\tfrac12)\big)\) on the tail \(\{k_i\ge k_{\min}\}\), and select \(k_{\min}\) by minimizing the Kolmogorov-Smirnov distance between empirical and model CDFs. For \(N=1024\) the fitted tail has slope \(\alpha\approx 1.43\) (dashed line in the figure). This suggests a heavy-tailed degree distribution induced by the column term \(\lfloor N/k\rfloor\), with the precise finite-size exponent shaped jointly by the divisor statistics of \(n\) and the multiplicity profile of \(k\).
Having characterized the empirical distribution and its numerical fit, we now formalize the asymptotic behavior of the degree tail through the following theorem.
Theorem 1(Asymptotic heavy-tail bounds for the degree).Let \(D\) be the degree of a uniformly random vertex of \(G_N\). There are absolute constants \(c_1,c_2>0\) such that for all \(d\) with \(2\le d\le N\), \[\frac{c_1\,\log\!\bigl(N/d\bigr)}{\log N} \;\;\le\;\;\mathbb{P}(D\ge d) \;\;\le\;\; \frac{c_2\,\log\!\bigl(N/d\bigr)}{\log N}.\]
In particular, the degree distribution has a heavy (non-exponential) tail governed by a slowly varying logarithmic factor; on finite ranges this tail admits effective power-law fits (e.g., the empirical slope reported around \(\alpha\approx 1.43\) at \(N=1024\) in §2.3).
Proof. Write \(M_k(N)=\lfloor N/k\rfloor\) and note \[\deg(k,n)=\tau(n)+M_k(N)-2\qquad\text{for }(k,n)\in V_{N}.\]
Fix \(d\ge 2\). For any column index \(k\le N/d\) we have \(M_k(N)\ge d\), hence \(\deg(k,n)\ge d-2\) for all nodes in column \(k\), independently of \(n\). Thus every vertex in columns \(k\le N/d\) contributes to the event \(\{D\ge d\}\), yielding \[\#\{v:\deg(v)\ge d\}\;\ge\;\sum\limits_{k\le N/d} M_k(N).\]
Conversely, for \(k> N/d\) we have \(M_k(N)<d\), so \(\deg(k,n)<d-2+\tau(n)\). Since \(\tau(n)=O_\varepsilon(n^\varepsilon)\) for any \(\varepsilon>0\), the set of exceptional vertices with \(\deg\ge d\) outside columns \(k\le N/d\) contributes a lower-order amount that can be absorbed in the constants for all \(d\) in the stated range.
Using the harmonic-sum estimate \(\sum\limits_{k\le x}\lfloor N/k\rfloor = N\log x + O(N)\) and taking \(x=N/d\) gives \[\sum\limits_{k\le N/d} M_k(N) = N\log(N/d)+O(N).\]
Since \(|V_{N}|=\sum\limits_{n\le N}\tau(n)=N\log N+O(N)\), we obtain \[\mathbb{P}(D\ge d) =\frac{\# \{v:\deg(v)\ge d\}}{\lvert V_{N}\rvert} =\frac{N\log(N/d)+O(N)}{N\log N+O(N)} =\frac{\log(N/d)}{\log N}\cdot\bigl(1+O(1/\log N)\bigr).\]
This proves the two-sided bounds with suitable absolute constants \(c_1,c_2\).
The bound shows a regularly varying tail modulated by a slowly varying logarithm: \(\mathbb{P}(D\ge d)\asymp \log(N/d)/\log N\). Over finite decades of \(d\) this can numerically mimic a power law (as observed above at \(N=1024\)), even though the asymptotic governor is logarithmic rather than a pure \(d^{1-\alpha}\) law. ◻
For the rook-divisibility network on ordered pairs \(V_{N}=\{(k,n)\in\mathbb{N}^2:\ 1\le n\le N,\ k\mid n\}\), the neighbors of a node \((k,n)\) split into two complete subgraphs: the row clique of size \(r=\tau(n)-1\) and the column clique of size \(c=\lfloor N/k\rfloor-1\). Consequently, the degree and local clustering coefficient are \[\deg(k,n)=r+c, \qquad C(k,n)=\frac{\binom{r}{2}+\binom{c}{2}}{\binom{r+c}{2}} = 1 – \frac{2rc}{(r+c)(r+c-1)}.\]
We estimate the dependence \(c(k)\) of clustering on degree \(k\) by grouping vertices by degree using logarithmic bins with edges \(2^0,2^1,2^2,\dots\) and plotting the mean clustering within each bin on log-log axes. The dashed curve overlays the simple asymptotic guide \(c(k)\approx 1-\frac{A}{k}\) (with \(A\) fixed to match the largest bin).
Since \(C(k,n)=1-\frac{2rc}{\deg(k,n)\,(\deg(k,n)-1)}\), whenever one clique dominates (e.g. \(c\gg r\) for small \(k\), or \(r\gg c\) for highly composite \(n\)), we have \(C(k,n)=1-\mathcal{O}(1/\deg(k,n))\). Accordingly, the binned average \(c(k)\) grows toward \(1\) as degree increases, reflecting that high-degree vertices are typically formed by one large clique (column or row) with a much smaller counterpart.
The following Figure 5 provides comparison of empirical and analytic clustering spectra for the rook-divisibility network on ordered pairs \((k,n)\) with \(k\mid n\) and \(1\le n\le N\) (here \(N=1024\)). Vertices are grouped by degree using logarithmic bins; the plot shows the average local clustering in each bin for both the empirical measurement (from the constructed graph) and the analytic formula \(C(k,n)=\bigl(\binom{\tau(n)-1}{2}+\binom{\lfloor N/k\rfloor-1}{2}\bigr)\big/\binom{\tau(n)+\lfloor N/k\rfloor-2}{2}\). The two curves coincide across bins, confirming the exactness of the closed-form expression and its agreement with network measurements.
For the rook-divisibility network \(V_{N}=\{(k,n)\in\mathbb{N}^2:\ 1\le n\le N,\ k\mid n\}\), each vertex \((k,n)\) has neighbors split into two cliques: the row clique of size \(r=\tau(n)-1\) and the column clique of size \(c=\lfloor N/k \rfloor – 1\). Hence \(\deg(k,n)=r+c\) and \[C(k,n)=\frac{\binom{r}{2}+\binom{c}{2}}{\binom{r+c}{2}} =1-\frac{2\,rc}{(r+c)(r+c-1)}.\]
We index vertices lexicographically by \((n,k)\) and plot \(c_i=C(k,n)\) against the node index \(i\) for \(N=2^{13},\,2^{14},\,2^{15}\). In any fixed window of indices the values appear irregular, but as \(N\) increases the entire point cloud stretches horizontally while preserving a characteristic envelope shaped by the pair \((r,c)\). When one clique dominates (e.g. small \(k\) so \(c\gg r\) or highly composite \(n\) so \(r\gg c\)), we have \(C(k,n)=1-\mathcal{O}(1/\deg)\); thus high-degree vertices cluster close to \(1\), whereas vertices with more balanced \((r,c)\) fall lower, forming visible bands. This produces a clear “stretching similarity” pattern across increasing \(N\).
Let \(V_{N}=\{(k,n)\in\mathbb{N}^2:\ 1\le n\le N,\ k\mid n\}\) and join two distinct vertices if they share the same row \(n\) or the same column \(k\) (rook-divisibility). For \((k,n)\in V_{N}\) the degree equals \[\deg(k,n)=\tau(n)+\Big\lfloor\frac{N}{k}\Big\rfloor-2 ,\] so the average degree admits the exact identity \[\langle k\rangle_N \;=\; \frac{\displaystyle \sum\limits_{n\le N}\tau(n)^2 \;-\; 2\sum\limits_{n\le N}\tau(n) \;+\; \sum\limits_{k\le N}\Big\lfloor\frac{N}{k}\Big\rfloor^{\!2}} {\displaystyle \sum\limits_{n\le N}\tau(n)} .\]
Using the classical asymptotics \(\sum\limits_{n\le N}\tau(n)=N\log N+(2\gamma-1)N+o(N)\) and \(\sum\limits_{k\le N}\!\lfloor N/k\rfloor^2 = (\pi^2/6)N^2 + O(N\log N)\), the leading behavior is \[\langle k\rangle_N \;=\; \frac{\pi^2}{6}\,\frac{N}{\log N}\;+\;O\!\left(\frac{(\log N)^2}{\log N}\right).\]
Figure 7 plots the exact values together with the analytic curve \(\tfrac{\pi^2}{6}\tfrac{N}{\log N}\) (solid). The agreement confirms that, unlike the one-dimensional integer network (which grows \(\sim\! \log N\)), the 2D ordered-pair network exhibits a much faster growth of the average degree, essentially linear in \(N/\log N\).
Let \(V_{N}=\{(k,n)\in\mathbb{N}^2:\ 1\le n\le N,\ k\mid n\}\) and join two vertices if they share the same row \(n\) or the same column \(k\) (rook-divisibility). For \((k,n)\in V_{N}\), \[C(k,n)=\frac{\binom{\tau(n)-1}{2}+\binom{\lfloor N/k\rfloor-1}{2}} {\binom{\tau(n)+\lfloor N/k\rfloor-2}{2}} =1-\frac{2(\tau(n)-1)\,(\lfloor N/k\rfloor-1)}{\deg(k,n)(\deg(k,n)-1)} .\]
Index vertices lexicographically by \((n,k)\) and define \(\Delta c_i = c_i – c_{i+1}\). Figure 8 plots \(\Delta c_i\) against \(i\) for \(N=2^{15}\). The scatter is centered around \(0\) and exhibits clear horizontal bands together with a “stretching similarity’’ pattern as \(i\) increases. Within a fixed row \(n\) (constant \(\tau(n)\)), moving to the next divisor typically changes the column size \(\lfloor N/k\rfloor\) by discrete steps, producing nearly constant increments in \(C(k,n)\) and hence visible banding. When \(i\) crosses from the last divisor of \(n\) to the first divisor of \(n{+}1\), the row size \(\tau(n)\) changes abruptly, inducing larger positive or negative jumps. As \(N\) grows, these features replicate on broader index ranges, preserving the global qualitative envelope while stretching horizontally.
The aim of this section is to establish how the suggested rook–divisibility network offers a systematic formulation for deriving, and interpreting a class of classical and fractional inequalities. By utilizing the deterministic arithmetic structure of the network, we present that several well-known inequality forms appear as direct consequences of its averaging and combinatorial mechanisms.
The new rook–divisibility network framework established in this study offers an analyzable and structured platform for interpreting and generating various forms of mathematical inequalities. Since each vertex \((k,n)\) represents a divisor–multiple pair and the edges encode deterministic arithmetic adjacency, the network implicitly defines inequality lattices, that is, hierarchical relations among number-theoretic quantities and their aggregated means. The deterministic clique intersections (rowwise and columnwise) naturally correspond to additive and multiplicative averaging processes that can be expressed through classical integral, convex, or fractional inequalities.
Each horizontal clique in the network represents the divisor set \(D(n)\), while each vertical clique represents the multiple set \(M_k(N)\). Considering a real-valued arithmetic function \(f : \mathbb{N} \rightarrow \mathbb{R}^{+}\), the local averages over these cliques can be defined as \[A_n(f) = \frac{1}{\tau(n)} \sum\limits_{k \mid n} f(k), \qquad A_k(f) = \frac{1}{\lfloor N/k \rfloor} \sum\limits_{m \leq N/k} f(km),\] which correspond respectively to divisor and multiple means. The inequality \[\min_{(k,n)\in V_N} f(k,n) \leq \frac{A_n(f) + A_k(f)}{2} \leq \max_{(k,n)\in V_N} f(k,n),\] acts as a discrete analogue of the classical Hermite-Hadamard inequality for convex functions, where rowwise and columnwise averaging parallels the integral mean over an interval. Hence, the rook-divisibility grid provides a finite arithmetic analogue of continuous convexity inequalities on domains with multiplicative symmetry.
The network’s two-dimensional ordering \((k,n)\) admits fractional-sum and integral analogues. Assigning fractional weights \(w_{k,n} = (k/n)^{\alpha}\) for \(0 < \alpha < 1\), one can define the weighted mean \[\mathcal{M}_{\alpha}(f; N) = \frac{\displaystyle\sum\limits_{(k,n)\in V_N} w_{k,n}\, f(k,n)} {\displaystyle\sum\limits_{(k,n)\in V_N} w_{k,n}}.\]
The monotonicity and boundedness of \(\mathcal{M}_{\alpha}(f; N)\) generate inequalities of Hermite-Hadamard-Mercer type in fractional form: \[f_{\min} \leq \mathcal{M}_{\alpha}(f; N) \leq \frac{1}{2} \bigl(\mathcal{M}_{0}(f; N) + \mathcal{M}_{1}(f; N)\bigr),\] which capture the transition between arithmetic and geometric means within the two-dimensional divisor-multiple lattice. Such inequalities can be extended to fractional integrals on the unit square \([0,1]^2\) by interpreting \(k/N \mapsto x\), \(n/N \mapsto y\), and taking the limit \(N \to \infty\).
The closed-form expressions \[\deg(k,n) = \tau(n) + \left\lfloor \frac{N}{k} \right\rfloor – 2, \qquad C(k,n) = 1 – \frac{2(\tau(n)-1)(\lfloor N/k \rfloor – 1)} {(\deg(k,n))(\deg(k,n)-1)},\] establish natural inequality relations among network invariants. By applying the arithmetic-geometric mean (AM-GM) and Cauchy-Schwarz inequalities, we get \[C(k,n) \geq 1 – \frac{2\sqrt{(\tau(n)-1)(\lfloor N/k \rfloor – 1)}}{\deg(k,n)-1},\] and for all \((k,n)\in V_N\), \[\frac{2}{\deg(k,n)} \leq 1 – C(k,n) \leq \frac{2}{\sqrt{\tau(n)\lfloor N/k \rfloor}}.\]
These relations quantify the degree-clustering complementarity and provide a bounded inequality framework for local structural heterogeneity.
Because \((k,n)\) pairs encode multiplicative harmonics, inequality results involving Dirichlet or Mellin transforms can be represented over the rook-divisibility grid. Defining \[\mathcal{D}(f,s) = \sum\limits_{(k,n)\in V_N} \frac{f(k,n)}{n^{s}},\] and using the inequality between harmonic and arithmetic averages of \(\tau(n)\) and \(\lfloor N/k \rfloor\), one may derive bounds such as \[\frac{\mathcal{D}(f,s)}{\lvert V_{N}\rvert} \leq \zeta(s)\, \max_{(k,n)\in V_N} f(k,n),\] where \(\zeta(s)\) denotes the Riemann zeta function. Thus, the rook-divisibility structure naturally embeds the inequality theory of multiplicative functions within a combinatorial lattice.
| Type | Formulation within Rook-Divisibility Network | Representative inequality |
| Convexity-based | Mean of row and column averages | \(\displaystyle \min f \leq \frac{A_n(f)+A_k(f)}{2} \leq \max f\) |
| Fractional / Integral | Weighted arithmetic mean with \(w_k,n=(k/n)^\alpha\) | \( f_\min \leq \mathcal{M}_\alpha(f;N)\leq \frac{1}{2}(\mathcal{M}_0+\mathcal{M}_1)\) |
| Combinatorial / Structural | Degree-clustering relation | \(C(k,n) \geq 1 – \dfrac{2\sqrt{(\tau(n)-1)(\lfloor N/k\rfloor-1)}}{\deg(k,n)-1}\) |
| Spectral / Transform-based | Dirichlet-Mellin representation | \(\mathcal{D}(f,s) \leq |V_N|\,\zeta(s)\,\max f(k,n)\) |
Hence, the rook-divisibility framework not only generalizes divisibility graphs but also generates a discrete analytical platform for inequality theory. It bridges the structure of arithmetic networks with the classical and fractional inequalities of convex analysis, yielding a unified approach to study functional bounds and network-based inequality formulations.
This work introduced a two-dimensional generalization of divisibility networks by embedding the classical one-dimensional integer graph into a lattice of ordered pairs \((k,n)\) satisfying the divisibility constraint \(k \mid n\). The resulting rook-divisibility network connects vertices that share either a common divisor index (column) or a common multiple index (row). This forms an analytically tractable model that captures both multiplicative and hierarchical dependencies in a deterministic manner.
The analysis established several structural properties and asymptotic laws that characterize the network:
1. Connectivity: The graph \(G_N\) is connected for all finite \(N\), and every vertex admits a projection path through the canonical spine \(\{(1,n)\}\), which forms a complete subgraph. This property ensures that the divisibility lattice remains fully navigable under rook-type adjacency.
2. Local statistics: Exact closed forms were derived for the degree and clustering coefficient, \[\deg(k,n) = \tau(n) + \big\lfloor \tfrac{N}{k} \big\rfloor – 2, \qquad C(k,n) = \frac{\binom{\tau(n)-1}{2} + \binom{\lfloor N/k \rfloor -1}{2}} {\binom{\tau(n) + \lfloor N/k \rfloor – 2}{2}},\] showing that high-degree nodes emerge both from small divisor indices \(k\) (dense columns) and highly composite rows \(n\).
3. Heavy-tailed degree behavior: Theorem 1 established that the degree distribution exhibits a heavy, non-exponential tail governed by a slowly varying logarithmic factor, \[\mathbb{P}(D \ge d) \asymp \frac{\log(N/d)}{\log N},\] consistent with numerical fits around slope \(\alpha \approx 1.43\). This reveals that the heavy-tail structure arises deterministically from the arithmetic multiplicity of columns.
4. Scaling laws: The average degree satisfies \[\langle k\rangle_N = \frac{\pi^2}{6}\,\frac{N}{\log N}\bigl(1+o(1)\bigr),\] implying that the 2D network grows much faster in density than its one-dimensional counterpart (\(\sim \log N\)). The local clustering spectrum remains high and nearly constant across degrees, verifying the small-world-like behavior within a deterministic arithmetic setting.
5. Empirical validation: Numerical experiments confirmed complete agreement between empirical and analytic clustering coefficients and demonstrated stretching similarity across increasing network sizes, reflecting a scale-invariant organization along both lattice dimensions.
That is, these results provide the first exact framework linking arithmetic divisor statistics with complex-network observables in two dimensions. The rook-divisibility network thus serves as a benchmark model where connectivity, degree heterogeneity, and clustering can all be computed exactly without randomness.
Several natural directions follow from the present formulation:
1. Spectral analysis and dynamics: Investigating the eigenvalue spectra of the adjacency and Laplacian matrices of \(G_N\) would reveal diffusion rates, mixing times, and potential analogues of spectral gaps known for small-world and scale-free networks.
2. Weighted and extended divisibility models: Variants in which edge weights depend on arithmetic functions (e.g., greatest common divisor, Euler’s \(\varphi\) function, or divisor depth) could introduce graded connectivity reflecting multiplicative strength.
3. Cross-divisibility extensions: A richer model could connect nodes \((k_1,n_1)\) and \((k_2,n_2)\) whenever \(k_1 \mid n_2\) or \(k_2 \mid n_1\), generating off-diagonal couplings that interpolate between 1D and 2D divisibility structures.
4. Continuum and limiting behavior: Exploring scaling limits as \(N \to \infty\) and mapping \(G_N\) to a continuum graphon or measure-based kernel on \([0,1]^2\) may establish connections with graph limit theory and continuous arithmetic networks.
5. Global metrics: Computing or bounding quantities such as average path length, diameter, and assortativity would extend the present local analysis to full-network organization and help quantify the extent of small-world behavior.
Pomerance, C. (1983). On the longest simple path in the divisor graph. In Proc. Southeastern Conf. Combinatorics, Graph Theory, and Computing. Congressus Numerantium, 40, 291–304.
Erdős, P., & Saias, É. (1995). Sur le graphe divisoriel. Acta Arithmetica, 73(2), 189–198.
Melotti, P., & Saias, É. (2020). On path partitions of the divisor graph. Acta Arithmetica, 192, 329–339.
McNew, N. (2021). Counting primitive subsets and other statistics of the divisor graph of {1,2,\(\ldots\),n}. European Journal of Combinatorics, 92, 103237.
Kumar, H., Patra, K. L., & Sahoo, B. K. (2020). Proper divisor graph of a positive integer. arXiv preprint arXiv:2005.04441.
Ravi, S. (2023). A brief survey on divisor graphs and divisor function graphs. Journal of Discrete Mathematical Sciences and Cryptography, 26(10), 2723–2748.
Shekatkar, S. M., Bhagwat, C., & Ambika, G. (2015). Divisibility patterns of natural numbers on a complex network. Scientific Reports, 5, 14280.
Garcı́a-Pérez, G., Serrano, M. Á., & Boguñá, M. (2014). Complex architecture of primes and natural numbers. Physical Review E, 90(2), 022806.
Yan, X.-Y., Wang, W.-X., Chen, G.-R., & Shi, D.-H. (2016). Multiplex congruence network of natural numbers. Scientific Reports, 6, 23714.
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393(6684), 440–442.
Barabási, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.
Clauset, A., Shalizi, C. R., & Newman, M. E. J. (2009). Power-law distributions in empirical data. SIAM Review, 51(4), 661–703.
Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press, UK.
Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45(2), 167–256.
Iguchi, K., & Yamada, H. (2005). Exactly solvable scale‐free network model. Physical Review E, 71(3), 036144.
Jiao, B., Nie, Y.-p., Shi, J., Huang, C.-d., Zhou, Y., Du, J., Guo, R., & Tao, Y. (2016). Scaling of weighted spectral distribution in deterministic scale‐free networks. Physica A: Statistical Mechanics and its Applications, 451, 632–645.
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2002). Pseudofractal scale‐free web. Physical Review E, 65(6), 066122.
Borgs, C., Chayes, J., Cohn, H., & Zhao, Y. (2018). Sparse exchangeable graphs and their limits via graphon processes. Journal of Machine Learning Research, 18, 1–98.
Alvarado, J., Wang, Y., & Ramon, J. (2023). Limits of multi-relational graphs. Machine Learning, 112, 177–216.
Khan, T. U., & Markarian, C. (2025). Existence and structure analysis of attractors for new delayed Kirchhoff-type suspension bridge equations under stochastic perturbations with applications. Ain Shams Engineering Journal, 16(11), 103691.
Bick, C., & Sclosa, D. (2025). Dynamical systems on graph limits and their symmetries. Journal of Dynamics and Differential Equations, 37(2), 1171–1206.
Jabin, P.-E., Poyato, D., & Soler, J. (2021). Mean-field limit of non-exchangeable systems. arXiv preprint arXiv:2112.15406.
