東京大学 情報理工学系研究科 コンピュータ科学専攻 2022年2月実施 問題2

Author

zephyr

Description

Let \(G = (V, E)\) be a simple undirected graph with the vertex set \(V = \{v_i \mid i = 1, \ldots, n\}\) and edge set \(E\). For an \(n\)-dimensional vector \(\mathbf{x} = (x_1, \ldots, x_n) \in \{-1, +1\}^n\), define \(f_G(\mathbf{x})\) by

\[ f_G(\mathbf{x}) = \sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}. \]

Answer the following questions.

(1) For the case where \(G\) is a complete graph \(K_n\) of \(n\) vertices, compute \(a_n = \max_{\mathbf{x} \in \{-1, +1\}^n} f_G(\mathbf{x})\).

(2) Let \(K_n\) and \(a_n\) be those given in question (1). Let \(b_n\) be the number of edges of \(K_n\). Compute

\[ \lim_{n \to \infty} \frac{a_n}{b_n}. \]

(3) Let \(G\) be an arbitrary simple undirected graph. When each \(x_i\) takes a value of either \(-1\) or \(+1\) with probability \(\frac{1}{2}\) independently, compute the expected value of \(f_G(\mathbf{x})\). You may use the linearity of expectation.

(4) Show that, for any simple undirected graph \(G\), there exists some \(\mathbf{x} \in \{-1, +1\}^n\) such that

\[ f_G(\mathbf{x}) \geq \frac{|E|}{2}. \]

Here, \(|E|\) denotes the number of edges of \(G\).

---

令 \(G = (V, E)\) 为一个简单无向图，其顶点集为 \(V = \{v_i \mid i = 1, \ldots, n\}\)，边集为 \(E\)。对于一个 \(n\) 维向量 \(\mathbf{x} = (x_1, \ldots, x_n) \in \{-1, +1\}^n\)，定义 \(f_G(\mathbf{x})\) 为

\[ f_G(\mathbf{x}) = \sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}. \]

回答以下问题。

(1) 当 \(G\) 是一个 \(n\) 个顶点的完全图 \(K_n\) 时，计算 \(a_n = \max_{\mathbf{x} \in \{-1, +1\}^n} f_G(\mathbf{x})\)。

(2) 令 \(K_n\) 和 \(a_n\) 为问题（1）中给出的。令 \(b_n\) 为 \(K_n\) 的边数。计算

\[ \lim_{n \to \infty} \frac{a_n}{b_n}. \]

(3) 令 \(G\) 为任意一个简单无向图。当每个 \(x_i\) 独立地以 \(\frac{1}{2}\) 的概率取 \(-1\) 或 \(+1\) 时，计算 \(f_G(\mathbf{x})\) 的期望值。你可以使用期望值的线性性。

(4) 证明对于任意简单无向图 \(G\)，存在某个 \(\mathbf{x} \in \{-1, +1\}^n\) 使得

\[ f_G(\mathbf{x}) \geq \frac{|E|}{2}. \]

这里，\(|E|\) 表示 \(G\) 的边数。

Kai

(1)

For \(G = K_n\), a complete graph with \(n\) vertices, every pair of distinct vertices is connected by an edge. Thus, the edge set \(E\) has \(\binom{n}{2} = \frac{n(n-1)}{2}\) edges.

To compute \(a_n = \max_{\mathbf{x} \in \{-1, +1\}^n} f_G(\mathbf{x})\), consider the definition of \(f_G(\mathbf{x})\):

\[ f_G(\mathbf{x}) = \sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}. \]

For each edge \((v_i, v_j)\), the term \(\frac{1 - x_i x_j}{2}\) is either \(0\) or \(1\):

\[ \frac{1 - x_i x_j}{2} = \begin{cases} 0 & \text{if } x_i = x_j \\ 1 & \text{if } x_i \neq x_j \end{cases} \]

To maximize \(f_G(\mathbf{x})\), we need to maximize the number of edges where \(x_i \neq x_j\). Let \(k\) be the number of vertices where \(x_i = 1\), and \(n-k\) be the number of vertices where \(x_i = -1\).

The number of edges between vertices with \(x_i = 1\) and \(x_j = -1\) is \(k(n-k)\). Therefore:

\[ f_G(\mathbf{x}) = k(n-k). \]

We need to maximize \(k(n-k)\). The function \(k(n-k)\) is a quadratic function in \(k\) with its maximum value when \(k = \frac{n}{2}\).

Case 1: \(n\) is even

When \(n\) is even, let \(k = \frac{n}{2}\). Then:

\[ a_n = \left(\frac{n}{2}\right)\left(n - \frac{n}{2}\right) = \left(\frac{n}{2}\right)\left(\frac{n}{2}\right) = \frac{n^2}{4}. \]

Case 2: \(n\) is odd

When \(n\) is odd, let \(k = \left\lfloor \frac{n}{2} \right\rfloor\) or \(k = \left\lceil \frac{n}{2} \right\rceil\). Either way, \(k(n-k)\) is maximized when the sizes of the two groups differ by at most one. Therefore:

