### The spectral proof of the Szemeredi regularity lemma

November 13, 2015

There are many proofs of this lemma, which is actually not that difficult to establish; see for instance these previous blog posts for some examples. In this post I would like to record one further proof, based on the spectral decomposition of the adjacency matrix of , which is essentially due to Frieze and Kannan. … More The spectral proof of the Szemeredi regularity lemma