A simple algorithm for constructing Szemerédi's regularity partition (Q1283876): Difference between revisions

Szemerédi's regularity lemma is often used to prove the existence of certain objects and if in addition one whises to construct them, one needs a constructive version of the lemma. This was provided by \textit{N. Alon}, \textit{R. A. Duke}, \textit{H. Lefmann}, \textit{V. Rödl} and \textit{R. Yuster} [J. Algorithms 16, No. 1, 80-109 (1994; Zbl 0794.05119)]. In this short paper, the authors give another construction based on the use of singular values of matrices.