Turán's theorem for pseudo-random graphs (Q880006): Difference between revisions

This paper deals with Túran number ex\((G,H)\) of two graphs \(G\) and \(H\). It is defined as the maximum number of edges in a subgraph of \(G\) not containing \(H\). When \(G\) is the complete graph \(K_m\) on \(m\) vertices, the asymptotic behavior of ex\((K_m,H)\) is determined by a classical Erdős-Stone-Simonovits theorem. In the present paper the authors obtain an analogous result for triangle-free graphs \(H\) and pseudo-random graphs \(G\). The concept of pseudo-randomness is inspired by the jumbled graphs introduced by \textit{A. Thomason} [Ann. Discrete Math. 33, 307--331 (1987; Zbl 0632.05045)]. These graphs are defined as follows. A graph \(G\) is \((q,\beta)\)-bi-jumbled if \(| e_G(X,Y)-q| X|| Y||\leq\beta\sqrt{| X|| Y|}\) for every two sets \(X, Y\) of vertices of \(G\). Here \(e_G(X,Y)\) is the number of pairs \((x,y)\) such that \(x\in X, y\in Y\) and \(xy\) presents an edge in \(G\). This condition implies that \(G\) and the binomial random graph with edge probability \(q\) share a number of properties. The main result of this paper implies, for instance, that for any triangle-free graph \(H\) with maximum degree \(\Delta\) and for any \(\delta>0\) there exists \(\gamma>0\) so that the following holds: any large enough \(m\)-vertex, \((q,\gamma q^{\Delta+1/2}m)\)-bi-jumbled graph \(G\) satisfies ex\((G,H)\leq\{1-1/[\chi(H)-1]+\delta\}| E(G)|\). Here \(\chi(H)\) and \(| E(G)|\) denote the chromatic number of \(H\) and the cardinality of the edge-set of \(G\), respectively.