I have a question relevant to the number of graphs with prescribed spectral ratio. Let $A$ be the adjacency matrix of a graph on $n$ vertices. Let $\lambda_i$ be its $i$-th largest (signed) eigenvalue. Moreover, assume the following (larger than a constant) spectral ratio constraint $$\frac{\lambda_1}{\max\{\lambda_2,|\lambda_n|\}} \ge \Omega(\log(n)).$$ What is the fraction of graphs (out of the $2^{O(n^2)}$ many) that have the above spectral property?

In other words, what is the fraction of graphs on $n$ vertices with increasing spectral ratio?

Edit: A relevant question that might be easier: 'is there a combinatorial property on the graph that leads to an $Ω(\log(n))$ ratio?'

  • $\begingroup$ I would NAUTY it up to nine verticies, then take a thousand random graphs of size 1000. If the thousand don't have your property it is probably rare. $\endgroup$ Oct 10, 2013 at 20:36
  • $\begingroup$ Random graphs wouldn't really work, if you are talking about G(n,p) ones. These guys have a ~1/sqrt(n) ratio, but the probability of a graph realization is proportional to the edges that are on. In the Gnp setting you don't sample graphs uniformly at random, which is the thing that I'm not sure how to do. Edit: Hmm I guess, I could have $2^{n \choose 2}$ numbers corresponding to the possible sequences of 0/1 of the edge set. Then I could uniformly sample one a graph. $\endgroup$
    – Dimitris
    Oct 10, 2013 at 20:48
  • $\begingroup$ G(n, .5) gives you the boring average random graph. If you have to shrink the edge ratio down to G(n, 1/sqrt(n)) you half answered your question by excluding those that are too dense or too sparse. $\endgroup$ Oct 10, 2013 at 21:03
  • $\begingroup$ Hmm, yes I guess you are right. I wonder if there is any combinatorial type of argument for the gap though. $\endgroup$
    – Dimitris
    Oct 10, 2013 at 22:50
  • 1
    $\begingroup$ But the fraction of all graphs that have some property is exactly the probability that $G_{n, 1/2}$ has the property $\endgroup$ Oct 12, 2013 at 4:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.