Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A generic question:

are there any spectral techniques to estimate the genus of a graph? I am interested in complete balance multipartite graph.

share|improve this question
1  
@Mohsen: A related post here on cstheory: cstheory.stackexchange.com/q/3100/1800. But I guess there are much stronger properties hold on complete multipartite graphs. –  Hsien-Chih Chang 張顯之 Feb 5 '11 at 15:48
add comment

2 Answers 2

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

share|improve this answer
add comment

I believe that this is the subject of Jon Kelner's paper Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. In particular, he proves a lower bound of the form $O(g/n)$ for $\lambda_2$, resolving a conjecture of Spielman and Teng.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.