论文标题
$ [1，n] $的排列和除数图
Permutations and the divisor graph of $[1,n]$
论文作者
论文摘要
令$ s _ {\ rm div}（n）$表示$ n $的排列$π$，以便每$ 1 \ leq j \ leq j \ leq n $ $ $ j \midπ（j）$或$π（j）\ j）\ mid j $。这些排列也可以看作是Divisor图$ \ MATHCAL {D} _ {[[1，N]} $的顶点 - 单位的定向周期封面，即Vertices $ v_1，\ ldots，v_n $，v_n $，带有$ v_i $和$ v_i $和$ v_j $和$ v_j $ i \ i \ i \ i \ i \ i \ i \ i \ i \ i \ i \ i \ j $ j $ j $ j $ j \ mid $ i $ i $ i $ i i i i i i。我们通过显示$ c_d = \ lim_ {n \ to \ infty} \ left（\＃s _ {\ rm div}（n）\ right）^{1/n} $来改善Pomerance的最新结果。我们还获得了集合的$ s _ {\ rm lcm}（n）$的相似结果，其中$ {\ rm lcm}（j，j，π（j））\ leq n $ for hast $ j $。结果依赖于图的理论结果，界定了顶点 - 偶有定向周期盖的数量，这可能具有独立感兴趣。
Let $S_{\rm div}(n)$ denote the set of permutations $π$ of $n$ such that for each $1\leq j \leq n$ either $j \mid π(j)$ or $π(j) \mid j$. These permutations can also be viewed as vertex-disjoint directed cycle covers of the divisor graph $\mathcal{D}_{[1,n]}$ on vertices $v_1, \ldots, v_n$ with an edge between $v_i$ and $v_j$ if $i\mid j$ or $j \mid i$. We improve on recent results of Pomerance by showing $c_d = \lim_{n \to \infty }\left(\# S_{\rm div}(n)\right)^{1/n}$ exists and that $2.069<c_d<2.694$. We also obtain similar results for the set $S_{\rm lcm}(n)$ of permutations where ${\rm lcm}(j,π(j))\leq n$ for all $j$. The results rely on a graph theoretic result bounding the number of vertex-disjoint directed cycle covers, which may be of independent interest.
