A path Turán problem for infinite graphs

Let GG be an infinite graph whose vertex set is the set of positive integers, and let GnGn be the subgraph of GG induced by the vertices {1,2,…,n}{1,2,…,n}. An increasing path of length kk in GG, denoted IkIk, is a sequence of k+1k+1 vertices 1≤i114(1−116) and p(k)>14+1200 for all k≥162k≥162. Given that the conjecture of Erdős is true for k∈{2,3}k∈{2,3} but false for large kk, it is natural to ask for the smallest value of kk 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≤154≤k≤15. We also show that p(4)≤14 which improves upon the previously best known upper bound on p(4)p(4). Therefore, p(4)p(4) must lie somewhere between 316+1584064 and 14.