  A distortion lower bound of $\Omega(\log(h)^{1/p})$ is proven for embedding
the complete countably branching hyperbolic tree of height $h$ into a Banach
space admitting an equivalent norm satisfying property $(\beta)$ of Rolewicz
with modulus of power type $p\in(1,\infty)$ (in short property ($\beta_p$)).
Also it is shown that a distortion lower bound of $\Omega(\ell^{1/p})$ is
incurred when embedding the parasol graph with $\ell$ levels into a Banach
space with an equivalent norm with property ($\beta_p$). The tightness of the
lower bound for trees is shown adjusting a construction of Matou\v{s}ek to the
case of infinite trees. It is also explained how our work unifies and extends a
series of results about the stability under nonlinear quotients of the
asymptotic structure of infinite-dimensional Banach spaces. Finally two other
applications regarding metric characterizations of asymptotic properties of
Banach spaces, and the finite determinacy of bi-Lipschitz embeddability
problems are discussed.

Metric Geometry;Functional Analysis