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

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 ℤ^d, with n∈ℕ, surjectively to the regular n times n grid {1,…,n}^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 {1,…,n}^d.