On universality of graphs with uniformly distributed edges (Q1089355)

Let \(\gamma\), \(\delta\), \(\sigma\) be positive reals smaller than 1. Define a graph \(G=(V,E)\) to have property (\(\gamma\),\(\delta\),\(\sigma)\) if the number of edges in the induced subgraph \(<S>\), for every \(S\subset V\) with \(| S| \geq \gamma | V|\), lies in the interval \(\left[(\sigma-\delta)\left(\begin{matrix} | S| \\ 2\end{matrix} \right),(\sigma +\delta)\left( \begin{matrix} | S| \\ 2\end{matrix} \right)\right]\). The author proves the following two theorems. (1) For every positive integer k and every \(\sigma\) and \(\delta\) such that \(\delta <\sigma <1-\delta\) there exist \(\gamma\) and a positive integer \(N_ 0\) such that every graph with at least \(N_ 0\) vertices, having the property (\(\gamma,\delta,\sigma)\) contains all graphs with k vertices as induced subgraphs. (2) For every positive integer k and for every \(\sigma\) and \(\gamma\), there exist a \(\delta\) and a positive integer \(N_ 1\) such that every graph with at least \(N_ 1\) vertices and having the property (\(\gamma\),\(\delta\),\(\sigma)\) contains all graphs with k vertices as induced subgraphs. In simpler words these mean that sufficiently large graphs with sufficiently many 'uniformly distributed' edges contain all small graphs as induced subgraphs. This fails to be true for k-uniform hypergraphs with \(k\geq 3.\) The second theorem gives a 'stronger' affirmative answer to a problem posed by Erdős whether every sufficiently large graph having the property (1/2,\(\delta\),1/2) contains \(K_ k\) as an induced subgraph.