The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

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