On the Turán Properties of Infinite Graphs - Dudek, Andrzej; Rödl, Vojtěch (The Electronic Journal of Combinatorics, 2008)
Let G^(∞) be an infinite graph with the vertex set corresponding to the set of positive integers N. Denote by G^(l) a subgraph of G^(∞) which is spanned by the vertices {1,…,l}. As a possible extension of Turán’s theorem to infinite graphs, in this paper we will examine how large _l→ ∞ |E(G^(l))|l^2 can be for an infinite graph G^(∞), which does not contain an increasing path I_k with k+1 vertices. We will show that for sufficiently large k there are I_k–free infinite graphs with 14+1200 < _l→ ∞ |E(G^(l))|l^2. This disproves a conjecture of J. Czipszer, P. Erdős and A. Hajnal. On the other hand, we will show that _l→ ∞ |E(G^(l))|l^213 for any k and such G^(∞).