Sparse quasi-random graphs (Q1848147): Difference between revisions

Let \(G_{1/2}(n)\) denote a random graph with \(n\) vertices in which each pair is selected to be an edge independently with probability \(1/2\). Almost all of them satisfy several basic properties which turn out to be equivalent. Families of graphs satisfying this equivalence class of properties are called quasi-random, see e.g. \textit{F. R. K. Chung}, textit{R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, 345--362 (1989; Zbl 0715.05057)]. So far most of the results dealt with dense quasi-random graphs (having \(cn^2\) edges for some \(c>0\) as \(n \rightarrow \infty\)). This article studies quasi-random graphs with \(o(n^2)\) edges for analogous results, which are more difficult, due for example to the possible absence of certain local structures, such as 4-cycles.