你所期望的图中的一个三角形是:三个顶点彼此相连。一个独立集是一个顶点的集合,他们彼此没有边相连。这里给出一个简单的论述来证明,一个具有个顶点的图一定包含一个三角形或者包含一个大小为的独立集。等价地说,如果一个图既不包含三角形,也不包含大小为k的独立集,那么它的顶点个数一定小于,这实际上是我要证明的。论述如下。令是图中的任意一个顶点。与关联的任何两个顶点都不会有边相连,因为那样的话我们就有一个三角形。因此,与关联的所有顶点构成一个独立集。于是不能跟多于个其他顶点关联(因为我们假设这个图不包含大小为的独立集)。现在我们设想来尝试寻找一个大的独立集。我们做这件事的一种方法是去寻找一个顶点的序列,,…,确保我们选择的每个新的顶点跟之前选过的任何顶点都不关联。我们能做到这点吗?假设目前为止我们已经选择了顶点,,…,其中每一个都关联于至多顶点,所以它们之间至多关联个顶点。因此,当选择一个新顶点时,我们必须回避至多个顶点。所以只要顶点的数目超过,我们就可以扩展这个序列。如果我们想得到从到,那么我们需要的顶点数目要超过。因为,所以如果我们有个顶点,我们将能继续我们的序列直到至少,于是这给了我们一个大小为的独立集。我们真的需要那么多个顶点来保证一个三角形或者一个大小为的独立集吗?我们可以给出一个比稍微强一点的结果:个顶点就足够了。但是存在个顶点的图,它既不包含三角形,也不包含大小为的独立集吗?如果不存在,这样的图可以有多少个顶点呢?满足这些的最大可能的数称为Ramsey数。上面的讨论(根据数学研究的标准)是非常简单的,但是确定是否可以改进它被证明是非常困难的。这就是AKS解决的问题:他们证明至多为乘以一个常数因子。如果你真的希望欣赏一下这个成就,你就应该花一点时间自己来考虑一下这个问题,但是如果你没有时间,那么你至少要记住这个问题已经有几十年的历史了,而且15年后Jeong Han Kim在另一篇著名的文章中证明了这个结果是最好的:即不会超过,而且实际上等于(仅相差一个常数因子)。为了证明他们的结果,AKS可以比上面讲到的简单论述做得更好。极其粗略地,他们用的是同样的讨论,但是用一种更谨慎的方式处理的。回忆一下基本的想法是选择顶点,,…并且回避你所选顶点的邻点。我们可以描述这个程序如下。从整个图出发,我们选择一个顶点,并且扔掉它的所有邻点;然后从图的剩余部分选择顶点,并且扔掉它的所有邻点。我们这样继续做下去。因为任何顶点的邻点个数都不会超过,所以每一步我们不会扔掉太多的顶点,因此我们可以持续相当长的一段时间。现在如果我们在程序的任何一步中,发现了一个顶点,它的邻点数目远小于,那么我们将会非常高兴:我们将选取那个顶点,并且我们不需要扔掉图的那么多个顶点,所以程序可以持续的更长。但是我们可以找到这样的顶点吗?最开始的时候,没有任何原因。但是我们确实对这个程序给出了某个控制:当我们选择一个顶点的时候,我们扔掉它的邻点。如果这些邻点本身有很多的邻点,那么当我们将它们扔掉的时候,我们也将会扔掉很大数目的边。所以基本的想法是以这样的方式选择序列,,…:尽量减少没有被扔掉的图的那部分边的数目。AKS证明将这个想法继续下去是可能的,并且最终会延长这一进程使得算法将会持续大约次,只要那个简单的论断成立。上面我所暗示的讨论并不是 AKS给出的原始证明,但是描述起来比较容易。他们早期的讨论也是非常重要的,因为它是称为半随机方法的一个较早的例子,这里我将不再讨论,但是我想说这是另一种具有很多应用的技巧。