Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT?Can the estimates provide sharp lower bound to MAXCUT?
Size of MAXCUT from eigenvalues
spectral graph theory;max cut
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$. The largest eigenvalue of $L$ is $$\lambda_{n-1} = \max_x\frac{x^TLx}{x^Tx} = \max_{x}\frac{\sum_{(i, j) \in E}{(x_i - x_j)^2}}{\sum_{i}{d_i x_i^2}}.$$Because $(x_i - x_j)^2 \leq 2x_i^2 + 2x_j^2$ by Cauchy-Schwarz, $\lambda_{n-1} \leq 2$. Equality is achieved if and only if for each edge $(i, j)$, $x_i = -x_j$, which means that $\lambda_{n-1}= 2$ only if the graph has a bipartite connected component, i.e. a connected component whose maximum cut is equal to the number of edges in the component. For a robust version of this result, see Luca Trevisan's paper. He shows that $$\lambda_{n-1} \geq 2\frac{\text{MaxCut}}{m},$$(where $m$ is the number of edges of the graph) and if $\lambda_{n-1} \geq 2(1-\epsilon)$, then there exits a set of vertices $S$ and a partition $(S_1, S_2)$ of $S$ such that $$|e(S_1, S_2)| \geq \frac{1}{2}(1-\sqrt{16\epsilon})\text{vol}(S),$$where $\text{vol}(S) = \sum_{i \in S}{d_i}$ and $e(S_1, S_2)$ is the set of edges with one endpoint in $S_1$ and the other in $S_2$.Note that the second bound does not necessarily lower bound the max cut in a useful way: it only lower bounds the maximum cut of the set $S$ in terms of $\text{vol}(S)$. This is unavoidable: think of a graph that's the disjoint union of an edge and a large graph with small maximum cut, say a clique. The maximum cut of the graph is very close to $m/2$, which is the minimum possible value of the max cut of a graph with $m$ edges. However, $\lambda_{n-1} = 2$, the maximum possible value of $\lambda_{n-1}$. In other words, while $\lambda_{n-1}$ is a relaxation of the maximum cut (up to appropriate rescaling), the gap is arbitrarily close to 2, and a 2-approximation to max cut is trivial.Nevertheless, in the paper Luca uses the spectral result to design a recursive approximation algorithm for max cut. This is one cool thing about the paper: it uses a relaxation that, unlike the SDP relaxation of Goemans and Wiliamson, has trivial gap, but despite that an optimal solution to the relaxation actually provides enough guidance to achieve a non-trivial approximation factor. 