Metric uniformization and spectral bounds for graphs
We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate 'Riemannian' metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatoric...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Science + Business Media B.V.
2012
|
| Online Access: | http://hdl.handle.net/1721.1/70991 https://orcid.org/0000-0002-4257-4198 |
| _version_ | 1826205269878636544 |
|---|---|
| author | Kelner, Jonathan Adam Lee, James R. Price, Gregory N. Teng, Shang-Hua |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Kelner, Jonathan Adam Lee, James R. Price, Gregory N. Teng, Shang-Hua |
| author_sort | Kelner, Jonathan Adam |
| collection | MIT |
| description | We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate 'Riemannian' metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs.
In particular, we use our method to show that for any positive integer k, the k [superscript th] smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k = 2. |
| first_indexed | 2024-09-23T13:10:21Z |
| format | Article |
| id | mit-1721.1/70991 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:10:21Z |
| publishDate | 2012 |
| publisher | Springer Science + Business Media B.V. |
| record_format | dspace |
| spelling | mit-1721.1/709912022-09-28T12:23:00Z Metric uniformization and spectral bounds for graphs Kelner, Jonathan Adam Lee, James R. Price, Gregory N. Teng, Shang-Hua Massachusetts Institute of Technology. Department of Mathematics Kelner, Jonathan Adam Kelner, Jonathan Adam Price, Gregory N. We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate 'Riemannian' metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the k [superscript th] smallest eigenvalue of the Laplacian on an n-vertex, bounded-degree planar graph is O(k/n). This bound is asymptotically tight for every k, as it is easily seen to be achieved for square planar grids. We also extend this spectral result to graphs with bounded genus, and graphs which forbid fixed minors. Previously, such spectral upper bounds were only known for the case k = 2. National Science Foundation (U.S.) (NSF grant CCF-0843915) National Science Foundation (U.S.) (NSF grant CCF-0915251) National Science Foundation (U.S.) (grant CCF-0644037) National Science Foundation (U.S.) (Graduate Research Fellowship) Akamai Technologies, Inc. Alfred P. Sloan Foundation (Research Fellowship) National Science Foundation (U.S.) (NSF grant CCF-0635102) National Science Foundation (U.S.) (grant CCF-0964481) National Science Foundation (U.S.) (CCF-1111270) 2012-06-01T18:25:24Z 2012-06-01T18:25:24Z 2011-08 Article http://purl.org/eprint/type/JournalArticle 1016-443X 1420-8970 http://hdl.handle.net/1721.1/70991 Kelner, Jonathan A. et al. “Metric Uniformization and Spectral Bounds for Graphs.” Geometric and Functional Analysis 21.5 (2011): 1117–1143. Web. https://orcid.org/0000-0002-4257-4198 en_US http://dx.doi.org/10.1007/s00039-011-0132-9 Geometric and Functional Analysis Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Science + Business Media B.V. MIT web domain |
| spellingShingle | Kelner, Jonathan Adam Lee, James R. Price, Gregory N. Teng, Shang-Hua Metric uniformization and spectral bounds for graphs |
| title | Metric uniformization and spectral bounds for graphs |
| title_full | Metric uniformization and spectral bounds for graphs |
| title_fullStr | Metric uniformization and spectral bounds for graphs |
| title_full_unstemmed | Metric uniformization and spectral bounds for graphs |
| title_short | Metric uniformization and spectral bounds for graphs |
| title_sort | metric uniformization and spectral bounds for graphs |
| url | http://hdl.handle.net/1721.1/70991 https://orcid.org/0000-0002-4257-4198 |
| work_keys_str_mv | AT kelnerjonathanadam metricuniformizationandspectralboundsforgraphs AT leejamesr metricuniformizationandspectralboundsforgraphs AT pricegregoryn metricuniformizationandspectralboundsforgraphs AT tengshanghua metricuniformizationandspectralboundsforgraphs |