Books vs Triangles - Mathematics > CombinatoricsReport as inadecuate

Books vs Triangles - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: A book of size b in a graph is an edge that lies in b triangles. Consider agraph G with n vertices and \lfloor n^2-4 floor +1 edges. Rademacher provedthat G contains at least \lfloor n-2 floor triangles, and Erdos conjecturedand Edwards proved that G contains a book of size at least n-6.We prove the following -linear combination- of these two results. Supposethat \alpha\in 1-2, 1 and the maximum size of a book in G is less than \alphan-2. Then G contains at least \alpha1-\alpha n^2-4 - on^2 triangles as napproaches 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 \betan^3 triangles. It remains an open problem to determine the largest possible\beta in terms of \alpha. Our proof uses the Ruzsa-Szemeredi theorem.

Author: Dhruv Mubayi


Related documents