10
$\begingroup$

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?'

|cite|improve this question
$\endgroup$
  • $\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$ – Chad Brewbaker Oct 10 '13 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 '13 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$ – Chad Brewbaker Oct 10 '13 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 '13 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$ – Sasho Nikolov Oct 12 '13 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.