On Lipschitz extension from finite subsets (Q2357002)

The paper contains two main results. The first main result is the estimate \(\mathfrak{ae}(n)\geq c\sqrt{\log n}\) (\(c>0\) is an absolute constant), where \(\mathfrak{ae}(n)\) is the absolute extendability constant. This improves the previous estimate \(\mathfrak{ae}(n)\geq c\sqrt{\log n/\log\log n}\) of \textit{W. B. Johnson} and \textit{J. Lindenstrauss} [Contemp. Math. 26, 189--206 (1984; Zbl 0539.46017)]. Without the \(\mathfrak{ae}\) notation, the result can be stated as: ``for every \(n\in\mathbb{N}\) there exists a metric space \((X,d_X)\), an \(n\)-point subset \(S\subset X\), a Banach space \((Z,\|\cdot\|_Z)\) and a \(1\)-Lipschitz function \(f:S\to Z\) such that the Lipschitz constant of every function \(F:X\to Z\) that extends \(f\) is at least a constant multiple of \(\sqrt{\log n}\).'' The importance of this result is not only in the removal of the \(\log\log n\) term in the denominator, but also in the designing of a different approach. The approach of Johnson and Lindenstrauss was based on discretization of a result on non-existence of an extension for linear maps. The authors of the present paper show that such a discretization-of-linear approach cannot lead to the lower bound \(c\sqrt{\log n}\). In this paper, the space \(X\) is an expander graph with \(k\) vertices and \(S\) is any of its subsets of size \(k/\sqrt{\log k}\) (the size of \(S\) is denoted by \(n\)). The metric of \(X\) is the so-called magnification of the graph distance of \(X\) at \(S\) (this means that distances between pairs containing elements of \(X\) are somewhat increased if one or both elements of the pair are in \(S\)), the Banach space \(Z\) is the space of real-valued functions on \(S\) with zero sum, endowed with the Wasserstein \(1\) norm (this space is also known as the Lipschitz free space on \(S\) or the Arens-Eells space on \(S\)). The second main result of the paper is a quantitative counterpart to the extension theorem of \textit{G. J. Minty} [Bull. Amer. Math. Soc. 76, 334--339 (1970; Zbl 0191.34603)]. Namely, the authors prove that, for every \(\alpha\in (1/2,1]\) and \(n\in \mathbb{N}\), there exists a metric space \((X,d_X)\), an \(n\)-point subset \(S\subset X\) and a function \(f:S\to \ell_2\) that is \(\alpha\)-Hölder with constant~\(1\), yet the \(\alpha\)-Hölder constant of any \(F:X\to \ell_2\) that extends \(f\) is at least \[ (\log n)^{\frac{2\alpha-1}{4\alpha}}+\left(\frac{\log n}{\log\log n}\right)^{\alpha^2-\frac12}. \] This part uses the discretization approach of Johnson and Lindenstrauss [loc. cit], twisted hypercubes in the spirit of \textit{W. B. Johnson} et al. [Isr. J. Math. 54, 129--138 (1986; Zbl 0626.46007)] and the Bourgain-Begun almost extension lemma [\textit{J. Bourgain}, Lect. Notes Math. 1267, 157--167 (1987; Zbl 0633.46018); \textit{B. Begun}, Isr. J. Math. 109, 151--155 (1999; Zbl 0944.46038)]. The second part of Section 1 contains a very interesting extensive discussion of related open problems and conjectures.