Diversity-normed spaces and diversity embeddings
Volume 267 / 2022
Abstract
The purpose of this paper is to extend some known metric embedding results to the setting of diversities introduced in [D. Bryant, P. F. Tupper, Adv. Math. 231 (2012), 3172–3198]. We first introduce diversity-normed spaces as a generalization of normed spaces and investigate their relationships with diversities. In particular, we introduce $ L_p $-diversity-normed spaces $ (1\leq p \leq \infty )$ which can be simultaneously considered as ($L_p$-)diversities. Then, for any $p$ $ (1 \leq p \leq \infty ) $, we investigate the possibility of embedding finite diversities and ultradiversities into $L_p$-diversities $ \ell _p^d $, for some positive integer $ d $, with some distortion. We present results analogous to the Bourgain theorem in the setting of both diversities and ultradiversities. We show that every diversity on $n$ points embeds in the diversities: (i) $\ell _p^{\mathcal {O}( \log n)}$ $(1\leq p \leq 2)$ with distortion $ \mathcal {O}(n \log ^{{(1+p)}/{p}}n) $; (ii) $\ell _p^{\mathcal {O}(\log ^{2}n)}$ $(2 \lt p \lt \infty )$ with distortion $\mathcal {O}(n \log ^{ {(2+p)}/{p}}n)$; (iii) $\ell _\infty ^{\mathcal {O}(\log ^2n)}$ with distortion $\mathcal {O}(n\log n)$. In addition, each ultradiversity embeds in the diversity $\ell _p^{\mathcal {O}( \log n)}$ $(1 \leq p \lt \infty )$ with distortion $ \mathcal {O}(\log ^{ {1}/{p}}n) $ as well as in $\ell _\infty ^{\mathcal {O}( \log n)}$ with constant distortion.