论文标题
分开关闭元素的排列
Permutations that separate close elements
论文作者
论文摘要
让$ n $为$ n \ geq 2 $的固定整数。对于$ i，j \ in \ mathbb {z} _n $，定义$ || i，j || _n $是$ i $和$ j $之间的距离，当$ \ mathbb {z} _n $的元素写成周期中。因此$ || i，j || _n = \ min \ {（i-j）\ bmod n，（j-i）\ bmod n \} $。对于积极的整数$ s $和$ k $，排列$π：\ mathbb {z} _n \ rightarrow \ mathbb {z} _n $是\ emph {$（s，k）$ - $ - clash-free}，如果$ ||π（i），π（j），π（j） $ i \ not = j $。因此，可以将$（s，k）$ - 无冲突排列$π$被认为是将$ \ mathbb {z} _n $的每对元素移动到大距离的一对。更几何而来，存在$（s，k）$ - 无冲突排列的存在等同于存在在$ n \ times n $ torus上的一组$ n $ non $ bulyplapping $ s \ times k $矩形，其中心具有独特的整数$ x $ coordinates和不同的integer $ y $ - $ y $ - $ -coordinates。 对于正整数$ n $和$ k $，带有$ k <n $，让$σ（n，k）$是$ s $的最大值，使得$（s，k）$ - 在$ \ mathbb {z} _n _ $上存在的无冲突置换。 In a recent paper, Mammoliti and Simpson conjectured that \[ \lfloor (n-1)/k\rfloor-1\leq σ(n,k)\leq \lfloor (n-1)/k\rfloor \] for all integers $n$ and $k$ with $k<n$.本文通过明确构建$（s，k）$ - 在$ \ mathbb {z} _n $上构建$（s，k）$ - 与$ s = \ lfloor（n-1）/k \ rfloor-1 $上的$（s，k）$ - 无冲突的排列来建立这种猜想。的确，这种结构用于建立更一般的猜想，对Mammoliti和Simpson进行了更一般的猜想，在这里，对于一些固定的整数$ r $，我们需要在最多$ r $矩形内部的圆环上的每个点。
Let $n$ be a fixed integer with $n\geq 2$. For $i,j\in\mathbb{Z}_n$, define $||i,j||_n$ to be the distance between $i$ and $j$ when the elements of $\mathbb{Z}_n$ are written in a cycle. So $||i,j||_n=\min\{(i-j)\bmod n,(j-i)\bmod n\}$. For positive integers $s$ and $k$, the permutation $π:\mathbb{Z}_n\rightarrow\mathbb{Z}_n$ is \emph{$(s,k)$-clash-free} if $||π(i),π(j)||_n\geq k$ whenever $||i,j||_n<s$ with $i\not=j$. So an $(s,k)$-clash-free permutation $π$ can be thought of as moving every close pair of elements of $\mathbb{Z}_n$ to a pair at large distance. More geometrically, the existence of an $(s,k)$-clash-free permutation is equivalent to the existence of a set of $n$ non-overlapping $s\times k$ rectangles on an $n\times n$ torus, whose centres have distinct integer $x$-coordinates and distinct integer $y$-coordinates. For positive integers $n$ and $k$ with $k<n$, let $σ(n,k)$ be the largest value of $s$ such that an $(s,k)$-clash-free permutation on $\mathbb{Z}_n$ exists. In a recent paper, Mammoliti and Simpson conjectured that \[ \lfloor (n-1)/k\rfloor-1\leq σ(n,k)\leq \lfloor (n-1)/k\rfloor \] for all integers $n$ and $k$ with $k<n$. The paper establishes this conjecture, by explicitly constructing an $(s,k)$-clash-free permutation on $\mathbb{Z}_n$ with $s=\lfloor (n-1)/k\rfloor-1$. Indeed, this construction is used to establish a more general conjecture of Mammoliti and Simpson, where for some fixed integer $r$ we require every point on the torus to be contained in the interior of at most $r$ rectangles.
