tailieunhanh - Báo cáo toán học: "Spectral saturation: inverting the spectral Tur´n theorem a"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Spectral saturation: inverting the spectral Tur´n theorem a. | Spectral saturation inverting the spectral Turan theorem Vladimir Nikiforov Department of Mathematical Sciences University of Memphis Memphis TN USA vnikifrv@ Submitted Nov 28 2007 Accepted Feb 26 2009 Published Mar 13 2009 Mathematics Subject Classifications 05C50 05C35 Abstract Let g G be the largest eigenvalue of a graph G and Tr n be the r-partite Turan graph of order n. We prove that if G is a graph of order n with g G g Tr n then G contains various large supergraphs of the complete graph of order r 1 . the complete r-partite graph with all parts of size log n with an edge added to the first part. We also give corresponding stability results. Keywords complete r-partite graph stability spectral Turan s theorem largest eigenvalue of a graph. 1 Introduction This note is part of an ongoing project aiming to build extremal graph theory on spectral basis see . 3 13 18 . Let ụ G be the largest adjacency eigenvalue of a graph G and Tr n be the r-partite Turan graph of order n. The spectral Turan theorem 15 implies that if G is a graph of order n with ụ G ụ Tr n then G contains a Kr 1 the complete graph of order r 1. On the other hand it is known . 2 4 9 12 that if e G e Tr n then G contains large supergraphs of Kr 1. It turns out that essentially the same results also follow from the inequality ụ G ụ Tr n . Recall first a family of graphs studied initially by Erdos 7 and recently in 2 an r-joint of size t is the union of t distinct r-cliques sharing an edge. Write jsr G for the maximum size of an r-joint in a graph G. Erdos 7 Theorem 3 showed that if G is a graph of sufficiently large order n satisfying e G e Tr n then jsr 1 G nr-1 10 r 1 6 r 1 . THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R33 1 Here is a explicit spectral analogue of this result. Theorem 1 Let r 2 n r15 and G be a graph of order n. If p G p Tr n then jsr 1 G nr-1 r2r 4. Erdos 4 introduced yet another graph related to Turan s theorem let K s1 . sr be the complete r-partite .