Lipschitz constant $\log n$ almost surely suffices for mapping $n$ grid points onto a cube

Abstract

Kaluža, Kopecká and the author have shown that the best Lipschitz constant for mappings taking a given $n^d$-element set in the integer lattice ${\mathbb{Z}}^d$, with $n\in \mathbb{N}$, surjectively to the regular $n$ times $n$ grid ${\left\{1,\dots ,n\right\}}^d$ may be arbitrarily large. However, there remain no known, non-trivial asymptotic bounds, either from above or below, on how this best Lipschitz constant grows with $n$. We approach this problem from a probabilistic point of view. More precisely, we consider the random configuration of $n^d$ points inside a given finite lattice and establish almost sure, asymptotic upper bounds of order $\log n$ on the best Lipschitz constant of mappings taking this set surjectively to the regular $n$ times $n$ grid ${\left\{1,\dots ,n\right\}}^d$.

17 pages, main result reformulated and several minor corrections and improvements. To appear in PAFA

References in corpus (1)

• Mapping $n$ grid points onto a square forces an arbitrarily large Lipschitz constant