Abstract
Let G be an infinite graph whose vertex set is the set of positive integers, and let Gn be the subgraph of G induced by the vertices {1,2,…,n}. An increasing path of length k in G, denoted Ik, is a sequence of k+1 vertices 1≤i1<i2<⋯<ik+1 such that i1,i2,…,ik+1 is a path in G. For k≥2, let p(k) be the supremum of lim infn→∞e(Gn)n2 over all Ik-free graphs G. In 1962, Czipszer, Erdős, and Hajnal proved that p(k)=14(1−1k) for k∈{2,3}. Erdős conjectured that this holds for all k≥4. This was disproved for certain values of k by Dudek and Rödl who showed that p(16)>14(1−116) and p(k)>14+1200 for all k≥162. Given that the conjecture of Erdős is true for k∈{2,3} but false for large k, it is natural to ask for the smallest value of k for which p(k)>14(1−1k). In particular, the question of whether or not p(4)=14(1−14) was mentioned by Dudek and Rödl as an open problem. We solve this problem by proving that p(4)≥14(1−14)+1584064 and p(k)>14(1−1k) for 4≤k≤15. We also show that p(4)≤14 which improves upon the previously best known upper bound on p(4). Therefore, p(4) must lie somewhere between 316+1584064 and 14.