ABSTRACT
Be´la Bolloba´s, University of Memphis, and Trinity College, Cambridge
Vladimir Nikiforov, University of Memphis
8.1.1 Tura´n-Type Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954 8.1.2 The Number of Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958 8.1.3 Erdo˝s-Stone Theorem and Its Extensions . . . . . . . . . . . . . . . . . . . . . . . 959 8.1.4 Zarankiewicz Problem and Related Questions . . . . . . . . . . . . . . . . . . . 961 8.1.5 Paths and Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963 8.1.6 Circumference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964 8.1.7 Hamiltonian Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964 8.1.8 Cycle Lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 965 8.1.9 Szemere´di’s Uniformity Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 967 8.1.10 Asymptotic Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968 8.1.11 Graph Minors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 970 8.1.12 Ramsey-Tura´n Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 971 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972
INTRODUCTION
Extremal graph theory is concerned with inequalities among functions of graph invariants and the structures that demonstrate that these inequalities are best possible. Accordingly, in its wide sense, it encompasses most of graph theory. Nevertheless, there is a clearly identifiable body of core extremal results: in this all-too-brief review we shall present a selection of narrowly interpreted extremal results.