IS CS-2022W-02

题目来源：Problem 2 日期：2024-07-18 题目主题：CS-离散数学-图论

具体题目

Let $G=(V,E)$ be

a simple undirected graph with the vertex set $V=\{v_i\mid i=1,\dots ,n\}$ and edge set $E$. For an $n$-dimensional vector $\mathbf{x}=(x_1,\dots ,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

$$\underset{n\to \infty }{\lim }\frac{a_n}{b_n}.$$

1. 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.
2. Show that, for any simple undirected graph $G$, there exists some $\mathbf{x}\in \{-1,+1{\}}^n$ such that

$$f_G(\mathbf{x})\ge \frac{|E|}{2}.$$

Here, $|E|$ denotes the number of edges of $G$.

正确解答

Question 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 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\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{array}{ll}0& \text{if }{x}_i=x_j\\ 1& \text{if }{x}_i\ne x_j\end{array}$$

To maximize $f_G(\mathbf{x})$, we need to maximize the number of edges where $x_i\ne 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=\lfloor \frac{n}{2}\rfloor$ or $k=\lceil \frac{n}{2}\rceil$. Either way, $k(n-k)$ is maximized when the sizes of the two groups differ by at most one. Therefore:

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

or

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

Since $\lfloor \frac{n}{2}\rfloor =\left(\frac{n-1}{2}\right)$ and $\lceil \frac{n}{2}\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{array}{ll}\frac{n^2}{4}& \text{if }n\text{ is even}\\ \frac{n^2-1}{4}& \text{if }n\text{ is odd}\end{array}$$

Question 2

The number of edges in a complete graph $K_n$ is $b_n=\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$.

Using the result from Question 1:

$$a_n=\{\begin{array}{ll}\frac{n^2}{4}& \text{if }n\text{ is even}\\ \frac{n^2-1}{4}& \text{if }n\text{ is odd}\end{array}$$

We have:

$$\underset{n\to \infty }{\lim }\frac{a_n}{b_n}=\underset{n\to \infty }{\lim }\frac{\frac{n^2}{4}}{\frac{n(n-1)}{2}}=\underset{n\to \infty }{\lim }\frac{n^2}{4}\cdot \frac{2}{n(n-1)}=\underset{n\to \infty }{\lim }\frac{n}{2(n-1)}=\underset{n\to \infty }{\lim }\frac{1}{2}\cdot \frac{n}{n-1}=\frac{1}{2}$$

Thus,

$$\underset{n\to \infty }{\lim }\frac{a_n}{b_n}=\frac{1}{2}$$

Question 3

Let $G=(V,E)$ be an arbitrary simple undirected graph, and $\mathbf{x}=(x_1,\dots ,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}$$

Question 4

To show that there exists some $\mathbf{x}\in \{-1,+1{\}}^n$ such that $f_G(\mathbf{x})\ge \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})\ge \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})\ge \frac{|E|}{2}$$

知识点

图论期望值极大值

难点解题思路

在第 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.