Diameters, distortion, and eigenvalues

DOI10.1016/J.EJC.2012.03.019MaRDI QIDQ444413zbMATH OpenOpenAlexFDO

Authors Piotr W. Nowak, R. I. Grigorchuk

Publication date 14 August 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.2560

zbMATH Keywords

Cayley graphsdiametereigenvalueLaplacianSierpinski gasketspectral gapdistortionSchreier graphsPascal graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: We study the relation between the diameter, the first positive eigenvalue of the discrete $p$-Laplacian and the $el{l}_p$-distortion of a finite graph. We prove an inequality relating these three quantities and apply it to families of Cayley and Schreier graphs. We also show that the $el{l}_p$-distortion of Pascal graphs, approximating the Sierpinski gasket, is bounded, which allows to obtain estimates for the convergence to zero of the spectral gap as an application of the main result.

Recommendations

• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
• A Family of Diameter-Based Eigenvalue Bounds for Quantum Graphs
• On the spectral gap and the diameter of Cayley graphs
• scientific article; zbMATH DE number 2191998
• Eigenvalue estimates of the \(p\)-Laplacian on finite graphs

Cites work

• scientific article; zbMATH DE number 1574582 (Why is no real title available?)
• scientific article; zbMATH DE number 1984019 (Why is no real title available?)
• scientific article; zbMATH DE number 1544074 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 2156384 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• "MÜNCHHAUSEN TRICK" AND AMENABILITY OF SELF-SIMILAR GROUPS
• Asymptotic aspects of Schreier graphs and Hanoi Towers groups.
• Automata, dynamical systems, and groups
• Bounds for the largest \(p\)-Laplacian eigenvalue for graphs
• DIAMOND GRAPHS AND SUPER-REFLEXIVITY
• Diameters and Eigenvalues
• Girth and Euclidean distortion
• Groups of intermediate growth: an introduction.
• Harmonic analysis on the Pascal graph
• Laplacians on the basilica Julia set
• Largest eigenvalues of the discrete p-Laplacian of trees with degree sequences
• ON A TORSION-FREE WEAKLY BRANCH GROUP DEFINED BY A THREE STATE AUTOMATON
• Old and new results on algebraic connectivity of graphs
• On Burnside's problem on periodic groups
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On the spectrum of Hecke type operators related to some fractal groups
• Schreier graphs of the Basilica group.
• Schreier spectrum of the Hanoi Towers group on three pegs
• Self-similarity and branching in group theory.
• Spectral analysis on infinite Sierpiński gaskets
• The Euclidean distortion of the lamplighter group.
• The diameter and Laplacian eigenvalues of directed graphs
• The geometry of graphs and some of its algorithmic applications
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum
• The spectral problem, substitutions and iterated monodromy.
• The spectrum of the \(p\)-Laplacian and \(p\)-harmonic morphisms on graphs
• The tower of Hanoi
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(11)

• Poincaré inequalities and rigidity for actions on Banach spaces
• scientific article; zbMATH DE number 1000519 (Why is no real title available?)
• Eigenvalues and diameter
• On the spectral gap and the diameter of Cayley graphs
• Eigenvalues of Cayley graphs
• On distortions of the transfinite diameter of disk image
• scientific article; zbMATH DE number 26331 (Why is no real title available?)
• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
• An average John theorem
• Speed of random walks, isoperimetry and compression of finitely generated groups
• Automorphism groups of simplicial complexes and rigidity for uniformly bounded representations

This page was built for publication: Diameters, distortion, and eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444413)