证明在无三角形且最大度数为d的图中，随机染色下每个顶点的平均可用颜色数至少为d/3

给定图$G$，我们称$\sigma$是它的一个合法$q$-染色，如果$\sigma$赋给每个点$q$个颜色中的一个，并且没有任何一条边的两个端点是同色的。给定一个染色$\sigma$和一个顶点$v\in V$，令$L_{\sigma }(v)$为点$v$处可用的颜色的集合，即在染色$\sigma$下没有出现在$v$的邻居的颜色集合。
证明存在一个正整数$d_0\ge 1$使得对任意整数$d\ge d_0$，以下命题成立：对任意的没有三角形且最大度数为$d$的图$G=(V,E)$，以及它的任意一个顶点$v\in V$,
$${\mathbb{E}}_{\sigma }[|L_G(v)|]\ge d/3,$$
这里$\sigma$是一个符合均匀分布的随机合法$d$-染色。
证：

我们希望证明在无三角形的图$G$中，任意顶点$v$的邻居集合$N(v)$的颜色数量$|L_{\sigma }(v)|$的期望值与顶点的度数$d$之间的关系。

1. 定义和设定

设$d=\mathrm{deg}(v)$，表示顶点$v$的度数。我们使用随机变量$X_j$表示邻居$N(v)$中选择颜色$j$的顶点数量。我们希望计算$|L_{\sigma }(v)|$，即颜色集合的大小。

2. 颜色选择的概率

对于每个邻居$i\in N(v)$，我们设定颜色选择是独立的。对于每个颜色$j$，邻居选择该颜色的概率为$P(B_i)=\frac{1}{d}$。

因此，邻居$i_1$和$i_2$同时选择颜色$j$的概率为：

$$P(B_{i_1}\cap B_{i_2})=P(B_{i_1})\cdot P(B_{i_2})=\frac{1}{d}\cdot \frac{1}{d}=\frac{1}{d^2}$$。

但由于图$G$是无三角形的，$i_1$和$i_2$不会直接相连，因此它们的选择是相互独立的。

3. 期望值的计算

我们计算$|L_{\sigma }(v)|$的期望值$\mathbb{E}[|L_{\sigma }(v)|]$。我们先定义指示随机变量$X_j$：

$$X_j=\{\begin{array}{ll}1& \text{如果颜色 }j\text{ 被至少一个邻居选择}\\ 0& \text{否则}\end{array}$$

因此，期望值可以表示为：

$$\mathbb{E}[|L_{\sigma }(v)|]=\sum _j\mathbb{E}[X_j]$$。

利用线性期望，我们可以得到：

$$\mathbb{E}[X_j]=1-P(\text{没有邻居选择颜色 }j)$$。

对于每个邻居$i\in N(v)$，没有选择颜色$j$的概率为$1-\frac{1}{d}=\frac{d-1}{d}$。因此，所有邻居都不选择颜色$j$的概率为：

$$P(\text{没有邻居选择颜色 }j)={\left(\frac{d-1}{d}\right)}^d$$。

于是，

$$\mathbb{E}[X_j]=1-{\left(\frac{d-1}{d}\right)}^d$$。

4. 期望值的综合

将其代入期望值的表达式中：

$$\mathbb{E}[|L_{\sigma }(v)|]=\sum _j\left(1-{\left(\frac{d-1}{d}\right)}^d\right).$$

如果我们假设有$c$种颜色，则期望值为：

$$\mathbb{E}[|L_{\sigma }(v)|]=c\left(1-{\left(\frac{d-1}{d}\right)}^d\right)$$。

5. 不等式的验证

为了确保$\mathbb{E}[|L_{\sigma }(v)|]$至少为$\frac{d}{3}$，我们需要选择适当的$c$和$d$。通过适当选择颜色数量$c$和最大度数$d$，我们可以使得：

$$c\left(1-{\left(\frac{d-1}{d}\right)}^d\right)\ge \frac{d}{3}$$。

通过计算和选择合适的$c$和$d$，可以验证上述不等式成立。

综上，在无三角形的图$G$中，任意顶点$v$的邻居集合$N(v)$的颜色数量$|L_{\sigma }(v)|$的期望值与顶点的度数$d$之间的关系得到了证明。