与这些各态历经理论的进展相平行，其他数学家则在寻找用别的方式来理解、重新证明及改进 Szemerédi 定理。Ruzsa 和 Szemerédi 取得了一个重要的概念突破，他们用上面提到的 Szemerédi 正规性引理确立了一些图论中的结果，包括现在被称为三角消除引理（triangle removal lemma）的引理，其大致内容是说一个包含少数三角形的图中的三角形可以通过删除数目少得令人惊讶的边而消除。他们随后发现前面提到的 Behrend 例子对这一引理的定量下界给出了某种极限，特别是它排除了许多类型的初等方法（因为那些方法通常给出多项式型的下界），事实上迄今所知消除引理的所有证明都是通过正规性引理的某些变种。将这一联系反过来应用，人们发现其实三角消除引理蕴含了 Roth 关于长度3序列的定理。这一发现首次开启了通过纯图论技巧证明 Szemerédi 型定理的可能性，从而抛弃了问题中几乎所有的加性结构（注意各态历经方法仍然保留了这一结构，以作用在系统上的移位算符的面目而出现；Szemerédi 的原始证明也只是部分是图论的，因为它在许多不同环节用到了序列的加性结构）。不过，一段时间之后人们才意识到图论方法与先于它出现的 Fourier 分析方法在很大程度上局限于检测象三角形或长度 3 序列那样的“低复杂度”结构，检测更长的序列将需要复杂得多的超图理论。特别是，这启示了（由 Frankl 和 Rödl 率先提出的）一个计划，意在寻找超图理论中正规性引理的类比，这将足以产生象 Szemerédi 定理（及其变种和推广）那样的推论。这被证明是一项复杂得令人吃惊的工作，尤其是要仔细安排这种正规化中参数的等级[13]，使之以正确的顺序相互主导。事实上，能够从中推出 Szemerédi 定理的正规性引理及与之相伴的记数引理（counting lemma）的最终证明直到最近才出现。 Gowers 的很有教益的反例也是值得一提的，它表明原始的正规性引理中的定量下界必须至少是塔状指数形式（tower-exponential），从而再次显示这一引理非同寻常的性质（和力量）。（译者注：1. 三角形消除引理中的“少得令人惊讶”是相对于三角形的数目而言的，它指的是用删除O(n2 )条边来消除O(n3 )个三角形。2. 超图（hypergraph）是普通图的推广，在其中边可以连接两个以上的顶点（类似于多元关系）。）