Journal of the European Mathematical Society


Full-Text PDF (149 KB) | Metadata | Table of Contents | JEMS summary
Volume 20, Issue 7, 2018, pp. 1747–1757
DOI: 10.4171/JEMS/798

Published online: 2018-05-22

Rational exponents in extremal graph theory

Boris Bukh[1] and David Conlon[2]

(1) Carnegie Mellon University, Pittsburgh, USA
(2) University of Oxford, UK

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.

Keywords: Extremal graph theory, bipartite graphs, algebraic constructions

Bukh Boris, Conlon David: Rational exponents in extremal graph theory. J. Eur. Math. Soc. 20 (2018), 1747-1757. doi: 10.4171/JEMS/798