On the Turán properties of infinite graphs (Q1010760)

Summary: Let \(G^{(\infty)}\) be an infinite graph with the vertex set corresponding to the set of positive integers \({\mathbb N}\). Denote by \(G^{(l)}\) a subgraph of \(G^{(\infty)}\) which is spanned by the vertices \(\{1,\dots,l\}\). As a possible extension of Turán's theorem to infinite graphs, in this paper we will examine how large \(\lim \text{inf}_{l\rightarrow \infty} \frac{|E(G^{(l)})|}{l^2}\) can be for an infinite graph \(G^{(\infty)}\), 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 \(\frac{1}{4}+\frac{1}{200} < \lim \text{inf}_{l\rightarrow \infty}\frac{|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 \(\liminf_{l\rightarrow \infty}\frac{|E(G^{(l)}|}{l^2} \leq \text{1}{3}\) for any \(k\) and such \(G^{(\infty)}\).