Timeline for Estimating a spectral gap
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2013 at 9:13 | comment | added | Delio Mugnolo | Vidit Nanda, OP is talking about the signless Laplacian, you are talking about the usual Laplacian, it seems. Their spectrum is quite different. For instance, it is known that the multiplicity of 0 as an eigenvalue of the signless Laplacian agrees with the number of connected components that are bipartite. In other words, if the graph is bipartite and connected, then OP's question simply reads: "Are there bounds on the second smallest eigenvalue?" | |
| Oct 25, 2013 at 9:00 | answer | added | Delio Mugnolo | timeline score: 2 | |
| Oct 25, 2013 at 1:20 | answer | added | Geoff | timeline score: 4 | |
| Oct 22, 2012 at 13:50 | comment | added | Federico Poloni | One could get bounds depending on some feature of $A$. For instance, we all know that $a^2+b^2$ can get arbitrarily small for positive $a$ and $b$, but nevertheless it is interesting to discover the bound $2ab\leq a^2+b^2$. | |
| Oct 22, 2012 at 12:43 | comment | added | Vidit Nanda | Searching google for "arbitrarily small spectral gap" produces this paper: <www.mis.mpg.de/fileadmin/jjost/abj21-6-04.pdf> which claims to construct graphs of arbitrarily small spectral gap given mild conditions on the degrees of the vertices. What is your starting point? If you know each entry of $A$ then you can presumably compute the eigenvalues and hence the gap. On the other hand if you want a theorem that bounds the gap for some general $A$, then there is no hope without more assumptions on the graph. | |
| Oct 22, 2012 at 11:37 | comment | added | Felix Goldberg | Well, $A$ is in fact a signless Laplacian of a graph. | |
| Oct 22, 2012 at 11:19 | comment | added | Vidit Nanda | Do you have any other information about A? As stated, the difference that you want to bound can be made arbitrarily small. | |
| Oct 22, 2012 at 10:36 | history | asked | Felix Goldberg | CC BY-SA 3.0 |