Estimating a spectral gap Suppose you have a real positive definite matrix $A$ who eigenvalues are $\lambda_{1} \leq \lambda_{2} \leq \ldots \leq \lambda_{n}$. I am interested in bounding from below $\lambda_{2}-\lambda_{1}$. (It is known that $\lambda_{1}$ is simple). Are there any known methods for this kind of problem?
 A: You mention that $A$ is the Laplacian of a graph. The field of spectral graph theory is well established, and I think there are several techniques that can be used to bound the spectral gap of a graph Laplacian for an undirected weighted graph.  
Perhaps the most straightforward is known as Cheeger's inequality which controls the spectral gap, $\lambda_2 - \lambda_1$ by the Cheeger constant of the graph.  See the wikipedia entry for Cheeger constant: http://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)
If you might also consider trying a Log sobolev inequality:
http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aoap/1034968224
I hope this helps.
A: There are many articles on spectral theory for signless Laplacians $Q$, but the most complete is as far as I know Towards a spectral theory of graphs based on the signless Laplacian, II
In that paper, which is three years old, Cvetkovic and Simic point out why in their opinion not the second smallest is important, but the second largest $Q$-eigenvalue is important (hint: it corresponds to the spectral gap). Most researchers seem to share their opinion, because as far as I know the answer to your question is unknown. 
The best available piece of information is, to my knowledge, the bound on the smallest $Q$-eigenvalues based on the largest (signed) Laplacian eigenvalue and the maximal and minimal degrees of the graph that is presented in Bipartite subgraphs and the signless laplacian matrix.
