Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Motzkin-Straus theorem says that the global optimum of the quadratic program $$\max f(x)=\frac{1}{2} x^{t}Ax,\qquad \mbox{ subject to }\sum x_{i}=1 \mbox{ and } x_{i}\geq 0,$$ where $A$ is the adjacency matrix of a simple, undirected graph $G$, is given by $\frac{1}{2} \left(1-\frac{1}{\omega(G)}\right)$, where $\omega(G)$ is the clique number.
Given a local maximum $x$ of the program, let $s(x)=\lbrace 1 \leq i \leq n: x_{i}>0 \rbrace$, and denote by $N(i)$ the set of (indices of) vertices adjacent to the vertex $i$.

In different presentations of the theorem, one finds at some point something like "let $i,j \in s(x)$ and assume without loss of generality that $\sum_{k \in N(i)}x_{k}\geq \sum_{k \in N(j)}x_{k}$..." But it seems to me that these sums must be equal: taking a small enough positive $\epsilon$ and denoting by $u$ the vector such that $u_{i}=-\epsilon$, $u_{j}=\epsilon$ and $u_{l}=0$ otherwise, we have

$$ 0 \geq f(x+u)-f(x)=-\epsilon \sum_{k \in N(i)}x_{k}+\epsilon \sum_{k \in N(j)}x_{k}-2 \epsilon^{2}a_{i j},$$ wich implies the above inequality (in fact, for any $i \in s(x)$ and any $j$). Am I missing something? Thanks in advance!

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.