Premium
Szemerédi's partition and quasirandomness
Author(s) -
Simonovits Miklós,
Sós Vera T.
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020102
Subject(s) - combinatorics , lemma (botany) , mathematics , graph , partition (number theory) , discrete mathematics , biology , botany , poaceae
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 (G n ) is quasirandom if and only if in the Szemerédi partitions of G n almost all densities are ½ + o(l).