On the second eigenvalue and linear expansion of regular graphs

摘要

The authors investigate the relation between the second eigen-value and the linear expansion of regular graphs. The spectral method is the best currently known technique to prove lower bounds on the expansion. He improves this technique by showing that the expansion coefficient of linear-sized subsets of a k-regular graph G is at least k/2(1- square root max(0,1-/sub lambda 1(G)2//sup 4k-4/))/sup -/ , where lambda /sub 1/(G) is the second largest eigenvalue of the graph. In particular, the linear expansion of Ramanujan graphs, which have the property that the second largest eigenvalue is at most 2 square root k-1, is at least (k/2)/sup -/. This improves upon the best previously known lower bound of 3(k-2)/8. For any integer k such that k-1 is prime, he explicitly constructs an infinite family of k-regular graphs G/sub n/ on n vertices whose linear expansion is k/2 and such that lambda /sub 1/(G/sub n/)>or= square root k-1+0(1). Since the graphs G/sub n/ have asymptotically optimal second eigenvalue, this essentially shows the (k/2) is the best bound one can obtain using the second eigenvalue method.