Hypergraph regularity and the multidimensional Szemeredi theorem

• 成果类型: Article
• 署名作者: Gowers, W. T.
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2007.166.897
• 发表日期: 2007
• 页码: 897-946
• 关键词: k-uniform hypergraphs; lemma; PROOF

摘要

We prove analogues for hypergraphs of Szemeredi's regularity lemma and the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemeredi theorem of Furstenberg and Katznelson, and the first proof that provides an explicit bound. Similar results with the same consequences have been obtained independently by Nagle, Rodl, Schacht and Skokan.