Infinite Turán problems for bipartite graphs

Abstract

We consider an infinite version of the bipartite Turán problem. Let $G$ be an infinite graph with $V(G)=\mathbb{N}$ and let $G_n$ be the $n$-vertex subgraph of $G$ induced by the vertices $\{1,2,\dots ,n\}$. We show that if $G$ is $K_{2,t+1}$-free then for infinitely many $n$, $e(G_n)\le 0.471\sqrt{t}{n}^{3/2}$. Using the $K_{2,t+1}$-free graphs constructed by Füredi, we construct an infinite $K_{2,t+1}$-free graph with $e(G_n)\ge 0.23\sqrt{t}{n}^{3/2}$ for all $n\ge n_0$.

arXiv comment10 pages