\[ a_n = \left\lfloor \frac{n}{2} \right\rfloor \left(n - \left\lfloor \frac{n}{2} \right\rfloor \right). \]

or

\[ a_n = \left\lceil \frac{n}{2} \right\rceil \left(n - \left\lceil \frac{n}{2} \right\rceil \right). \]

Since \(\left\lfloor \frac{n}{2} \right\rfloor = \left(\frac{n-1}{2}\right)\) and \(\left\lceil \frac{n}{2} \right\rceil = \left(\frac{n+1}{2}\right)\), we have:

\[ a_n = \left(\frac{n-1}{2}\right)\left(\frac{n+1}{2}\right). \]

Thus:

\[ a_n = \frac{(n-1)(n+1)}{4} = \frac{n^2 - 1}{4}. \]

In conclusion:

\[ a_n = \begin{cases} \frac{n^2}{4} & \text{if } n \text{ is even} \\ \frac{n^2 - 1}{4} & \text{if } n \text{ is odd} \end{cases} \]

(2)

The number of edges in a complete graph \(K_n\) is \(b_n = \binom{n}{2} = \frac{n(n-1)}{2}\).

Using the result from Question 1:

\[ a_n = \begin{cases} \frac{n^2}{4} & \text{if } n \text{ is even} \\ \frac{n^2 - 1}{4} & \text{if } n \text{ is odd} \end{cases} \]

We have:

\[ \lim_{n \to \infty} \frac{a_n}{b_n} = \lim_{n \to \infty} \frac{\frac{n^2}{4}}{\frac{n(n-1)}{2}} = \lim_{n \to \infty} \frac{n^2}{4} \cdot \frac{2}{n(n-1)} = \lim_{n \to \infty} \frac{n}{2(n-1)} = \lim_{n \to \infty} \frac{1}{2} \cdot \frac{n}{n-1} = \frac{1}{2} \]

Thus,

\[ \lim_{n \to \infty} \frac{a_n}{b_n} = \frac{1}{2} \]

(3)

Let \(G = (V, E)\) be an arbitrary simple undirected graph, and \(\mathbf{x} = (x_1, \ldots, x_n) \in \{-1, +1\}^n\) with each \(x_i\) taking values \(-1\) or \(1\) independently with probability \(\frac{1}{2}\).

To find the expected value of \(f_G(\mathbf{x})\), use the linearity of expectation:

\[ \mathbb{E}[f_G(\mathbf{x})] = \mathbb{E}\left[\sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}\right] = \sum_{(v_i, v_j) \in E} \mathbb{E}\left[\frac{1 - x_i x_j}{2}\right] \]

Now, consider \(\mathbb{E}\left[\frac{1 - x_i x_j}{2}\right]\):

\[ \mathbb{E}[x_i x_j] = \mathbb{E}[x_i] \mathbb{E}[x_j] = 0 \cdot 0 = 0 \]

since \(x_i\) and \(x_j\) are independent and each has expectation \(0\) (values are \(-1\) or \(1\) with equal probability).

Thus,

\[ \mathbb{E}\left[\frac{1 - x_i x_j}{2}\right] = \frac{1 - \mathbb{E}[x_i x_j]}{2} = \frac{1 - 0}{2} = \frac{1}{2} \]

Therefore,

\[ \mathbb{E}[f_G(\mathbf{x})] = \sum_{(v_i, v_j) \in E} \frac{1}{2} = \frac{|E|}{2} \]

(4)

To show that there exists some \(\mathbf{x} \in \{-1, +1\}^n\) such that \(f_G(\mathbf{x}) \geq \frac{|E|}{2}\), consider the expected value derived in Question 3.

We have:

\[ \mathbb{E}[f_G(\mathbf{x})] = \frac{|E|}{2} \]

Since \(\mathbb{E}[f_G(\mathbf{x})]\) is the average value of \(f_G(\mathbf{x})\) over all possible \(\mathbf{x} \in \{-1, +1\}^n\), there must be at least one particular \(\mathbf{x} \in \{-1, +1\}^n\) for which \(f_G(\mathbf{x}) \geq \frac{|E|}{2}\). Otherwise, the average value could not be \(\frac{|E|}{2}\).

Therefore, there exists some \(\mathbf{x} \in \{-1, +1\}^n\) such that:

\[ f_G(\mathbf{x}) \geq \frac{|E|}{2} \]

Knowledge

图论 期望值 极大值

难点解题思路

在第 1 题中，找到使得 \(f_G(\mathbf{x})\) 最大的 \(\mathbf{x}\) 是关键。在处理完全图时，可以通过对称性和顶点划分来简化问题。对于一般图，期望值和线性期望的使用使得问题更易处理。

解题技巧和信息

对于复杂的图论问题，可以通过图的对称性来简化问题。期望值的计算可以利用线性期望的性质，使得问题转化为求和问题。求极大值时，可以考虑图的特殊结构，例如完全图的顶点划分。

重点词汇

• graph 图
• complete graph 完全图
• edge 边
• vertex 顶点
• expected value 期望值

参考资料

1. Bollobás, B. (1998). Modern Graph Theory. Springer. Chap. 1-3.