most recent 30 from http://mathoverflow.net 2013-06-20T09:45:09Z http://mathoverflow.net/feeds/question/54395 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54395/spectral-techniques-for-genus-of-a-graph Mohsen 2011-02-05T12:44:27Z 2011-02-05T21:18:23Z

<p>A generic question: </p> <p>are there any spectral techniques to estimate the genus of a graph? I am interested in complete balance multipartite graph.</p>

http://mathoverflow.net/questions/54395/spectral-techniques-for-genus-of-a-graph/54413#54413 Igor Rivin 2011-02-05T16:29:17Z 2011-02-05T16:43:44Z

<p>Yes, there are techniques. For graphs of fixed genus and $n$ vertices, the second lowest eigenvalue of the laplacian is of order $O(1/\sqrt{n}),$ where the hidden constant depends on the genus (in an explicit way -- this follows from the Cheeger inequality and the separator theorems of Lipton and Tarjan, see eg, the paper of Spielman and Teng called "Spectral partitioning works). The dependence on the genus can be made quite explicit, so if you do that, you will get a lower bound on the genus in terms of the size of the graph and $\lambda_2.$</p>

http://mathoverflow.net/questions/54395/spectral-techniques-for-genus-of-a-graph/54414#54414 David Speyer 2011-02-05T16:43:34Z 2011-02-05T16:43:34Z

<p>I believe that this is the subject of Jon Kelner's paper <a href="http://math.mit.edu/~kelner/Publications/Docs/LowGenusJournal.pdf" rel="nofollow">Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus</a>. In particular, he proves a lower bound of the form $O(g/n)$ for $\lambda_2$, resolving a conjecture of Spielman and Teng.</p>