<p>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, <span class="math-container">$L = I - D^{-1/2}AD^{-1/2}$</span>, where <span class="math-container">$I$</span> is the identity, <span class="math-container">$A$</span> is the adjacency matrix of the graph <span class="math-container">$G = ([n], E)$</span>, and <span class="math-container">$D$</span> is the diagonal matrix defined by <span class="math-container">$D_{ii} = d_i$</span>, the degree of vertex <span class="math-container">$i$</span>. The largest eigenvalue of <span class="math-container">$L$</span> is</p>
<p><span class="math-container">$$\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}}.$$</span></p>
<p>Because <span class="math-container">$(x_i - x_j)^2 \leq 2x_i^2 + 2x_j^2$</span> by Cauchy-Schwarz, <span class="math-container">$\lambda_{n-1} \leq 2$</span>. Equality is achieved if and only if for each edge <span class="math-container">$(i, j)$</span>, <span class="math-container">$x_i = -x_j$</span>, which means that <span class="math-container">$\lambda_{n-1}= 2$</span> 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.</p>
<p>For a robust version of this result, see <a href="http://arxiv.org/abs/0806.1978" rel="nofollow noreferrer">Luca Trevisan's paper</a>. He showed that</p>
<p><span class="math-container">$$
\lambda_{n-1} \geq 2\frac{\text{MaxCut}}{m},
$$</span></p>
<p>(where <span class="math-container">$m$</span> is the number of edges of the graph) and if <span class="math-container">$\lambda_{n-1} \geq 2(1-\epsilon)$</span>, then there exits a set of vertices <span class="math-container">$S$</span> and a partition <span class="math-container">$(S_1, S_2)$</span> of <span class="math-container">$S$</span> such that</p>
<p><span class="math-container">$$
|e(S_1, S_2)| \geq \frac{1}{2}(1-\sqrt{16\epsilon})\text{vol}(S),
$$</span>
where <span class="math-container">$\text{vol}(S) = \sum_{i \in S}{d_i}$</span> and <span class="math-container">$e(S_1, S_2)$</span> is the set of edges with one endpoint in <span class="math-container">$S_1$</span> and the other in <span class="math-container">$S_2$</span>.</p>
<p>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 <span class="math-container">$S$</span> <em>in terms of <span class="math-container">$\text{vol}(S)$</span></em>. This is unavoidable: think of a graph that is 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 <span class="math-container">$m/2$</span>, which is the minimum possible value of the max cut of a graph with <span class="math-container">$m$</span> edges. However, <span class="math-container">$\lambda_{n-1} = 2$</span>, the maximum possible value of <span class="math-container">$\lambda_{n-1}$</span>. In other words, while <span class="math-container">$\lambda_{n-1}$</span> 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.</p>
<p>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 Williamson, has trivial gap, but despite that an optimal solution to the relaxation actually provides enough guidance to achieve a non-trivial approximation factor.</p>

