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}),$ 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.$
|
2 | fixed typo in formula. | ||
|
|
||||
|
|
1 |
|
||
|
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.$ |
||||
