Mapping \(n\) grid points onto a square forces an arbitrarily large Lipschitz constant (Q724264)

The authors answer negatively the following open question by U. Feige: Is there a constant \(L>0\) such that for every \(n\in\mathbb{N}\) and every set \(S\subset\mathbb{Z}^2\) with cardinality \(|S|=n^2\) there is a bijection \(f:S\to\{1,2,\dots,n\}^2\) with Lipschitz constant \(\text{Lip}(f)\leq L\)? The solution of the problem takes place largely in a continuous setting and is based on some new results for Lipschitz mappings falling into two broad areas of interest, studied independently. Firstly, they present detailed investigation on Lipschitz regular mappings on Euclidean spaces, with emphasis on their bi-Lipschitz decomposability. Secondly, they build on work of \textit{D. Burago} and \textit{B. Kleiner} [Geom. Funct. Anal. 8, No. 2, 273--282 (1998; Zbl 0902.26004)], as well as \textit{C. T. McMullen} [Geom. Funct. Anal. 8, No. 2, 304--314 (1998; Zbl 0941.37030)] on non-realisable densities. The results and proofs are too involved to be presented here.