Diameters, distortion, and eigenvalues

DOI10.1016/J.EJC.2012.03.019zbMATH Open1246.05046arXiv1005.2560OpenAlexW2963733245MaRDI QIDQ444413FDOQ444413

Authors: Piotr W. Nowak, R. I. Grigorchuk 

Publication date: 14 August 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On Burnside's problem on periodic groups
• The geometry of graphs and some of its algorithmic applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Laplacians on the basilica Julia set
• Title not available (Why is that?)
• Automata, dynamical systems, and groups
• The lamplighter group as a group generated by a 2-state automaton, and its spectrum
• Old and new results on algebraic connectivity of graphs
• On the spectrum of Hecke type operators related to some fractal groups
• Diameters and Eigenvalues
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Spectral analysis on infinite Sierpiński gaskets
• The spectrum of the \(p\)-Laplacian and \(p\)-harmonic morphisms on graphs
• Harmonic analysis on the Pascal graph
• The tower of Hanoi
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Girth and Euclidean distortion
• Schreier graphs of the Basilica group.
• Bounds for the largest \(p\)-Laplacian eigenvalue for graphs
• 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
• Groups of intermediate growth: an introduction.
• Asymptotic aspects of Schreier graphs and Hanoi Towers groups.
• "MÜNCHHAUSEN TRICK" AND AMENABILITY OF SELF-SIMILAR GROUPS
• DIAMOND GRAPHS AND SUPER-REFLEXIVITY
• Self-similarity and branching in group theory.
• Schreier spectrum of the Hanoi Towers group on three pegs
• The spectral problem, substitutions and iterated monodromy.
• The diameter and Laplacian eigenvalues of directed graphs
• The Euclidean distortion of the lamplighter group.

Cited In (11)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• \(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
• Poincaré inequalities and rigidity for actions on Banach spaces

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)