We prove analogues for hypergraphs of Szemer´di’s regularity lemma and e the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemer´di theorem of Furstenberg e and Katznelson, and the first proof that provides an explicit bound. Similar results with the same consequences have been obtained independently by Nagle, R¨dl, Schacht and Skokan. o 1. Introduction Szemer´di’s theorem states that, for every real number δ 0 and every e positive integer k, there exists a positive integer N such that every subset A of the set {1, 2,
