ON THE EDGE DISTRIBUTION IN TRIANGLE-FREE GRAPHS

Two problems on the edge distribution in triangle-free graphs are cons idered: (1) Given an 0<alpha!<1. Find the largest beta = beta(alpha) s uch that for infinitely many n there exists a triangle-free graph G on n vertices in which every ccn vertices span al least beta n(2) edges. This problem was considered by Erdos, Faudree, Rousseau, and Schelp i n (J. Combin. Theory Ser. B 45 (1988), 111-120). Here we extend and im prove their results, proving in particular the bound beta<1/36 for alp ha=1/2; (2) How much does the edge distribution in a triangle-free gra ph G on n vertices deviate from the uniform edge distribution in a typ ical (random) graph on n vertices with the same number of edges? We gi ve quantitative expressions for this deviation. (C) 1995 Academic Pres s, Inc.