The Motzkin-Straus Theorem

To fully comprehend this topic, a basic understanding of multivariable calculus is required. A highly recommended reference is [1], specifically Theorem 2.4.15.

Let $\displaystyle G$ be a simple, undirected graph with vertices labeled as $\displaystyle 1, 2, \dots, n$ . Let $\displaystyle S$ be the set of all non-negative real vectors whose components sum to $\displaystyle 1$ :

$\displaystyle S = \left\{ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n \;\middle|\; x_i \ge 0 \text{ for all } i=1,\dots,n, \text{ and } \sum_{i=1}^{n} x_i = 1 \right\}.$

For any vector $\displaystyle x \in S$ , we define the objective function $\displaystyle f(x)$ as the sum of the products of the weights associated with adjacent vertices in $\displaystyle G$ :

$\displaystyle f(x) = \sum_{(i,j) \in E} x_i x_j. \qquad (1)$

Here, each edge $\displaystyle (i,j) = (j,i) \in E$ is counted exactly once. The Motzkin-Straus theorem investigates the maximum value of this function over the set $\displaystyle S$ , denoted as:

$\displaystyle f(G) = \max_{x \in S} f(x) = \max_{x \in S} \sum_{(i,j) \in E} x_i x_j.$

Remark on Existence: The function $\displaystyle f(x)$ defined in (1) is a polynomial, which implies it is continuous everywhere on $\displaystyle \mathbb{R}^n$ . Furthermore, the domain $\displaystyle S$ is a closed and bounded set (a compact set) in $\displaystyle \mathbb{R}^n$ . According to the Extreme Value Theorem, any continuous real-valued function attains both a global maximum and a global minimum on a closed and bounded domain. Therefore, the maximum value $\displaystyle f(G)$ is strictly guaranteed to exist.

Theorem (Motzkin-Straus, 1965). Let $\displaystyle k$ be the clique number (the order of the largest complete subgraph) of $\displaystyle G$ . Then

$\displaystyle f(G)=\frac{1}{2}\left(1-\frac{1}{k}\right). \qquad (2)$

Proof. Suppose $\displaystyle x = (x_1, x_2, \dots, x_n)$ is a point in $\displaystyle S$ that maximizes the function

$\displaystyle f(x) = \sum_{(i,j)\in G} x_i x_j.$

Let $\displaystyle V_x = \{i \mid x_i > 0\}$ be the set of vertices with positive weights. Suppose $\displaystyle V_x$ does not induce a complete subgraph (clique). Then, there exist at least two vertices $\displaystyle u, v \in V_x$ that are not adjacent in $\displaystyle G$ .

Let $\displaystyle S_u = \sum_{j \in N(u)} x_j$ and $\displaystyle S_v = \sum_{j \in N(v)} x_j$ be the sum of the weights of the neighbors of $\displaystyle u$ and $\displaystyle v$ in $\displaystyle G$ , respectively. Without loss of generality, assume that $\displaystyle S_u \le S_v$ .

We construct a new weight distribution $\displaystyle x'$ by shifting the entire weight of $\displaystyle u$ to $\displaystyle v$ :

$\displaystyle x'_u = 0$
$\displaystyle x'_v = x_u + x_v$
$\displaystyle x'_i = x_i$ for all $\displaystyle i \neq u, v$ .

It is clear that $\displaystyle x' \in S$ because the total weight remains $\displaystyle 1$ and all weights remain non-negative. The change in the objective function is given by

$\displaystyle f(x') - f(x) = x_u (S_v - S_u).$

Since $\displaystyle x_u > 0$ and $\displaystyle S_v \ge S_u$ , we have $\displaystyle f(x') \ge f(x)$ . However, because $\displaystyle x$ is already a global maximizer, it must hold that $\displaystyle f(x') = f(x)$ .

The new point $\displaystyle x'$ still achieves the maximum value, but the number of vertices with positive weights has decreased by 1 (since $\displaystyle x'_u = 0$ ). We repeat this weight-shifting process for any remaining pair of non-adjacent vertices with positive weights. This process must terminate after a finite number of steps. Upon termination, all vertices with positive weights must be mutually adjacent, meaning they form a complete subgraph $\displaystyle C$ .

