Rational exponents in extremal graph theory
Given a family of graphs ℌ, the extremal number ex(n, ℌ) is the largest m for which there exists a graph with n vertices and m edges containing no graph from the family ℌ as a subgraph. We show that for every rational number r between 1 and 2, there is a family of graphs ℌ_r such that ex (n, ℌ_r) = Θ(n^r). This solves a longstanding problem in the area of extremal graph theory.
Additional Information© 2018 European Mathematical Society. Published online: 2018-05-22. Bukh research supported in part by a Sloan Research Fellowship, NSF grant DMS-1301548, and NSF CAREER grant DMS-1555149. Conlon research supported by a Royal Society University Research Fellowship and ERC Starting Grant 676632. We would like to thank Jacques Verstraete for interesting discussions relating to the topic of this paper. We would also like to thank an anonymous referee and Lisa Sauermann for a number of useful comments and corrections.
Submitted - 1506.06406.pdf