Metric uniformization and spectral bounds for graphs

Mathematics – Metric Geometry

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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 kth 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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Metric uniformization and spectral bounds for graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Metric uniformization and spectral bounds for graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Metric uniformization and spectral bounds for graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-188744

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.