Lower Bounds for Embedding Graphs into Graphs of Smaller Characteristic

摘要

The subject of graph embeddings deals with embedding a finite point set in a given metric space by points in another target metric space in such a way that distances in the new space are at least, but not too much more, than distances in the old space. The largest new distance to old distance ratio over all pairs of points is called the distortion of the embedding. In this paper, we will study the distortion dist(G,H) while embedding metrics supported on a given graph G into metrics supported on a graph H of lower characteristic, where the characteristic χ(H) of a graph H is the quantity E -V + 1 (E is the number of edges and V is the number of vertices in H). We will prove the following lower bounds for such embeddings which generalize and improve lower bounds given in [10]. -If |G| = |H| and χ(G) - χ(H) = k, dist(G, H) ≥ gk - 1 -If χ(G) - χ(H) = k, dist(G, H) ≥ (gk-4)/3 Further, we will also give an alternative proof for lower bounding the distortion when probabilistically embedding expander graphs into tree metrics. in addition, we also generalize this lower bound to the case when expander graphs probabilistically embed into graphs of constant characteristic.