Abstract
Let $G$ be an infinite graph whose vertex set is the set of positive
integers, and let $G_n$ be the subgraph of $G$ induced by the vertices $\{1,2,
\dots , n \}$. An increasing path of length $k$ in $G$, denoted $I_k$, is a
sequence of $k+1$ vertices $1 \leq i_1 < i_2 < \dots < i_{k+1}$ such that $i_1,
i_2, \ldots, i_{k+1}$ is a path in $G$. For $k \geq 2$, let $p(k)$ be the
supremum of $\liminf_{ n \rightarrow \infty} \frac{ e(G_n) }{n^2}$ over all
$I_k$-free graphs $G$. In 1962, Czipszer, Erd\H{o}s, and Hajnal proved that
$p(k) = \frac{1}{4} (1 - \frac{1}{k})$ for $k \in \{2,3 \}$. Erd\H{o}s
conjectured that this holds for all $ k \geq 4$. This was disproved for certain
values of $k$ by Dudek and R\"{o}dl who showed that $p(16) > \frac{1}{4} (1 -
\frac{1}{16})$ and $p(k) > \frac{1}{4} + \frac{1}{200}$ for all $k \geq 162$.
Given that the conjecture of Erd\H{o}s is true for $k \in \{2,3 \}$ but false
for large $k$, it is natural to ask for the smallest value of $k$ for which
$p(k) > \frac{1}{4} ( 1 - \frac{1}{k} )$. In particular, the question of
whether or not $p(4) = \frac{1}{4} ( 1 - \frac{1}{4} )$ was mentioned by Dudek
and R\"{o}dl as an open problem. We solve this problem by proving that $p(4)
\geq \frac{1}{4} (1 - \frac{1}{4} ) + \frac{1}{584064}$ and $p(k) > \frac{1}{4}
(1 - \frac{1}{k})$ for $4 \leq k \leq 15$. We also show that $p(4) \leq
\frac{1}{4}$ which improves upon the previously best known upper bound on
$p(4)$. Therefore, $p(4)$ must lie somewhere between $\frac{3}{16} +
\frac{1}{584064}$ and $\frac{1}{4}$