Carnegie Mellon University
Browse
file.pdf (278.75 kB)

On a problem of Erdős and Rothschild on edges in triangles

Download (278.75 kB)
journal contribution
posted on 2011-06-01, 00:00 authored by Jacob Fox, Po-Shen Loh

Erdos 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, Erdos 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) = n O(1/ log log n) for every fixed c < 1/4. This gives a negative answer to the question of Erdos, and is best possible in terms of the range for c, as it is known that every n-vertex graph with more than n 2/4 edges contains an edge that is in at least n/6 triangles.

History

Date

2011-06-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC