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
Online access to the full text of Journal of the European Mathematical Society is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
subscriptions@ems-ph.org
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