合缝证明样本（一些我非常喜爱的组成证实）

合缝证明样本：一些我非常喜爱的组成证实

数学课话题讨论下的出色回答者

1.Sylvester-GallaiTheorem:上随意个不全相切的点，最少存有一条平行线正好通过在其中的两个点。（CO.IncidenceGeometry）

Remark：合缝证明样本

里边提及过一些事例（题图），这个问题对一般的field不创立，因此出题并不平凡，一定要使用实数域特有的特性。

Pf(byGallai)：合缝证明样本

随意点集，过点集任意两个点做一条平行线。考虑到全部没有在平行线上的点至全部那样的平行线的间距组成的结合，因为是有限集，存有点到直线的间距为最短路线。过对做垂直线，垂足为。

假如正好只过两个点，出题创立。

假定与此同时通过点，那麼最少两个点在同一侧，设其为而且到间距更远。那麼到过平行线的间距比到距离严苛小，分歧。

（byB.GreenandT.Tao）：合缝证明样本

如果是双数，那样的平行线最少条；如果是单数，最少条。

2.Roth'sTheorem:假如结合达到，那麼包括无限多长短为的等差数列。（CO.AdditiveCombinatorics）

Remark：原证实是解析的。可是这个问题具体是问，对整数集用比较有限种色去上色，一定存有长短为的等差数列中三个数同色，这是一个Ramsey问题，因而可以应用纯图论方式。

Pf(bySzemeredi)：为了更好地描述便捷，大家用替代。针对三部图，点集分成三一部分，在其中每一部分全是。

如下图，对随意中的点，中的点，中的点，与有边相接当且仅当；与相连当且仅当；与相接当且仅当

那麼长短为的等差数列便是图上的三角形，有着尺寸公差。考虑到假如中沒有等差数列，这时中仅有尺寸公差为的普普通通三角形，图上有一个点，条边，每一条边在且仅在一个三角形中。

运用countinglemma：假如一个图每一条边都只在一个三角形中，那麼边的数目非常少（）。

返回图，有，则，分歧。

（byB.GreenandT.Tao）：在Szemeredi证实正相对密度集存有随意长等差数列后，她们完成的营销推广了SzemerediTheorem到一个零相对密度集（素数）上。

3.CrossingNumberInequality:假如图有一个点条边，且，那麼。（CO.GraphTheory）

Remark：是将一个图用simplecurve画在水平面上，促使边有着至少的相交的数量。实际界定在

Pf(byLeighton)：考虑到图正好有一个相交点的怎么画，在每一个相交点处清除一条边，获得了一个有一个点条边的总平面图。由欧拉公式，显而易见，获得.

如今从这当中单独的以几率为的选择端点获得子图，中两点之间有边当且仅当这两个点在中国有边。针对大家有，且达到。因此，带入，可以获得，取即证。

Remark2：这个问题最开始由Szemeredi和他的合作方们用拓扑结构方式证实，证明较长而且只对减弱界定下的crossingnumber创立。以后Leighton用几率方式几行就证出来了更强的結果，这大约便是组成数学的魅力。

最新消息：缺憾的是迄今沒有升级的进度了，有关paper许多，可是如今连一些最独特的图的crossingnumber我们都不清楚。