Szemerédi's partition and quasirandomness |
| |
Authors: | Mikls Simonovits Vera T Ss |
| |
Institution: | Miklós Simonovits,Vera T. Sós |
| |
Abstract: | In this paper we shall investigate the connection between the Szemerédi Regularity Lemma and quasirandom graph sequences, defined by Chung, Graham, and Wilson, and also, slightly differently, by Thomason. We prove that a graph sequence (Gn) is quasirandom if and only if in the Szemerédi partitions of Gn almost all densities are ½ + o(l). |
| |
Keywords: | |
|
|