Carnegie Mellon University
file.pdf (177.15 kB)

Rational exponents in extremal graph theory

Download (177.15 kB)
journal contribution
posted on 2015-06-21, 00:00 authored by Boris Bukh, David Conlon

Given a family of graphs H, 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 of graphs Hr such that ex(n,Hr)=Θ(nr). This solves a longstanding problem in the area of extremal graph theory.




Usage metrics