2011/10/31 by Pierre-Nicolas Jolissaint, Alain Valette
Computer Science · Mathematics · #Cayley graph #Eigenvalues and eigenvectors #Finite Group Theory Research #Finite graph #Graph #Graph theory and applications #Interconnection Networks and Systems #Upper and lower bounds #Vertex-transitive graph #math.CO #math.MG #msc:05C12 #msc:05C45 #msc:05C50
paper · pdf · doi:10.1112/blms/bdt096
arxiv created 2013/07/02 · openalex publication_date 2014/02/03 · openalex created_date 2016/06/24 · arxiv updated 2017/05/17 · openalex updated_date 2026/08/05
We give a lower bound for the L p -distortion c p ( X ) of finite graphs X, depending on the first eigenvalue λ 1 ( p ) ( X ) of the p-Laplacian and the maximal displacement of permutations of vertices. For a k-regular vertex-transitive graph it takes the form c p ( X ) p ⩾ diam ( X ) p λ 1 ( p ) ( X ) 2 p − 1 k . This bound is optimal for expander families and, for p = 2 , it gives the exact value for cycles and hypercubes. As new applications we give non-trivial lower bounds for the L 2 -distortion for families of Cayley graphs of the finite lamplighter groups C 2 ≀ C n d ( d ⩾ 2 fixed), and for a family of Cayley graphs of SL n ( q ) ( q fixed, n ⩾ 2 ) with respect to a standard two-element generating set. An application to the L 2 -compression of certain box spaces is also given.