Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-29T01:20:14.475Z Has data issue: false hasContentIssue false
  • English
  • Français

A Spectral Erdős–Stone–Bollobás Theorem

Published online by Cambridge University Press:  01 May 2009

VLADIMIR NIKIFOROV
VLADIMIR NIKIFOROV*
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Let r ≥ 3 and (c/rr)r log n ≥ 1. If G is a graph of order n and its largest eigenvalue μ(G) satisfies then G contains a complete r-partite subgraph with r − 1 parts of size ⌊(c/rr)r log n⌋ and one part of size greater than n1−cr−1.

This result implies the Erdős–Stone–Bollobás theorem, the essential quantitative form of the Erdős–Stone theorem. Another easy consequence is that if F1, F2, . . . are r-chromatic graphs satisfying v(Fn) = o(log n), then

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 3 , May 2009 , pp. 455 - 458
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Babai, L. and Guiduli, B. (2007) Spectral extrema for graphs: The Erdős–Stone–Simonovits theorem. Manuscript.Google Scholar
[2]Bollobás, B. (1998) Modern Graph Theory, Vol. 184 of Graduate Texts in Mathematics}, Springer.CrossRefGoogle Scholar
[3]Bollobás, B. and Erdős, P. (1973) On the structure of edge graphs. Bull. London Math. Soc. 5 317–321.CrossRefGoogle Scholar
[4]Bollobás, B. and Nikiforov, V. (2007) Cliques and the spectral radius. J. Combin. Theory Ser. B 97 859–865.CrossRefGoogle Scholar
[5]Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.CrossRefGoogle Scholar
[6]Guiduli, B. (1996) Spectral extrema for graphs. PhD thesis, University of Chicago.Google Scholar
[7]Nikiforov, V. (2008) Graphs with many r-cliques have large complete r-partite subgraphs. Bull. London Math. Soc. 40 23–25.CrossRefGoogle Scholar