4.2 Article

A Spectral Erdos-Stone-Bollobas Theorem

Journal

COMBINATORICS PROBABILITY & COMPUTING
Volume 18, Issue 3, Pages 455-458

Publisher

CAMBRIDGE UNIV PRESS
DOI: 10.1017/S0963548309009687

Keywords

-

Ask authors/readers for more resources

Let r >= 3 and (c/r(r))(r) log n >= 1. If G is a graph of order n and its largest eigenvalue mu(G) satisfies mu(G) >= (1 - 1/(r - 1) + c)n, then G contains a complete r-partite subgraph with r - 1 parts of size [(c/r(r))(r) log n] and one part of size greater than n(1-cr-1). This result implies the Erdos-Stone-Bollobas theorem, the essential quantitative form of the Erdos-Stone theorem. Another easy consequence is that if F-1, F-2,F-... are r-chromatic graphs satisfying v(F-n) = o(log n), then lim(n ->infinity) 1/n max{mu(G) : v(G) = n and F-n not subset of G} = 1 - 1/r - 1.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.2
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available