Stochastic embeddings of finite metric spaces into graph-theoretic trees have proven to be a vital tool for constructing approximation algorithms in theoretical computer science. In the present work, we build out some of the basic theory of stochastic embeddings in the infinite setting with an aim toward applications to Lipschitz free space theory. We prove that proper metric spaces stochastically embedding into $\mathbb {R}$-trees have Lipschitz free spaces isomorphic to $L^1$-spaces. We then undergo a systematic study of stochastic embeddability of Gromov hyperbolic metric spaces into $\mathbb {R}$-trees by way of stochastic embeddability of their boundaries into ultrametric spaces. The following are obtained as our main results: (1) every snowflake of a compact, finite Nagata-dimensional metric space stochastically embeds into an ultrametric space and has Lipschitz free space isomorphic to $\ell ^1$, (2) the Lipschitz free space over hyperbolic n-space is isomorphic to the Lipschitz free space over Euclidean n-space and (3) every infinite, finitely generated hyperbolic group stochastically embeds into an $\mathbb {R}$-tree, has Lipschitz free space isomorphic to $\ell ^1$, and admits a proper, uniformly Lipschitz affine action on $\ell ^1$.

Given a Gromov hyperbolic domain $G\subsetneq \mathbb{R}^n$ with uniformly perfect Gromov boundary, Zhou and Rasila recently proved that for all quasiconformal homeomorphisms $\psi\colon G\to G$ with identity value on the Gromov boundary, the quasihyperbolic displacement $k_G(x,\psi(x))$ for all $x\in G$ is bounded above. In this paper, we generalize this result and establish Teichmüller displacement theorem for quasi-isometries of Gromov hyperbolic spaces in a quantitative way. As applications, we obtain its connections to bilipschitz extensions of certain Gromov hyperbolic spaces.

We define balanced self-similar quasi-round carpets and compare the carpet moduli of some path families relating to such a carpet. Then, using some known results on quasiconformal geometry of carpets, we prove that the group of quasisymmetric self-homeomorphisms of every balanced self-similar quasi-round carpet is finite. Furthermore, we prove that some balanced self-similar carpets in the unit square with strong geometric symmetry are quasisymmetrically rigid by using the quasisymmetry of weak tangents of carpets.

To every finite metric space X, including all connected unweighted graphs with the minimum edge-distance metric, we attach an invariant that we call its blowup-polynomial $p_X(\{ n_x : x \in X \})$. This is obtained from the blowup $X[\mathbf {n}]$ – which contains $n_x$ copies of each point x – by computing the determinant of the distance matrix of $X[\mathbf {n}]$ and removing an exponential factor. We prove that as a function of the sizes $n_x$, $p_X(\mathbf {n})$ is a polynomial, is multi-affine, and is real-stable. This naturally associates a hitherto unstudied delta-matroid to each metric space X; we produce another novel delta-matroid for each tree, which interestingly does not generalize to all graphs. We next specialize to the case of $X = G$ a connected unweighted graph – so $p_G$ is “partially symmetric” in $\{ n_v : v \in V(G) \}$ – and show three further results: (a) We show that the polynomial $p_G$ is indeed a graph invariant, in that $p_G$ and its symmetries recover the graph G and its isometries, respectively. (b) We show that the univariate specialization $u_G(x) := p_G(x,\dots ,x)$ is a transform of the characteristic polynomial of the distance matrix $D_G$; this connects the blowup-polynomial of G to the well-studied “distance spectrum” of G. (c) We obtain a novel characterization of complete multipartite graphs, as precisely those for which the “homogenization at $-1$” of $p_G(\mathbf { n})$ is real-stable (equivalently, Lorentzian, or strongly/completely log-concave), if and only if the normalization of $p_G(-\mathbf { n})$ is strongly Rayleigh.

Main results of the paper are as follows:

(1) For any finite metric space $M$ the Lipschitz-free space on $M$ contains a large well-complemented subspace that is close to $\ell _{1}^{n}$.

(2) Lipschitz-free spaces on large classes of recursively defined sequences of graphs are not uniformly isomorphic to $\ell _{1}^{n}$ of the corresponding dimensions. These classes contain well-known families of diamond graphs and Laakso graphs.

Interesting features of our approach are: (a) We consider averages over groups of cycle-preserving bijections of edge sets of graphs that are not necessarily graph automorphisms. (b) In the case of such recursive families of graphs as Laakso graphs, we use the well-known approach of Grünbaum (1960) and Rudin (1962) for estimating projection constants in the case where invariant projections are not unique.

For a fixed $K\,\gg \,1$ and $n\,\in \,\mathbb{N}$, $n\,\gg \,1$ we study metric spaces which admit embeddings with distortion $\le \,K$ into each $n$-dimensional Banach space. Classical examples include spaces embeddable into log $n$-dimensional Euclidean spaces, and equilateral spaces.

We prove that good embeddability properties are preserved under the operation of metric composition of metric spaces. In particular, we prove that $n$-point ultrametrics can be embedded with uniformly bounded distortions into arbitrary Banach spaces of dimension $\log \,n$.

The main result of the paper is a new example of a family of finite metric spaces which are not metric compositions of classical examples and which do embed with uniformly bounded distortion into any Banach space of dimension $n$. This partially answers a question of G. Schechtman.