Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Van Vu

UCSD

Generalizing Turan

Abstract:

Turan's theorem is probably one of the most well-known theorem in graph theory. Let k be a small integer, say 5, and n be a large integer. Turan showed that one must delete at least a $1/(k-1)$-fraction of the edges of the complete graph $K_n$ in order to destroy all cliques of size k. For instance, one must delete at least half of the edges to destroy all triangles. It is natural to study the problem for graphs other than $K_n$. A graph G on n vertices is called k-Turan if one needs to delete at least a $1/(k-1)$- fraction of the edges of G in order to destroy all k-cliques in G. Which graphs are k-Turan ? For instance, is the Paley graph 5-Turan ? Despite the long and rich history of Turan's theory, which spans several decades, not much has been known about this question. Recently, Sudakov, Szabo, and Vu, based on earlier results of the last two researchers, found a general sufficient condition for a regular graph to be k-Turan. We discovered a surprising connection between the k-Turan property and the spectral of the graph: if the second eigenvalue of G is sufficiently small compared to the degree, then G is k-Turan. In particular, good expanders have the Turan properties. The proof is completely elementary.

Host:

December 3, 2002

3:00 PM

AP&M 7429

****************************