MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.