\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Andrzej Dudek and Vojt\v{e}ch R\"odl}
%
%
\medskip
\noindent
%
%
{\bf On the Tur\'an Properties of Infinite Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G^{(\infty)}$ be an infinite graph with the vertex set
corresponding to the set of positive integers ${\Bbb 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\'an's
theorem to infinite graphs, in this paper we will examine how large
$\liminf_{l\rightarrow \infty} {|E(G^{(l)})|\over 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
${1\over 4}+{1\over 200} < \liminf_{l\rightarrow \infty}
{|E(G^{(l)})|\over l^2}$. This disproves a conjecture of J.~Czipszer,
P.~Erd\H{o}s and A.~Hajnal.  On the other hand, we will show that
$\liminf_{l\rightarrow \infty} {|E(G^{(l)})|\over l^2}\le{1\over 3}$
for any $k$ and such $G^{(\infty)}$.

\bye