2010/02/07 by Dhruv Mubayi, Mubayi, Dhruv
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1002.1492
arxiv created 2010/02/07 · openalex publication_date 2010/02/07 · arxiv updated 2010/02/26 · openalex created_date 2022/09/02 · openalex updated_date 2026/07/28
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 n2/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 α∈ (1/2, 1) and the maximum size of a book in G is less than αn/2. Then G contains at least α(1-α) n2/4 - o(n2) triangles as n approaches infinity. This is asymptotically sharp. On the other hand, for every α∈ (1/3, 1/2), there exists β>0 such that G contains at least βn3 triangles. It remains an open problem to determine the largest possible βin terms of α. Our proof uses the Ruzsa-Szemeredi theorem.