Stochastic Embeddings of Graphs into Trees

Th. Schlumprecht, Garrett Tresch

It is known that every graph with n vertices embeds stochastically into trees with distortion $O(\log n)$. In this paper, we show that this upper bound is sharp for a large class o…