Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs (Q1276304): Difference between revisions

The work can be considered as continuation of \textit{F. R. K. Chung, R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, No. 4, 345-362 (1989; Zbl 0715.05057)] on quasi-random properties of graphs. A \(G_n\) sequence of graphs is quasi-random if it exhibits some behavior of random graph properties asymptotically, and it turns out that a number of equivalent properties ensure this. Informally these assumtions can be summerized as \(G_n\) contains about the same number of subgraphs as the appropriate \(G_{n, p}\) does. However, assumptions on certain subgraphs do not imply quasi randomness, such as the subgraphs having 3 vertices, the odd cycles, or the cutsets of size \(\lfloor n/2 \rfloor\), where \(n\) is the number of vertices. The main idea of the paper is that the properties above still imply the quasi randomness of \(G_n\) if one imposes them not only on the members of \(G_n\) but on the induced subgraphs also. The proofs heavily use the so-called Szemerédi partitions and the celebrated regularity lemma.