Books vs Triangles - Mathematics > CombinatoricsReportar como inadecuado

Books vs Triangles - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Dhruv Mubayi


Documentos relacionados