Free Access

Expanders and right-angled Artin groups

Department of Geometry and Topology, University of Seville, Spain

Department of Computer Science, Queens College, CUNY, Queens, NY, United States of America

Department of Mathematics, Queens College, CUNY, Queens, NY, United States of America

New York University, Tandon School of Engineering, PhD Program in Computer Science, CUNY Graduate Center, United States of America

Department of Computer Science, University of York, United Kingdom

E-mail Address: dk2572@nyu.edu

E-mail Address: dkahrobaei@gc.cuny.edu

Search for more papers by this author

, and

Thomas Koberda

https://orcid.org/0000-0001-5465-2651

Department of Mathematics, University of Virginia, Charlottesville, VA 22904, United States of America

E-mail Address: thomas.koberda@gmail.com

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S179352532150059XCited by:4 (Source: Crossref)

Abstract

The purpose of this paper is to give a characterization of families of expander graphs via right-angled Artin groups. We prove that a sequence of simplicial graphs ${Γ_{i}}_{i \in ℕ}$ forms a family of expander graphs if and only if a certain natural mini-max invariant arising from the cup product in the cohomology rings of the groups ${A (Γ_{i})}_{i \in ℕ}$ agrees with the Cheeger constant of the sequence of graphs, thus allowing us to characterize expander graphs via cohomology. This result is proved in the more general framework of vector space expanders, a novel structure consisting of sequences of vector spaces equipped with vector-space-valued bilinear pairings which satisfy a certain mini-max condition. These objects can be considered to be analogues of expander graphs in the realm of linear algebra, with a dictionary being given by the cup product in cohomology, and in this context represent a different approach to expanders that those developed by Lubotzky–Zelmanov and Bourgain–Yehudayoff.

Keywords:

AMSC: 20F36, 05C48, 05C50, 20J06

References

1. N. Alon , Eigenvalues and expanders, Theory of Computing, Vol. 6 (Singer Island, Fla., 1984), pp. 83–96. Google Scholar
2. J. Bourgain , Expanders and dimensional expansion, C. R. Math. Acad. Sci. Paris 347 (2009) 357–362. Crossref, Google Scholar
3. J. Bourgain and A. Yehudayoff , Expansion in ${SL}_{2} (ℝ)$ and monotone expanders, Geom. Funct. Anal. 23 (2013) 1–41. Crossref, Google Scholar
4. N. Brady and J. Meier , Connectivity at infinity for right angled Artin groups, Trans. Amer. Math. Soc. 353 (2001) 117–132. Crossref, Google Scholar
5. P. Cartier and D. Foata , Problèmes Combinatoires de Commutation et Réarrangements, Lecture Notes in Mathematics, Vol. 85 (Springer-Verlag, Berlin, New York, 1969). Crossref, Google Scholar
6. Denis X. Charles, Kristin E. Lauter and Eyal Z. Goren , Cryptographic hash functions from expander graphs, J. Cryptol. 22 (2009) 93–113. Crossref, Google Scholar
7. R. Charney , An introduction to right-angled Artin groups, Geom. Dedicata 125 (2007) 141–158. Crossref, Google Scholar
8. J. Crisp, E. Godelle and B. Wiest , The conjugacy problem in subgroups of right-angled Artin groups, J. Topol. 2 (2009) 442–460. Crossref, Google Scholar
9. M. W. Davis , The cohomology of a Coxeter group with group ring coefficients, Duke Math. J. 91 (1998) 297–314. Crossref, Google Scholar
10. C. Droms , Isomorphisms of graph groups, Proc. Amer. Math. Soc. 100 (1987) 407–408. Crossref, Google Scholar
11. R. Flores, D. Kahrobaei and T. Koberda , Algorithmic problems in right-angled Artin groups: Complexity and applications, J. Algebra 519 (2019) 111–129. Crossref, Google Scholar
12. R. Flores, D. Kahrobaei and T. Koberda , An algebraic characterization of $k$ -colorability, Proc. Amer. Math. Soc. 149 (2021) 2249–2255. Crossref, Google Scholar
13. O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan and D. Zuckerman , Security preserving amplification of hardness, in 31st Annual Symp. Foundations of Computer Science, Vol. 1, 2 (St. Louis, MO, 1990) (IEEE Computer Society Press, Los Alamitos, CA, 1990), pp. 318–326. Crossref, Google Scholar
14. S. Hermiller and J. Meier , Algorithms and geometry for graph products of groups, J. Algebra 171 (1995) 230–257. Crossref, Google Scholar
15. S. Hermiller and Z. Šunić , Poly-free constructions for right-angled Artin groups, J. Group Theory 10 (2007) 117–138. Crossref, Google Scholar
16. S. Hoory, N. Linial and A. Wigderson , Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006) 439–561. Crossref, Google Scholar
17. C. Jensen and J. Meier , The cohomology of right-angled Artin groups with group ring coefficients, Bull. London Math. Soc. 37 (2005) 711–718. Crossref, Google Scholar
18. M. Kambites , On commuting elements and embeddings of graph groups and monoids, Proc. Edinb. Math. Soc. 52 (2009) 155–170. Crossref, Google Scholar
19. S.-H. Kim and T. Koberda , Embeddability between right-angled Artin groups, Geom. Topol. 17 (2013) 493–530. Crossref, Google Scholar
20. S.-H. Kim and T. Koberda , Free products and the algebraic structure of diffeomorphism groups, J. Topol. 11 (2018) 1054–1076. Crossref, Google Scholar
21. T. Koberda, Geometry and combinatorics via right-angled Artin groups, preprint (2003), arXiv:2103.09342. Google Scholar
22. T. Koberda , Right-angled Artin groups and a generalized isomorphism problem for finitely generated subgroups of mapping class groups, Geom. Funct. Anal. 22 (2012) 1541–1590. Crossref, Google Scholar
23. E. Kowalski, An introduction to expander graphs, Cours Spécialisés [Specialized Courses], Vol. 26, Société Mathématique de France, Paris, 2019. Google Scholar
24. A. Lubotzky , Discrete Groups, Expanding Graphs and Invariant Measures, Modern Birkhäuser Classics (Birkhäuser Verlag, Basel, 2010). Google Scholar
25. A. Lubotzky , High dimensional expanders, in Proc. Int. Cong. Mathematicians—Rio de Janeiro 2018, Plenary Lectures, Vol. 1 (World Scientific Publication, Hackensack, New Jersey, 2018), pp. 705–730. Google Scholar
26. A. Lubotzky , Ralph Phillips, and Peter Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261–277. Crossref, Google Scholar
27. A. Lubotzky and E. Zelmanov , Dimension expanders, J. Algebra 319 (2008) 730–738. Crossref, Google Scholar
28. L. Sabalka , On rigidity and the isomorphism problem for tree braid groups, Groups Geom. Dyn. 3 (2009) 469–523. Crossref, Google Scholar
29. H. Servatius , Automorphisms of graph groups, J. Algebra 126 (1989) 34–60. Crossref, Google Scholar