Bi-Lipschitz embedding properties of lamplighter graphs on weighted and unweighted trees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911284226686976 |
|---|---|
| author | Melby, Charlotte Randrianantoanina, Beata |
| author_facet | Melby, Charlotte Randrianantoanina, Beata |
| contents | In 2021 Baudier, Motakis, Schlumprecht, and Zsák proved that if a sequence of graphs
$(G_k)_{k\in{\mathbb{N}}}$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_25421 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bi-Lipschitz embedding properties of lamplighter graphs on weighted and unweighted trees Melby, Charlotte Randrianantoanina, Beata Functional Analysis Metric Geometry Primary: 46B85, Secondary: 05C12, 20F65, 30L05 In 2021 Baudier, Motakis, Schlumprecht, and Zsák proved that if a sequence of graphs $(G_k)_{k\in{\mathbb{N}}}$ 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. |
| title | Bi-Lipschitz embedding properties of lamplighter graphs on weighted and unweighted trees |
| topic | Functional Analysis Metric Geometry Primary: 46B85, Secondary: 05C12, 20F65, 30L05 |
| url | https://arxiv.org/abs/2509.25421 |