User floc - MathOverflow

When Do a Few Eigenvectors of Graph Laplacians Not Determine the Graph?

2012-08-18T21:21:15Z

Essentially as the title, but I'll give a little bit more background.

I have some finite graph $G$ with $n$ vertices and adjacency matrix $A$. Let $D$ be the $n$ by $n$ matrix with the degree of vertex $i$ at the $i,i$ entry, and 0's everywhere. Finally, let $L = D - A$ be the (unnormalized) graph Laplacian of $G$. Next, fix some collection of eigenvectors and eigenvalues of $L$.

My big-picture question is: Under what conditions are there other graphs which share those eigenvectors/values?

With a little more precision: Approximately how many eigenvectors & eigenvalues can be specified before the answer is no? About how many graphs are there when the answer is yes?

It seems likely that the answer would be a little complicated. I know a few special cases (e.g. 2 eigenvectors/values determine cycles completely; on the other hand, as long as the average degree is fairly large, there are generally very many graphs with the same bottom eigenvector). I certainly appreciate hearing about conditions which aren't tight, as long as they are at least a little broad.

I'm interested in the situation where the eigenvectors DON'T determine the graph, so I would also appreciate any literature pointers to `relaxations' of this idea. For example, one could imagine requiring that the Laplacian contracts the eigenvectors by at least a certain amount (this certainly allows many graphs, but that space is pretty big). In another direction, it seems plausible there is some analogue in the language of graphons.

Thanks for any help!

An $L^{\infty} Version of Principal Component Analysis?

2012-08-05T02:26:26Z

I have a $k$ by $n$ matrix $A$, with $k \ll n$. In case it helps, the $k$ rows are orthonormal.

I'm interested in finding a $k$ by $k$ orthogonal matrix $M$ so as to maximize the $L^{\infty}$ norms of the rows of $MA$. This is a little imprecise, since it may not be possible to maximize all of them simultaneously. At the moment, my criterion is to maximize the weighted sums of these $L^{\infty}$ norms by some weights $w_{1}, \ldots, w_{k}$. All of these weights are fairly similar, so if it is easier, I would also be happy with maximizing the average.

This seems to be a little bit similar to PCA, which essentially finds rows with maximal L^2 norm.

Thanks for any suggestions/literature references.

Comment by floc

2012-08-19T14:35:32Z

Dear Chris, Thanks for the pointer! That seems like a fairly large family, and between this and Qiaochu's comment it seems clear that there is only something nontrivial to say about very special graphs. I'm inclined to accept unless someone comes by soon with a miraculous pointer to a literature on relaxations.

Comment by floc

2012-08-19T00:02:52Z

Re Douglas: Thank you. Re Qiaochu: Interesting comment. I wouldn't be surprised if a small number of eigenvectors were essentially always enough, but am not familiar with what you mean by the `corresponding Galois group'. A quick Google search only found me articles that seemed focused on graphs with at least some symmetry. (I should also mention: Even ~log(n) is interesting to me. I'd be happy to know that for large, fairly dense graphs, there is generically freedom to fix ~10 eigenvectors! )

Comment by floc

2012-08-18T22:25:33Z

Re: Douglas Zare: I'm not sure. The few `classical' examples I've looked at seem to have pretty different eigenvectors. Until your question, I hadn't thought about this avenue - I thought they were of interest if you want different eigenvectors. Could you let me know any intuition about why these might be good candidates?

Comment by floc

2012-08-05T21:31:23Z

Thanks for the comment on multidimensional scaling. I can see that this question fits into that framework, but that framework is much broader (and seems to encompass many things we'd like to do, but which are not computationally feasible). Do you know if this particular question (or one similar to it) has been addressed?