Today I did something for the first time ever that I should have done many times before: I put a paper on the ArXiV. Since I’ve got a blog I thought I’d use it to give the paper a small plug and, more importantly, to let anybody who might already be familiar with the paper know that I have revised it quite a bit recently, for the better.

The paper itself is called “Hypergraph regularity and the multidimensional Szemerédi theorem.” At the bottom level, the basic idea of the paper is due to Ruzsa, Szemerédi and Rödl. Ruzsa and Szemerédi started the ball rolling with a short and very clever argument that showed that Szemerédi’s famous theorem on arithmetic progressions, in the case of progressions of length 3, could be deduced from Szemerédi’s almost as famous *regularity lemma*, a remarkable result that allows any graph to be partitioned into a bounded number of pieces, almost all of which “behave randomly.” (more…)