Small dense subgraphs of a graph

Abstract

Given a family $\mathcal{F}$ of graphs, and a positive integer $n$, the Turán number $ex(n,\mathcal{F})$ of $\mathcal{F}$ is the maximum number of edges in an $n$-vertex graph that does not contain any member of $\mathcal{F}$ as a subgraph. The order of a graph is the number of vertices in it. In this paper, we study the Turán number of the family of graphs with bounded order and high average degree. For every real $d\ge 2$ and positive integer $m\ge 2$, let ${\mathcal{F}}_{d,m}$ denote the family of graphs on at most $m$ vertices that have average degree at least $d$. It follows from the Erdős-Rényi bound that $ex(n,{\mathcal{F}}_{d,m})=\Omega (n^{2-\frac{2}{d}+\frac{c}{dm}})$, for some positive constant $c$. Verstraëte asked if it is true that for each fixed $d$ there exists a function ${\epsilon }_d(m)$ that tends to $0$ as $m\to \infty$ such that $ex(n,{\mathcal{F}}_{d,m})=O(n^{2-\frac{2}{d}+{\epsilon }_d(m)})$. We answer Verstraëte's question in the affirmative whenever $d$ is an integer. We also prove an extension of the cube theorem on the Turán number of the cube $Q_3$, which partially answers a question of Pinchasi and Sharir.