##### Department of Mathematics,

University of California San Diego

****************************

### Math 288 - Probability & Statistics

## Garrett Tresch

#### Texas A&M University

## Stochastic Embeddings of Graphs into Trees

##### Abstract:

As the shortest path metric on a weighted tree can be embedded isometrically into a finite $\ell_1$ space, a Lipschitz embedding of a given graph into $\ell_1$ can be obtained by constructing a low distortion embedding into a tree. Conversely, while there are various topological properties of graphs that guarantee controlled distortion Lipschitz embeddings into $\ell_1$ ($k$-outerplanar, series-parallel, low Euler characteristic), it is still often the case that such a graph embeds quite poorly into a tree.

By introducing the notion of a stochastic embedding into a family of trees one can find more general concrete embeddings into $\ell_1$ then those limited by a single tree. In fact, it is known that every graph with n vertices embeds stochastically into trees with distortion O(log(n)). Nevertheless, this upper bound is sharp for graphs such as expanders, grids and, by a recent joint work with Schlumprecht, a large class of "fractal-like" series-parallel graphs called slash powers.

In this talk we introduce an equivalent characterization of stochastic distortion called expected distortion and after proving a mild extension of a result of Gupta regarding poor tree embeddings of a cycle, inductively lower bound the expected distortion of generalized Laakso graphs found in most nontrivial slash power families.

Host: Chris Gartland

### May 16, 2024

### 11:00 AM

APM 6402** **https://ucsd.zoom.us/j/

****************************