​ 用概率论来求解一个问题，称作概率方法。本文将简要介绍一下概率方法，并介绍荆老师在加性组合课上[1]讲述的两个问题。

一、基本的概率方法

​ 设P是某种性质，A是一个集合。我们常常要证明集合A包含满足性质P的子集B。有一个充分条件：对A中以某种方式随机选取的子集B，概率 P(B满足性质P)＞0。

​ 我们用n-一致超图（每条边上都恰有n个点的超图）上一个与2-点染色有关的命题 来作为一个实例：

​ 如果性质P有关子集大小的上下界，我们就可以通过计算 某种方式随机选取的子集B的数学期望E|B|，来得到P(B满足性质P)＞0。这是因为P(|B|≥E|B|)＞0，P(|B|≤E|B|)＞0。接下来的几个问题均为通过计算数学期望来得到子集的存在性。

第一个问题：二维实数空间里点与线的相交数

​ 如果在二维实数空间中有一个n个点构成的集合P，与一个m个直线构成的集合L。我们自然而然地会对点与直线相交（一个点落在一条直线上称这个点与这条线相交）的总数产生兴趣。著名的Szemeredi-Trotter定理告诉我们，相交数I(P,L)满足
$$
\mathbf{I}(\mathcal{P}, \mathcal{L}) \ll n^{2 / 3} m^{2 / 3}+n+m
$$

这里g(n)≪ f(n) 定义为 f非负，且存在一个正常数C，使|g(n)|≤ Cf(n)对所有的n成立。

​ Szemeredi-Trotter也给出了另一个定理，本文将介绍这一定理中用到了概率方法的地方：

​ 定义 r-rich points 为 P中 至少与r条直线相交的所有点 组成的子集，Pr(L) 为这个子集所含的元素的个数。Szemeredi-Trotter的另一个定理告诉我们
$$
\mathbf{P}_{\mathbf{r}}(\mathcal{L})^{*} \ll m r^{-1}+m^{2} r^{-3}
$$
这个定理的证明需要三个引理，引理3用到了基础的概率方法，我们将在这里给出这个引理的证明。

​ 记Cr(G)为 在平面上画出图G所产生的最少edge crossings 数，如Cr(K5)=1（这里的画法不允许出现＞2条边交叉于同一点、两边相切、完全多余的相交）。记V和E分别为图G的顶点数和边数。

​ 由平面图上的欧拉定理容易得出

Lemma1: 如果G是平面图(Cr(G)=0)，则E ≤ 3V-6.

​ 由于在一个图的有Cr(G)条边的画法中可以去掉至多Cr(G)条边使之变为平面图，结合引理1，有

Lemma2: 对任意一个图G，Cr(G) ≥ E-3V+6.

​ 用概率方法可以得出引理3（crossing number 不等式），我们来详细叙述它的证明：

第二个问题：Erdos 关于 sum-free 集 的一个问题

​ 考虑一个加性群上的加性集A。如果A不包含x，y，z使x+y=z，则称A为sum-free 集。

​ 对于任意一个不含0的正整数构成的集合A，我们对它的最大sum-free 子集的大小感兴趣，记为M(A)。根据定义，很容易可以得到M({1,2…n})≤n/2 。

​ 对于一般的不含0的正整数构成的集合A(以下默认A是这样的集合)，Erdos在1965年提出了一个问题：如果*|A|=n，M(A)*会是怎样？

​ 在同一篇paper里，Erdos给出了M(A)的一个下界，证明中用到了概率方法：

​ 这里的界不能通过改变Ω的大小来改善，这是因为如果Ω在其上可测，则Ω的测度是不超过1/3的。

​ 关于M(A)的界，还有一个比较新的定理，被Ehrhard Green Mauers三人在2013年给出：

​ 这个定理的证明用到了概率方法，也用到了非标准分析的方法，我还没怎么看懂。感兴趣的同学可以去b站看荆老师的课程录屏。

参考文献：

[1]荆一凡：”Additive Combinatorics” in SDU https://www.bilibili.com/video/BV1154y1s7Mm