<p>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?</p>

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

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

CC BY-SA 3.0
2013-10-10T20:36:46.077Z
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.
Chad Brewbaker
CC BY-SA 3.0
2013-10-10T20:48:09.300Z
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.
Dimitris
CC BY-SA 3.0
2013-10-10T21:03:48.873Z
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.
Chad Brewbaker
CC BY-SA 3.0
2013-10-10T22:50:59.190Z
Hmm, yes I guess you are right. I wonder if there is any combinatorial type of argument for the gap though.
Dimitris
CC BY-SA 3.0
2013-10-11T00:26:51.290Z
Doesn't Cheeger's inequality relate the gap to expansion?
Sasho Nikolov
CC BY-SA 3.0
2013-10-11T00:34:20.450Z
I think that Cheeger only works for $d$-regular graphs if you care about the adjacency's $\lambda_2$.
Dimitris
CC BY-SA 3.0
2013-10-11T00:59:33.327Z
For $G_{n, 1/2}$, the degrees will be very tightly concentrated around $n/2$, you may still be able to deduce something from Cheeger (i.e. from the more general Cheeger ineq. which relates the normalized adjacency to conductance)
Sasho Nikolov
CC BY-SA 3.0
2013-10-11T13:38:01.687Z
for these cases maybe you can, I need to check it. But still I'm not sure if all dense (sparse is another story), irregular graphs, behave like the concentration points of Gnp.
Dimitris
CC BY-SA 3.0
2013-10-12T04:49:10.480Z
But the fraction of all graphs that have some property is exactly the probability that $G_{n, 1/2}$ has the property
Sasho Nikolov
CC BY-SA 3.0
2013-10-12T14:45:40.243Z
Sasho you are right. Any graph on $n$ vertices that is picked uniformly at random, is an equiprobable event in the $G(n,1/2)$ family. This implies what you said: almost all graphs have at least this gap (they actually have $\sqrt{n}$). So my question as is, is answered by your comment. You can write it as an answer below. A sidenote: A negative consequence of talking about the fraction of all graphs that satisfy a property $P$, is that all sparse graphs are lost in probability, since almost all graphs are dense, and $G(n,1/2)$ 'like'. The 'edit' part of my question seems more interesting now.
Dimitris
CC BY-SA 3.0
2013-10-12T18:40:03.813Z
wondering if this could be related/recast without too much trouble to an NP complete problem, eg computing cliques? there is some related research on this for $G_{n,{1 \over 2}}$ & clique detection. $log(n)$-cliques are right at the transition point of being 50% likely.
vzn
<graph-theory><linear-algebra><spectral-graph-theory>
Number of graphs with prescribed spectrum
Dimitris
# Number of graphs with prescribed spectrum

(Asked by: username_0 on 2013-10-10)

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

**Tags:** graph-theory, linear-algebra, spectral-graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Hmm, yes I guess you are right. I wonder if there is any combinatorial type of argument for the gap though.  
> **username_2**: Doesn't Cheeger's inequality relate the gap to expansion?  
> **username_0**: I think that Cheeger only works for $d$-regular graphs if you care about the adjacency's $\lambda_2$.  
> **username_2**: For $G_{n, 1/2}$, the degrees will be very tightly concentrated around $n/2$, you may still be able to deduce something from Cheeger (i.e. from the more general Cheeger ineq. which relates the normalized adjacency to conductance)  
> **username_0**: for these cases maybe you can, I need to check it. But still I'm not sure if all dense (sparse is another story), irregular graphs, behave like the concentration points of Gnp.  
> **username_2**: But the fraction of all graphs that have some property is exactly the probability that $G_{n, 1/2}$ has the property  
> **username_0**: Sasho you are right. Any graph on $n$ vertices that is picked uniformly at random, is an equiprobable event in the $G(n,1/2)$ family. This implies what you said: almost all graphs have at least this gap (they actually have $\sqrt{n}$). So my question as is, is answered by your comment. You can write it as an answer below. A sidenote: A negative consequence of talking about the fraction of all graphs that satisfy a property $P$, is that all sparse graphs are lost in probability, since almost all graphs are dense, and $G(n,1/2)$ 'like'. The 'edit' part of my question seems more interesting now.  
> **username_3**: wondering if this could be related/recast without too much trouble to an NP complete problem, eg computing cliques? there is some related research on this for $G_{n,{1 \over 2}}$ & clique detection. $log(n)$-cliques are right at the transition point of being 50% likely.  

---

## 0 answers

