Stochastic embeddings of graphs into trees

It is known that every graph with n vertices embeds stochastically into trees with distortion \(O(\log n)\) $O(logn)$ . In this paper, we show that this upper bound is sharp for a large class of graphs. As this class of graphs contains Laakso graphs, this result extends known examples that obtain this largest possible stochastic distortion.