Turan's theorem for pseudo-random graphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:114

Article

Kohayakawa, Yoshiharu ; Roedl, Vojtech ; Schacht, Mathias ; Sissokho, Papa ; Skokan, Jozef

关键词: Turan's theorem;    pseudo-randomness;    regularity lemma;    (n, d, lambda)-graphs;   

DOI  :  10.1016/j.jcta.2006.08.004

来源: Elsevier

【 摘 要 】

The generalized Turan number 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 K-m on m vertices, the value of ex(K-m, H) is (1-1/(chi(H) - 1) + o(1))((m)(2)), where o(1) -> 0 as in -> infinity, by the Erdos-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, Poznan, 1985, North-Holland, Amsterdam, 1987, -pp. 30733 1. MR 89d:051581. A graph G is (q, beta)-bi-jumbled if vertical bar e(G) (X, Y) - q vertical bar X vertical bar vertical bar Y vertical bar vertical bar <= beta root vertical bar X vertical bar vertical bar Y for every two sets of vertices X, Y subset of V (G). Here e(G) (X, Y) is the number of pairs (x, y) such that x is an element of X, y is an element of Y. and xy is an element of E(G). This condition guarantees that G and the binomial random graph with edge probability q share a number of properties.

【 授权许可】

Free