Rational exponents in extremal graph theory

摘要

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