Extremal Number

The extremal number of a graph is the largest number of edges in an -vertex simple graph containing no subgraph isomorphic to . The forbidden subgraph need not be induced. For example, Mantel's theorem gives , where is the cycle graph of length three and is the floor function.

The example with has quadratic growth. More generally, the rational exponents conjecture concerns which power-law growth rates can occur as the forbidden graph varies. Conlon et al. (2026) proved that every rational number occurs in for a single forbidden graph , where is big-Theta notation.