Diameters, distortion, and eigenvalues
Copyright policy )Diameters, distortion, and eigenvalues
We study the relation between the diameter, the first positive eigenvalue of the discrete $p$-Laplacian and the $\ell_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 $\ell_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.
Final version, to appear in the European Journal of Combinatorics
- The University of Texas System United States
- Texas A&M Research Foundation United States
- Texas A&M University United States
- Texas A&M University United States
- Texas A&M University United States
Group Theory (math.GR), Theoretical Computer Science, Sierpinski gasket, Mathematics - Metric Geometry, spectral gap, FOS: Mathematics, eigenvalue, diameter, Pascal graphs, Distance in graphs, Graphs and linear algebra (matrices, eigenvalues, etc.), Metric Geometry (math.MG), Cayley graphs, Graphs and abstract algebra (groups, rings, fields, etc.), Functional Analysis (math.FA), Mathematics - Functional Analysis, Computational Theory and Mathematics, Geometry and Topology, Laplacian, distortion, Schreier graphs, Mathematics - Group Theory
Group Theory (math.GR), Theoretical Computer Science, Sierpinski gasket, Mathematics - Metric Geometry, spectral gap, FOS: Mathematics, eigenvalue, diameter, Pascal graphs, Distance in graphs, Graphs and linear algebra (matrices, eigenvalues, etc.), Metric Geometry (math.MG), Cayley graphs, Graphs and abstract algebra (groups, rings, fields, etc.), Functional Analysis (math.FA), Mathematics - Functional Analysis, Computational Theory and Mathematics, Geometry and Topology, Laplacian, distortion, Schreier graphs, Mathematics - Group Theory
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!