Thursday, October 31, 2013 - 12:00
427 Thackeray Hall
Abstract or Additional Information
Erdös and Rothschild asked to estimate the maximum number, denoted by h(n,c), such that every n-vertex graph with at least cn2 edges, each of which is contained in at least one triangle, must contain an edge that is in at least h(n,c) triangles. In particular, Erdös asked in 1987 to determine whether for every c>0 there is ϵ>0 such that h(n,c)>nϵ for all sufficiently large n. We prove that h(n,c)=nO(1/loglogn) for every fixed c<1/4. This gives a negative answer to the question of Erdös, and is best possible in terms of the range for c, as it is known that every n-vertex graph with more than n2/4 edges contains an edge that is in at least n/6 triangles.
Joint work with Jacob Fox.