On the Edge Distribution in Triangle-free Graphs

Two problems on the edge distribution in triangle-free graphs are considered: (1) Given an 0 < α < 1. Find the largest β = β(α) such that for infinitely many n there exists a triangle-free graph G on n vertices in which every αn vertices span at least βn2 edges. This problem was considered by Erdo&#x030B;s, Faudree, Rousseau, and Schelp in (J. Combin. Theory Ser. B45 (1988), 111-120). Here we extend and improve their results, proving in particular the bound β < 136 for α = 12; (2) How much does the edge distribution in a triangle-free graph G on n vertices deviate from the uniform edge distribution in a typical (random) graph on n vertices with the same number of edges? We give quantitative expressions for this deviation.