Combinatorics Seminar
When: Sunday, December 18, 10am
Where: Schreiber 309
Speaker: Po-Shen Loh, Carnegie Mellon University
Title: On a problem of Erdos and Rothschild on edges in triangles
Abstract:
Erdos 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, Erdos asked in 1987 to determine whether for every c>0
there is epsilon>0 such that h(n,c)>n^{epsilon} 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.
Joint work with Jacob Fox.