Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2018 | Submitted
Journal Article Open

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.

Attached Files

Submitted - 1506.06406.pdf


Files (183.4 kB)
Name Size Download all
183.4 kB Preview Download

Additional details

August 19, 2023
October 18, 2023