Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Bi-Lipschitz Geometry of Lamplighter Graphs

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

In this article we start a systematic study of the bi-Lipschitz geometry of lamplighter graphs. We prove that lamplighter graphs over trees bi-Lipschitzly embed into Hamming cubes with distortion at most 6. It follows that lamplighter graphs over countable trees bi-Lipschitzly embed into \(\ell _1\). We study the metric behaviour of the operation of taking the lamplighter graph over the vertex-coalescence of two graphs. Based on this analysis, we provide metric characterisations of superreflexivity in terms of lamplighter graphs over star graphs or rose graphs. Finally, we show that the presence of a clique in a graph implies the presence of a Hamming cube in the lamplighter graph over it. An application is a characterisation, in terms of a sequence of graphs with uniformly bounded degree, of the notion of trivial Bourgain–Milman–Wolfson type for arbitrary metric spaces, similar to Ostrovskii’s characterisation previously obtained in Ostrovskii (C. R. Acad. Bulgare Sci. 64(6), 775–784 (2011)).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Austin, T., Naor, A., Valette, A.: The Euclidean distortion of the lamplighter group. Discrete Comput. Geom. 44(1), 55–74 (2010)

    Article  MathSciNet  Google Scholar 

  2. Bollobás, B.: Modern Graph Theory. Graduate Texts in Mathematics, vol. 184. Springer, New York (1998)

    Book  Google Scholar 

  3. Bourgain, J.: The metrical interpretation of superreflexivity in Banach spaces. Isr. J. Math. 56(2), 222–230 (1986)

    Article  MathSciNet  Google Scholar 

  4. Bourgain, J., Milman, V., Wolfson, H.: On type of metric spaces. Trans. Am. Math. Soc. 294(1), 295–317 (1986)

    Article  MathSciNet  Google Scholar 

  5. Cornulier, Y., Stalder, Y., Valette, A.: Proper actions of wreath products and generalizations. Trans. Am. Math. Soc. 364(6), 3159–3184 (2012)

    Article  MathSciNet  Google Scholar 

  6. Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997)

    Book  Google Scholar 

  7. Donno, A.: Generalized wreath products of graphs and groups. Graphs Comb. 31(4), 915–926 (2015)

    Article  MathSciNet  Google Scholar 

  8. Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.): Handbook of Discrete and Computational Geometry. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton (2018)

  9. James, R.C.: A nonreflexive Banach space that is uniformly nonoctahedral. Isr. J. Math. 18, 145–155 (1974)

    Article  MathSciNet  Google Scholar 

  10. James, R.C.: Nonreflexive spaces of type \(2\). Isr. J. Math. 30(1–2), 1–13 (1978)

    Article  MathSciNet  Google Scholar 

  11. Kaĭmanovich, V.A., Vershik, A.M.: Random walks on discrete groups: boundary and entropy. Ann. Probab. 11(3), 457–490 (1983)

    Article  MathSciNet  Google Scholar 

  12. Lee, J.R., Naor, A., Peres, Y.: Trees and Markov convexity. Geom. Funct. Anal. 18(5), 1609–1659 (2009)

    Article  MathSciNet  Google Scholar 

  13. Linial, N., Magen, A.: Least-distortion Euclidean embeddings of graphs: products of cycles and expanders. J. Comb. Theory Ser. B 79(2), 157–171 (2000)

    Article  MathSciNet  Google Scholar 

  14. Lyons, R., Pemantle, R., Peres, Y.: Random walks on the lamplighter group. Ann. Probab. 24, 1993–2006 (1996)

    Article  MathSciNet  Google Scholar 

  15. Mendel, M., Naor, A.: Metric cotype. Ann. Math. 168, 247–298 (2008)

    Article  MathSciNet  Google Scholar 

  16. Naor, A.: \(L_1\) embeddings of the Heisenberg group and fast estimation of graph isoperimetry. In: Proceedings of the International Congress of Mathematicians, vol. 3, pp. 1549–1575. Hindustan Book Agency, New Delhi (2010)

  17. Naor, A., Peres, Y.: Embeddings of discrete groups and the speed of random walks. Int. Math. Res. Not. IMRN 2008, # rnn076 (2008)

  18. Naor, A., Peres, Y.: \(L_p\) compression, traveling salesmen, and stable walks. Duke Math. J. 157(1), 53–108 (2011)

    Article  MathSciNet  Google Scholar 

  19. Ostrovskii, M.I.: On metric characterizations of some classes of Banach spaces. C. R. Acad. Bulgare Sci. 64(6), 775–784 (2011)

    MathSciNet  MATH  Google Scholar 

  20. Ostrovskii, M.I.: Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs. Anal. Geom. Metric Spaces 2(1), 154–168 (2014)

    MathSciNet  MATH  Google Scholar 

  21. Ostrovskii, M.I., Randrianantoanina, B.: A characterization of superreflexivity through embeddings of lamplighter groups. Proc. Am. Math. Soc. 147(11), 4745–4755 (2019)

    Article  MathSciNet  Google Scholar 

  22. Pisier, G., Xu, Q.H.: Random series in the real interpolation spaces between the spaces \(v_p\). In: Geometrical Aspects of Functional Analysis (1985/86). Lecture Notes in Math., vol. 1267, pp. 185–209. Springer, Berlin (1987)

  23. Stein, M., Taback, J.: Metric properties of Diestel–Leader groups. Mich. Math. J. 62(2), 365–386 (2013)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank the referees for their careful reading and the many suggestions that helped improve the exposition and clarity of the paper.

Author information

Authors and Affiliations

  1. Department of Mathematics, Texas A&M University, College Station, TX, 77843, USA

    F. Baudier & Th. Schlumprecht

  2. Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL, 61801, USA

    P. Motakis

  3. Faculty of Electrical Engineering, Czech Technical University in Prague, Zikova 4, 166 27, Prague, Czech Republic

    Th. Schlumprecht

  4. Peterhouse, Cambridge, CB2 1RD, UK

    A. Zsák

Authors
  1. F. Baudier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Motakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Th. Schlumprecht
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. A. Zsák
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to F. Baudier.

Additional information

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

F. Baudier was supported by the National Science Foundation under Grant Number DMS-1800322. P. Motakis was supported by National Science Foundation under Grant Numbers DMS-1600600 and DMS-1912897. Th. Schlumprecht was supported by the National Science Foundation under Grant Numbers DMS-1464713 and DMS-1711076. A. Zsák was supported by the 2018 Workshop in Analysis and Probability at Texas A&M University.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Baudier, F., Motakis, P., Schlumprecht, T. et al. On the Bi-Lipschitz Geometry of Lamplighter Graphs. Discrete Comput Geom 66, 203–235 (2021). https://doi.org/10.1007/s00454-020-00184-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-020-00184-1

Keywords

Mathematics Subject Classification

Search

Navigation