Books versus triangles

Abstract: A book of size b in a graph is an edge that lies in b triangles. Consider a graph G with n vertices and lfloor n^2/4 floor +1 edges. Rademacher proved that G contains at least lfloor n/2 floor triangles, and Erdos conjectured and Edwards proved that G contains a book of size at least n/6. We prove the following "linear combination" of these two results. Suppose that alphain (1/2, 1) and the maximum size of a book in G is less than alpha n/2. Then G contains at least alpha(1-alpha) n^2/4 - o(n^2) triangles as n approaches infinity. This is asymptotically sharp. On the other hand, for every alphain (1/3, 1/2), there exists �eta>0 such that G contains at least �eta n^3 triangles. It remains an open problem to determine the largest possible �eta in terms of alpha. Our proof uses the Ruzsa-Szemeredi theorem.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Books versus triangles

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