tailieunhanh - Báo cáo toán học: "he spectral gap of random graphs with given expected degrees"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: he spectral gap of random graphs with given expected degrees. | The spectral gap of random graphs with given expected degrees Amin Coja-Oghlan University of Edinburgh School of Informatics Crichton Street Edinburgh EH8 9AB UK acoghlan@ Andre Lanka Technische Universitat Chemnitz Fakultat fur Informatik Strafie der Nationen 62 09107 Chemnitz Germany lanka@ Submitted Jun 26 2008 Accepted Oct 31 2009 Published Nov 13 2009 Mathematics Subject Classifications 05C80 15B52 Abstract We investigate the Laplacian eigenvalues of a random graph G n d with a given expected degree distribution d. The main result is that . G n d has a large subgraph core G n d such that the spectral gap of the normalized Laplacian of 7-1 2 core G n d is 1 codmin with high probability here Co 0 is a constant and dmin signifies the minimum expected degree. The result in particular applies to sparse graphs with dmin O 1 as n TO. The present paper complements the work of Chung Lu and Vu Internet Mathematics 1 2003 . 1 Introduction and Results Spectral Techniques for Graph Problems Numerous heuristics for graph partitioning problems are based on spectral methods the heuristic sets up a matrix that represents the input graph and reads information on the global structure of the graph out of the eigenvalues and eigenvectors of the matrix. Since there are rather efficient methods for computing eigenvalues and -vectors spectral techniques are very popular in various applications 22 23 . Though in many cases there are worst-case examples known showing that certain spectral heuristics perform badly on general instances . 16 spectral methods are in An extended abstract version of this paper appeared in the Proc. 33rd ICALP 2006 15-26. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R138 1 common use and seem to perform well on many practical inputs. Therefore in order to gain a better theoretical understanding of spectral methods quite a few papers deal with rigorous analyses of spectral heuristics on suitable classes of .