Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-08T18:25:59.568Z 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: vnikifrv@memphis.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let r ≥ 3 and (c/rr)r log n ≥ 1. If G is a graph of order n and its largest eigenvalue μ(G) satisfies$\[ \mu ( G ) geq ( 1-1/ ( r-1 ) +c ) n, \]$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$\[ \lim_{n\rightarrow\infty}\frac{1}{n}\max\bigl\{ \mu ( G ): v ( G ) =n~~\text{and}~~F_{n}\nsubseteq G\bigr\} =1-\frac{1}{r-1}$

Information

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

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