|
|||||
|
|
Metric Uniformization and Spectral Bounds for Graphs |
|
| Authors: | Jonathan A. Kelner James R. Lee Gregory N. Price Shang-Hua Teng |
| Affiliation: | 1. Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA 2. Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA, 98195-2350, USA 3. Computer Science and Artifical Intelligence Laboratory, 2159 Massachusetts Institute of Technology, 2160, Cambridge, MA, 02139, USA 4. 913 Cowper St, Palo Alto, CA, 94301, USA 5. Department of Computer Science, University of Southern California, 941 Bloom Walk, Los Angeles, CA, 90089, USA |
| Abstract: | 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |