Paper Info
Title
On a problem of Erdös and Rothschild on edges in triangles.
Abstract
Abstract Erdös and Rothschild asked to estimate the maximum number, denoted by h(n, c), such that every n-vertex graph with at least cn 2 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) = n O(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 n 2/4 edges contains an edge that is in at least n/6 triangles.
Year
DOI
Venue
2012
10.1007/s00493-012-2844-3
Combinatorica
Keywords
DocType
Volume
05C35
Journal
32
Issue
ISSN
Citations 
6
1439-6912
0
PageRank 
References 
Authors
0.34
7
2
Name
Order
Citations
PageRank
Jacob Fox127625.20
Po-Shen Loh213318.68