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.