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

Abstract: ErdH{o}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, ErdH{o}s 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 ErdH{o}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.

Review text

Let \(h(n,c)\) denote the maximum number such that every graph \(G\) with \(n\) vertices and at least \(cn^2\) edges, each of which is in a triangle, will contain an edge on at least \(h(n, c)\) triangles. It was conjectured by Erdős that for each \(c > 0\) there is an \(\epsilon > 0\) such that \(h(n, c) > n^\epsilon\). The conjecture of Erdős was disproved by the following result. The existence of a \(G\) graph of order \(n\) sufficiently large with \(\frac{n^2}{4}(1 - e^{-(\log n)^{1/6}})\) edges with the property that every edge is in a triangle, but no edge is in more than \(n^{14/\log \log n}\) triangles was proved.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: On a problem of Erdős and Rothschild on edges in triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448958)