Let $\displaystyle m$ be the number of vertices in $\displaystyle C$ . Since $\displaystyle k$ is the clique number of $\displaystyle G$ , we must have $\displaystyle m \le k$ . On the complete subgraph $\displaystyle C$ , all vertices are pairwise adjacent, so

$\displaystyle f(x) = \sum_{(i,j) \in C} x_i x_j = \frac{1}{2} \left( \left( \sum_{i \in C} x_i \right)^2 - \sum_{i \in C} x_i^2 \right).$

Since the sum of the weights on $\displaystyle C$ is $\displaystyle \sum_{i \in C} x_i = 1$ , we obtain

$\displaystyle f(x) = \frac{1}{2} \left( 1 - \sum_{i \in C} x_i^2 \right).$

By the Cauchy-Schwarz inequality, we have

$\displaystyle \sum_{i \in C} x_i^2 \ge \frac{1}{m} \left( \sum_{i \in C} x_i \right)^2 = \frac{1}{m}.$

This implies $\displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{m} \right).$

Since the function $\displaystyle g(m) = \frac{1}{2}\left(1 - \frac{1}{m}\right)$ is strictly increasing with respect to $\displaystyle m$ and $\displaystyle m \le k$ , we get:

$\displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (3)$

Now, choose a maximum complete subgraph of $\displaystyle G$ with order $\displaystyle k$ . Assume the vertices of this subgraph are $\displaystyle 1, 2, \dots, k$ . By distributing the total weight equally among these $\displaystyle k$ vertices and setting the weights of all other vertices to $\displaystyle 0$ , i.e.,

$\displaystyle x_1 = x_2 = \dots = x_k = \frac{1}{k} \quad \text{and} \quad x_{k+1} = \dots = x_{n} = 0,$

we can compute the value of the objective function at this specific point as:

$\displaystyle f(x) = \binom{k}{2} \cdot \frac{1}{k^2} = \frac{k(k-1)}{2} \cdot \frac{1}{k^2} = \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (4)$

Combining (3) and (4), we conclude that the maximum value of the objective function on the set $\displaystyle S$ is precisely $\displaystyle f(G) = \frac{1}{2}\left(1 - \frac{1}{k}\right).$

This completes the proof. ∎

Corollary (Turán’s Theorem). Let $\displaystyle G$ be a graph with $\displaystyle n$ vertices and edge set $\displaystyle E$ . If $\displaystyle G$ contains no complete subgraph of order $\displaystyle k+1$ (meaning the clique number of $\displaystyle G$ does not exceed $\displaystyle k$ ), then the number of edges in $\displaystyle G$ satisfies

$\displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).$

Proof. Consider the uniform weight distribution $\displaystyle x = \left(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}\right)$ . Clearly, $\displaystyle x \in S$ since all coordinates are non-negative and their sum equals 1.

Evaluating the objective function $\displaystyle f(x)$ at this point, each edge $\displaystyle (i,j) \in G$ contributes exactly $\displaystyle \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n^2}$ . Since the graph $\displaystyle G$ has $\displaystyle |E|$ edges, we have:

$\displaystyle f(x) = \sum_{(i,j) \in G} x_i x_j = \sum_{(i,j) \in G} \frac{1}{n^2} = \frac{|E|}{n^2}.$

On the other hand, by the Motzkin-Straus Theorem, the value of $\displaystyle f(x)$ at any point in $\displaystyle S$ cannot exceed the global maximum $\displaystyle f(G)$ . Let $\displaystyle m$ be the clique number of $\displaystyle G$ . By hypothesis, $\displaystyle m \le k$ . Therefore:

$\displaystyle f(x) \le f(G) = \frac{1}{2} \left( 1 - \frac{1}{m} \right) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right).$

Combining these two results, we obtain $\displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).$

The inequality is thus proven. ∎

References
[1] Jerry Shurman, Calculus and Analysis in Euclidean Space (pages 23-56).

M	T	W	T	F	S	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

The Motzkin-Straus Theorem

Published by Random

Leave a comment Cancel reply

Share this:

Related

Published by Random

Leave a comment Cancel reply