Bi-Lipschitz embedding properties of lamplighter graphs on weighted and unweighted trees

Abstract

In 2021, F. Baudier, P. Motakis, Th. Schlumprecht and A. Zsák proved that if a sequence $(G_k)_{k\in{\mathbb{N}}}$ of graphs contains the sequence of complete graphs with uniformly bounded distortion, then the sequence of lamplighter graphs on $G_k$'s contains Hamming cubes with uniformly bounded distortion and asked whether the converse holds.

They suggested that a sequence of trees with edges replaced by paths of "moderately growing" lengths may be a counterexample. We prove that indeed this is the case, and that a sequence of "moderately" weighted trees is another counterexample.

Further, we prove that diamond graphs do not embed with uniformly bounded distortion into lamplighter graphs on trees with edges replaced by paths with sufficiently fast growing lengths.