Rational exponents in extremal graph theory

Abstract

Given a family of graphs $\mathcal{H}$, the extremal number ex$(n,\mathcal{H})$ is the largest $m$ for which there exists a graph with $n$ vertices and $m$ edges containing no graph from the family $\mathcal{H}$ as a subgraph. We show that for every rational number $r$ between 1 and 2, there is a family of graphs ${\mathcal{H}}_r$ such that ex$(n,{\mathcal{H}}_r)=\Theta (n^r)$. This solves a longstanding problem in the area of extremal graph theory.