Turán's theorem for pseudo-random graphs

The generalized Turán number ex(G,H)ex(G,H) of two graphs G and H is the maximum number of edges in a subgraph of G not containing H. When G   is the complete graph KmKm on m   vertices, the value of ex(Km,H)ex(Km,H) is (1−1/(χ(H)−1)+o(1))(m2), where o(1)→0o(1)→0 as m→∞m→∞, by the Erdős–Stone–Simonovits theorem.In this paper we give an analogous result for triangle-free graphs H and pseudo-random graphs G. Our concept of pseudo-randomness is inspired by the jumbled graphs introduced by Thomason [A. Thomason, Pseudorandom graphs, in: Random Graphs '85, Poznań, 1985, North-Holland, Amsterdam, 1987, pp. 307–331. MR 89d:05158]. A graph G   is (q,β)(q,β)-bi-jumbled if|eG(X,Y)−q|X||Y||⩽β|X||Y| for every two sets of vertices X,Y⊂V(G)X,Y⊂V(G). Here eG(X,Y)eG(X,Y) is the number of pairs (x,y)(x,y) such that x∈Xx∈X, y∈Yy∈Y, and xy∈E(G)xy∈E(G). This condition guarantees that G and the binomial random graph with edge probability q share a number of properties.Our results imply that, for example, for any triangle-free graph H with maximum degree Δ   and for any δ>0δ>0 there exists γ>0γ>0 so that the following holds: any large enough m  -vertex, (q,γqΔ+1/2m)(q,γqΔ+1/2m)-bi-jumbled graph G satisfiesex(G,H)⩽(1−1χ(H)−1+δ)|E(G)|.