Skip to main content
6 votes
Accepted

Dichotomy of the spectra of directed graphs

The answer to “alternatively, can a directed graph have an eigenvalue with an exponentially small imaginary component” is YES (though I don’t understand what is “alternative” about this statement, as ...
Emil Jeřábek's user avatar
6 votes
Accepted

How is SDP an extension of spectral algorithms?

This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the ...
Sasho Nikolov's user avatar
1 vote

Entries of the Inverse Laplacian

I originally wanted to pose the question, but then I started investigating and found a few very helpful interpretation that haven't been collected anywhere (to my knowledge). Hence, I will write my ...
Zuza's user avatar
  • 141
1 vote

Spectral sparsification of graphs with negative edge weights

I personally do not work in spectral graph theory. I write this from a linear algebra perspective. This definition seems to apply naturally to graphs which are permitted to have negative edge weights ...
BrownieInMotion's user avatar
1 vote
Accepted

When can partial spectral sparsifiers be combined?

Regarding your 1st question: no, this would not hold in general. Rather (answering your 2nd question), the right way to interpret the approach by Spielman and Teng is as follows: let $G'$ be a vertex-...
smapers's user avatar
  • 849
1 vote
Accepted

Fast Computation of First k Eigenvectors of Graph Laplacian

Answer to Q1: In [1], it is argued at the end of section 1 that the first k eigenvectors can be approximated in time roughly $O(mk)$ (up to log-factors), with $m$ the number of edges. They are not ...
smapers's user avatar
  • 849
1 vote

Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?

Without any further constraints, this expression will in general be unbounded, so the maximum won't exist. Let $V$ be $\{v_1,\ldots,v_n\}$ with $n\ge 2$. Pick $i\neq j$ such that $v_i,v_j$ are not ...
Klaus Draeger's user avatar
1 vote

Dichotomy of the spectra of directed graphs

I feel like the bounds will very strongly depend on the particular connectivity structure of the graph. One example would be a one-way cycle of length $N$. With the correct ordering, it's not hard ...
Lagerbaer's user avatar
  • 329

Only top scored, non community-wiki answers of a minimum length are eligible