Mathematics – Combinatorics
Scientific paper
2010-02-07
Mathematics
Combinatorics
Scientific paper
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\rfloor +1 edges. Rademacher proved that G contains at least \lfloor n/2\rfloor 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 \alpha\in (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 \alpha\in (1/3, 1/2), there exists \beta>0 such that G contains at least \beta n^3 triangles. It remains an open problem to determine the largest possible \beta in terms of \alpha. Our proof uses the Ruzsa-Szemeredi theorem.
No associations
LandOfFree
Books vs Triangles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Books vs Triangles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Books vs Triangles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-307391