文献综述（或调研报告）：
为了让读者相信概率方法的力量，我们提出了一个关于这种证明方法的非常简单的图的交叉数的应用。根据图的阶数和大小，得到图的交叉数的下界，然后利用这个下界导出组合几何中的两个定理。
回想一下，图G的交叉数cr(G)是G的平面嵌入中交叉数最少的一个。这个参数满足琐碎下届（事实上当；练习 10.3.1）。阿贾泰(Ajtai)等人(1982)和莱顿(Leighton)(1983)各自独立地给出了更强的下界。它更短的证明由阿隆(N. Alon)给出；见阿隆和斯宾塞(Alon and Spencer)(2000)。
设G是一个简单图且。则有
定义上的随机变量如下所示：X是顶点数，Y是边数，Z是的交叉数。当应用到H时，上面所述的琐碎边界就产生了不等式。根据期望的线性定义(13.4)，。现在有，（每条边有两个端点）和（每个交点由四个顶点定义）。所以有
两边同时除以，我们有：
塞凯伊()(1997)认识到交叉引理(13.1)能被用来很简单地推导出组合几何中的许多定理，其中一些迄今被认为极具挑战性。现在我们给出其中两个的证明。
考虑平面上n个点的集合。其中任意两点决定一条直线，但也有可能其中一些直线经过两个以上的点。具体来说，给定一个正整数k，有人可能会问有多少条直线可以通过至少k个点。例如，如果n是一个完全平方数并且这些点以正方形网格的形式表示，则有条线通过个点。那么是否存在这样一种点的构型，它包含更多的直线穿过这个点的数量。
剩余内容已隐藏，您需要先支付 10元 才能查看该篇文章全部内容！立即支付
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