CC BY-SA 3.0
2013-09-30T16:52:27.983Z
Thankyou. What is $m$? what is $e(S_1,S_2)$ here? And so we have $MaxCut \leq \frac{\lambda_{n-1}}{2m}$?
Turbo
CC BY-SA 3.0
2013-09-30T16:56:28.937Z
Can we have a lower bound to $MaxCut$ from eignevalues?
Turbo
CC BY-SA 3.0
2013-09-30T17:01:25.397Z
I think you did the algebra wrong there, the max cut is at most $m \lambda_{n-1}/2$. This is the easy direction however. Indeed, the second bound is a partial converse. Note that it only says something about the subset $S$, however. In general you cannot lower bound the maximum cut of the entire graph from $\lambda_{n-1}$ because it's possible to have $\lambda_{n-1} = 2$ but the maximum cut being arbitrarily close to its minimum possible value, $m/2$
Sasho Nikolov
CC BY-SA 3.0
2013-09-30T17:02:22.173Z
I see that $MaxCut*d_{max}\geq|e(S_1,S_2)|$ and hence $MaxCut\geq\frac{1}{2d_{max}}(1-\sqrt{16\epsilon})Vol(S)$. Is this a sharp lower bound? However there is no eigenvalue here.
Turbo
CC BY-SA 3.0
2013-09-30T17:04:05.747Z
Correction: $MaxCut\leq\frac{m\lambda_{n-1}}{2}$ holds.
Turbo
CC BY-SA 3.0
2013-09-30T17:04:52.643Z
"In general you cannot lower bound the maximum cut of the entire graph from λn−1" How about for regular graphs or some graphs with special structure?>
Turbo
CC BY-SA 3.0
2013-09-30T17:09:09.833Z
Does your updated comment hold for connected graphs with $\lambda_{n-1}<2$? You have mentioned disjoint union as a counter example to my lower bound estimate.
Turbo
CC BY-SA 3.0
2013-09-30T17:10:11.950Z
as long as you allow a graph that consists of a large graph with small maximum cut and a small bipartite graph, and the two are either disconnected or are connected by a small number of edges, the gap between $2m - 2\text{MaxCut}$ and $2 - \lambda_{n-1}$ can be arbitrarily bad. however, I'd say Luca's partial converse is quite satisfactory.
Sasho Nikolov
CC BY-SA 3.0
2013-09-30T17:11:06.470Z
I am interested in a graph sequence that is regular and is not bipartite which also has $MaxCut=\theta(n)$ in my case. That is why I thought may be your comments could be turned into a sharp lowerbound and am I wrong again?
Turbo
CC BY-SA 3.0
2013-09-30T17:19:53.683Z
So the bad example is quite robust. It's not necessary to have a bipartite connected component: just a small set of vertices that induce a subgraph which is *close to bipartite* and the cut between these vertices and the rest of the graph is small.
Sasho Nikolov
CC BY-SA 3.0
2013-10-02T21:05:09.630Z
It seems that $m = O(n^2)$. Does it really give a constant fact result since $\frac{\lambda_{n-1}}{2}\leq 1$?
Turbo
CC BY-SA 3.0
2013-10-02T21:09:23.790Z
The result here http://www.fmf.uni-lj.si/~mohar/Reprints/1990/BM90_CMJ40_Delorme_MaximumCutProblem.pdf gives $\frac{n\lambda_{n-1}}{4}$. May be it is the way the Laplacians arew defined?
Turbo
CC BY-SA 3.0
2013-10-03T01:02:20.647Z
About Delorme-Poljak, the difference is because their Laplacian is not normalized, so it is equal to mine muliplied by $D^{1/2}$ on both sides. With respect to your first question, I do not understand what you are asking. Think of $\lambda_{n-1}m/2$ as the relaxation of MaxCut. If the graph is bipartite, $\lambda_{n-1} = 2$. Fan Chung's notes are a good source about basic spectral graph theory: http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf
Sasho Nikolov
CC BY-SA 3.0
2013-10-03T01:42:58.237Z
nevermind, the first question was related to the second. You answer answers both.
Turbo
CC BY-SA 3.0
2013-10-03T01:52:18.420Z
BTW the Delorme-Poljak bound is stronger than the largest eigenvalue of the laplacian and is in fact equivalent to the Goemans-Williamson SDP.
Sasho Nikolov
CC BY-SA 3.0
2013-10-03T02:04:51.413Z
How is it stronger? Symbolically both look the same except for the factor of $4$ below and the modified Laplacians?
Turbo
CC BY-SA 3.0
2013-10-03T02:26:17.540Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/10867/discussion-between-sasho-nikolov-and-jas)
Sasho Nikolov
CC BY-SA 4.0
2013-09-30T16:46:45.333Z
2024-01-09T13:46:38.757Z
2024-01-09T13:46:38.757Z
Sasho Nikolov
<p>Yes. The original <a href="http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf" rel="nofollow">Goemans-Williamson paper</a> 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.</p>

<p><a href="http://arxiv.org/pdf/0806.1978v5.pdf" rel="nofollow">Trevisan</a> 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, he essentially looks at the largest eigenvector of the normalized Laplacian in order to isolate components of the graph between which there is a large cut. The core of the analysis is a Cheeger-like inequality for the largest eigenvalue.</p>

CC BY-SA 3.0
2013-09-30T16:54:03.537Z
"....all traceless" contains complex matrices?
Turbo
CC BY-SA 3.0
2013-09-30T17:32:56.227Z
No, we're only looking at real matrices.
zotachidil
CC BY-SA 3.0
2013-09-30T20:34:24.160Z
I think since L is real, D the optimal D will be real wlog
Sasho Nikolov
CC BY-SA 3.0
2013-09-30T16:44:30.720Z
2013-09-30T16:44:30.720Z
zotachidil
<p>Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT?</p>

<p>Can the estimates provide sharp lower bound to MAXCUT?</p>

<spectral-graph-theory><max-cut>
Size of MAXCUT from eigenvalues
Turbo
# Size of MAXCUT from eigenvalues

(Asked by: username_0 on 2013-09-30)

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?

