Chapter 4 Near or Beyond the Extremal Number
In this chapter, we focus on more detailed and subtle questions than computing or estimating extremal numbers. In particular, we will consider the following types of questions:
- Suppose that \(G\) is a graph on \(n\) vertices such that \(|E(G)|>\ex(n,H)\text{;}\) i.e. that \(G\) is supersaturated. How many copies of \(H\) must \(G\) contain?
- Suppose that \(G\) is an \(H\)-free graph with \(n\) vertices such that \(|E(G)|\) is “almost as large as” \(\ex(n,H)\text{.}\) Does it follow that the “structure” of \(G\) is “close” to that of an extremal example? That is, are the extremal graphs stable?
With regards to Question 1, we will begin by proving tight results for some specific graphs \(H\text{,}\) including \(K_3\) and even cycles. After this, we will prove a “qualitative” result for general graphs which says that if the number of edges in \(G\) is larger than the extremal number by \(\varepsilon n^2\text{,}\) then, as \(n\) grows, the number of copies of \(H\) in \(G\) grows at a rate of \(\Omega\left(n^{|V(H)|}\right)\text{.}\) We will explore Question 2 only in the case that \(H\) is a complete graph.
