14

I too encountered this issue when I was writing a paper that required a citation to hardness of edge expansion (or Cheeger constant) defined as $\min_{S \subset V, |S| \leq |V|/2} |\delta(S)|/|S|$. The classic paper of Leighton and Rao on separators ( http://dl.acm.org/citation.cfm?id=331526 ) mentions that this is a hard problem and refers to the paper of ...


13

It is known that, for $G$ of bounded treewidth, the Tutte polynomial $T(G;x,y)$ can be evaluated at any $(x,y)$ using $O(n)$ arithmetic operations. If $G$ is connected, then $t(G)=T(G;1,1)$.


11

I think the following should answer your questions, even though it's not exactly in the same order. The original formulation of the small set expansion conjecture states that, analogously to the Unique Games Conjecture, for every $\epsilon >0$ there exists $\delta>0$ so that it is NP-hard to determine whether in a graph $G$ it's the "YES" case where ...


10

Even asking whether a graph with a given spectrum exists is a tough question. This is witnessed by the open problem of determining whether there exists a graph of girth 5 diameter 2 and order 3250 whose spectrum (if it exists) is known.


7

You might like this recent paper: http://arxiv.org/abs/1211.0589v1 The paper shows, e.g., that "for any finite graph with $n$ vertices and all $k ≥ 2$, the $k$th largest eigenvalue" of the graph's Laplacian, i.e. $L=I-A/d$, "is at most $1−\Omega(\frac{k^3}{n^3})$", where $A$ is the adjacency matrix and $d$ a bound on the degree.


7

[This answer was copied from my answer on the now-defunct theoreticalphysics stackexchange site.] For classical expanders, the spectral definition can be expressed in terms of the second-smallest eigenvalue of the graph Laplacian, which can be thought of as the minimum of a quadratic form over all unit vectors orthogonal to the all-ones vector. If we ...


6

Just an extended comment to include the picture: if the following (random) resistor network is valid then the max current flow 33.9mA is not on the shortest path from $s$ (+5V) to $t$ (GND).


6

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 it does not in any way disprove the conjecture). As I already wrote in a comment, it is a not very difficult exercise to show that if $f\in\mathbb Z[x]$ is a ...


5

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 leading eigenvector of a symmetric matrix". So spectral algorithms that use the latter as a starting point can be interpreted as SDP rounding algorithm. To see that ...


5

Regarding the last eigenvalue: The last eigenvalue $\lambda_n$ measures (roughly) how close is the graph to be bipartite. For example, $\lambda_n = -d$ if and only if the graph is bipartite (this is a fairly easy exercise). You can read more about it in Luca Trevisan's blog: http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/ ...


4

At least among regular bi-partite graphs, Ramanujan graphs provide the optimal approximation of the complete bipartite graph. Let's say that a graph $H$ $C$-approximates a graph $G$ if $tL_H \preceq CL_G$ for $t$ the smallest real number such that $L_G \preceq tL_H$. (I.e. $t := \|L_H^{-1/2} L_G L_H^{-1/2}\|$ where the norm is the operator norm and inverses ...


4

Yes, there is a connection between the spectrum of the graph and the size of the maximum cut. It might be easiest to see this with the normalized graph Laplacian, $L = I - D^{-1/2}AD^{-1/2}$, where $I$ is the identity, $A$ is the adjacency matrix of the graph $G = ([n], E)$ and $D$ is the diagonal matrix defined by $D_{ii} = d_i$, the degree of vertex $i$. ...


3

There are two separate issues here. How to use efficient solvers for $Ax=b$ in order to apply $A^{1/2}b$. How to compute the determinant. The short answers are 1) use rational matrix function approximations, and 2) you don't, but you don't need to anyways. I address both of these issues below. Matrix square root approximations The idea here is to ...


2

Your intuition is in a certain sense correct. By straightforward linear algebra we can find the electric potential of each node in the graph, given the net current from source to sink. Now we can calculate the probability distribution of the path taken by the electric current through the graph. By the second law of thermodynamics, (that no process may ...


2

Yes. The original Goemans-Williamson paper also discusses the dual of the PSD relaxation, which is equivalent to minimizing $\lambda_{max}(L_G+D)$, over all the traceless diagonal matrices D. Trevisan used some of this intuition to design a nontrivial approximation to MaxCut, at the bottom of which lies a spectral partitioning algorithm. In his algorithm, ...


1

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-induced subgraph of $G$, and $H'$ a spectral sparsifier of $G'$. Then the graph $G-G'+H'$ (replace all edges in $G'$ by those in $H'$) will be a spectral ...


1

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 very precise in their statement however, but I'm not aware of a better reference explictly stating this. Answer to Q2: No, this will not hold in general. You ...


1

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 both isolated. The submatrix of the Laplacian for $v_i,v_j$ has the form $\begin{pmatrix}d_i & -a_{ij} \\ -a_{ij} & d_j\end{pmatrix}$ with $a_{ij}\in\{0,1\...


1

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 to see that $A(G)^N - I = 0$, so the eigenvalues are all the $N$-th roots of unity, i.e. $e^{2\pi i n/N}$ with $n$ going from $0$ to $N-1$. For even $N$, you'...


1

I wanted to add this as a comment but it was too long. I am not sure if this completely answers the question. For bipartite graphs for instance we can possibly get a simple first cut bound from a simple trace method. Lets look at the adjacency matrix. In your case we want to show that $\lambda_k$ is not close to 0. So consider $Trace(A^2)$. For a d-regular ...


1

Suggest these free available resources. Most textbooks on graph theory only glance at "free probability theory". Lectures on the Combinatorics of Free Probability (London Mathematical Society Lecture Note Series): http://www.amazon.com/Lectures-Combinatorics-Probability-Mathematical-Society/dp/0521858526 Speicher lectures: http://www.mast.queensu.ca/~...


1

Tree isomorphism is polynomial time. Reed, Ronald C. (1972). "The Coding of Various Kinds of Unlabeled Trees". Graph Theory and Computing: 153–182


1

This is just a partial answer mainly answering just $a)$ and $b)$ The number of non-isomorphic graphs is asymptotically equivalent to $$\frac{2^{n \choose 2}}{n!}$$ Almost all graphs are connected (in fact $k$-connected for any constant $k$) hence this answer your first question. This is an open problem. If we restrict ourselves to trees then it is well ...


1

This is simple. Assume the adjacency matrix is $A$. As it is symmetric, it guarantees that $A$ can be diagonalized as $A=U\Sigma U^T$ by SVD decomposition, where $\Sigma=diag(\lambda_1,...,\lambda_n)$ is the diagonal matrix of eigenvalues. For node $i$, just add this mount of loop to it: $\text{ceiling}(|min(\lambda_i,0)|)$.


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