**Tags:** spectral-graph-theory, max-cut


---

## 2 answers

### Answer by username_1 on 2013-09-30. Score: 5 | Accepted answer

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](http://arxiv.org/abs/0806.1978). He showed 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 is 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 Williamson, has trivial gap, but despite that an optimal solution to the relaxation actually provides enough guidance to achieve a non-trivial approximation factor.

> **Comments:**
> **username_0**: Thankyou. What is $m$? what is $e(S_1,S_2)$ here? And so we have $MaxCut \leq \frac{\lambda_{n-1}}{2m}$?  
> **username_0**: Can we have a lower bound to $MaxCut$ from eignevalues?  
> **username_1**: I think you did the algebra wrong there, the max cut is at most $m \lambda_{n-1}/2$. This is the easy direction however. Indeed, the second bound is a partial converse. Note that it only says something about the subset $S$, however. In general you cannot lower bound the maximum cut of the entire graph from $\lambda_{n-1}$ because it's possible to have $\lambda_{n-1} = 2$ but the maximum cut being arbitrarily close to its minimum possible value, $m/2$  
> **username_0**: I see that $MaxCut*d_{max}\geq|e(S_1,S_2)|$ and hence $MaxCut\geq\frac{1}{2d_{max}}(1-\sqrt{16\epsilon})Vol(S)$. Is this a sharp lower bound? However there is no eigenvalue here.  
> **username_0**: Correction: $MaxCut\leq\frac{m\lambda_{n-1}}{2}$ holds.  
> **username_0**: "In general you cannot lower bound the maximum cut of the entire graph from λn−1" How about for regular graphs or some graphs with special structure?>  
> **username_0**: Does your updated comment hold for connected graphs with $\lambda_{n-1}<2$? You have mentioned disjoint union as a counter example to my lower bound estimate.  
> **username_1**: as long as you allow a graph that consists of a large graph with small maximum cut and a small bipartite graph, and the two are either disconnected or are connected by a small number of edges, the gap between $2m - 2\text{MaxCut}$ and $2 - \lambda_{n-1}$ can be arbitrarily bad. however, I'd say Luca's partial converse is quite satisfactory.  
> **username_0**: I am interested in a graph sequence that is regular and is not bipartite which also has $MaxCut=\theta(n)$ in my case. That is why I thought may be your comments could be turned into a sharp lowerbound and am I wrong again?  
> **username_1**: So the bad example is quite robust. It's not necessary to have a bipartite connected component: just a small set of vertices that induce a subgraph which is *close to bipartite* and the cut between these vertices and the rest of the graph is small.  
> **username_0**: It seems that $m = O(n^2)$. Does it really give a constant fact result since $\frac{\lambda_{n-1}}{2}\leq 1$?  
> **username_0**: The result here http://www.fmf.uni-lj.si/~mohar/Reprints/1990/BM90_CMJ40_Delorme_MaximumCutProblem.pdf gives $\frac{n\lambda_{n-1}}{4}$. May be it is the way the Laplacians arew defined?  
> **username_1**: About Delorme-Poljak, the difference is because their Laplacian is not normalized, so it is equal to mine muliplied by $D^{1/2}$ on both sides. With respect to your first question, I do not understand what you are asking. Think of $\lambda_{n-1}m/2$ as the relaxation of MaxCut. If the graph is bipartite, $\lambda_{n-1} = 2$. Fan Chung's notes are a good source about basic spectral graph theory: http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf  
> **username_0**: nevermind, the first question was related to the second. You answer answers both.  
> **username_1**: BTW the Delorme-Poljak bound is stronger than the largest eigenvalue of the laplacian and is in fact equivalent to the Goemans-Williamson SDP.  
> **username_0**: How is it stronger? Symbolically both look the same except for the factor of $4$ below and the modified Laplacians?  
> **username_1**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/10867/discussion-between-sasho-nikolov-and-jas)  

---

### Answer by username_2 on 2013-09-30. Score: 3

Yes. The original [Goemans-Williamson paper](http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf) 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](http://arxiv.org/pdf/0806.1978v5.pdf) 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, he essentially looks at the largest eigenvector of the normalized Laplacian in order to isolate components of the graph between which there is a large cut. The core of the analysis is a Cheeger-like inequality for the largest eigenvalue.

> **Comments:**
> **username_0**: "....all traceless" contains complex matrices?  
> **username_2**: No, we're only looking at real matrices.  
> **username_1**: I think since L is real, D the optimal D will be real wlog  

---

