Document Open Access Logo

Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues

Authors Gary L. Miller, Noel J. Walkington, Alex L. Wang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.8.pdf
  • Filesize: 0.49 MB
  • 19 pages

Document Identifiers

Author Details

Gary L. Miller
  • Carnegie Mellon University, Pittsburgh, PA, USA
Noel J. Walkington
  • Carnegie Mellon University, Pittsburgh, PA, USA
Alex L. Wang
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Miller, Gary L.: Supported partially by NSF Grants CCF - 1637523 AitF.
  • Walkington, Noel J.: Supported by NSF Grants DMS - 1418991 and DMREF - 1729478.
  • Wang, Alex L.: Supported partially by NSF Grants CCF - 1637523 AitF.

Acknowledgements

We would like to thank Timothy Chu for many helpful discussions.

Cite As Get BibTex

Gary L. Miller, Noel J. Walkington, and Alex L. Wang. Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.8

Abstract

We present two graph quantities Psi(G,S) and Psi_2(G) which give constant factor estimates to the Dirichlet and Neumann eigenvalues, lambda(G,S) and lambda_2(G), respectively. Our techniques make use of a discrete Hardy-type inequality due to Muckenhoupt.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Spectra of graphs
  • Mathematics of computing → Approximation algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Hardy
  • Muckenhoupt
  • Laplacian
  • eigenvalue
  • effective resistance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon and Vitali D Milman. λ₁, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1):73-88, 1985. Google Scholar
  2. Ivo Babuška and John E Osborn. Finite element-Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems. Mathematics of computation, 52(186):275-297, 1989. Google Scholar
  3. Thomas Bühler and Matthias Hein. Spectral clustering based on the graph p-Laplacian. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 81-88. ACM, 2009. Google Scholar
  4. Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Proceedings of the Princeton conference in honor of Professor S. Bochner, 1969. Google Scholar
  5. Jozef Dodziuk. Difference equations, isoperimetric inequality and transience of certain random walks. Transactions of the American Mathematical Society, 284(2):787-794, 1984. Google Scholar
  6. Shayan Oveis Gharan. Lecture 12: Introduction to Spectral Graph Theory, Cheeger’s inequality. Lecture Notes, May 2016. Google Scholar
  7. Stephen Guattery, F. Thomson Leighton, and Gary L. Miller. The Path Resistance Method For Bounding The Smallest Nontrivial Eigenvalue Of A Laplacian. Combinatorics, Probability & Computing, 8(5), 1999. Google Scholar
  8. Stephen Guattery and Gary L. Miller. Graph Embedding and Laplacian Eigenvalues. SIAM J. Matrix Anal. Appl., 21(3):703-723, 2000. Google Scholar
  9. G.H. Hardy, Karreman Mathematics Research Collection, J.E. Littlewood, G. Pólya, D.E. Littlewood, and G. Pólya. Inequalities. Cambridge Mathematical Library. Cambridge University Press, 1952. URL: https://books.google.com/books?id=t1RCSP8YKt8C.
  10. Nabil Kahale. A semidefinite bound for mixing rates of Markov chains. Random Structures & Algorithms, 11(4):299-313, 1997. Google Scholar
  11. Ioannis Koutis, Gary L. Miller, and Richard Peng. A Nearly-mlog n Time Solver for SDD Linear Systems. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, pages 590-598, Washington, DC, USA, 2011. IEEE Computer Society. Available at https://arxiv.org/abs/1102.4842. URL: https://doi.org/10.1109/FOCS.2011.85.
  12. Alois Kufner, Lech Maligranda, and Lars-Erik Persson. The prehistory of the Hardy inequality. The American Mathematical Monthly, 113(8):715-732, 2006. Google Scholar
  13. Gyu Eun Lee. Stability of matter. GSO Seminar, UCLA, 2017. Google Scholar
  14. László Lovász et al. Random walks on graphs: A survey. Combinatorics, Paul erdos is eighty, 2(1):1-46, 1993. Google Scholar
  15. Laurent Miclo. An example of application of discrete Hardy’s inequalities. Markov Process. Related Fields, 5(3):319-330, 1999. Google Scholar
  16. Bojan Mohar. Some applications of Laplace eigenvalues of graphs, pages 225-275. Springer Netherlands, Dordrecht, 1997. URL: https://doi.org/10.1007/978-94-015-8937-6_6.
  17. Benjamin Muckenhoupt. Hardy’s inequality with weights. Studia Mathematica, 44(1):31-38, 1972. Google Scholar
  18. Y. Saad. Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2nd edition, 2003. Available at: URL: http://www-users.cs.umn.edu/~saad/toc.pdf.
  19. Aaron Schild. A Schur Complement Cheeger Inequality. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.10834.
  20. D. Spielman and S. Teng. Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal on Matrix Analysis and Applications, 35(3):835-885, 2014. Available at http://arxiv.org/abs/cs/0607105. URL: https://doi.org/10.1137/090771430.
  21. Gilbert Strang. Linear algebra and its applications. Thomson, Brooks/Cole, Belmont, CA, 2006. URL: http://www.amazon.com/Linear-Algebra-Its-Applications-Edition/dp/0030105676.
  22. Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact