A path Turan problem for infinite graphs

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\le i_1<i_2<\cdots <i_{k+1}$ such that $i_1,i_2,\dots ,i_{k+1}$ is a path in $G$. For $k\ge 2$, let $p(k)$ be the supremum of ${\mathrm{liminf}}_{n\to \infty }\frac{e(G_n)}{n^2}$ over all $I_k$-free graphs $G$. In 1962, Czipszer, Erdős, and Hajnal proved that $p(k)=\frac{1}{4}(1-\frac{1}{k})$ for $k\in \{2,3\}$. Erdős conjectured that this holds for all $k\ge 4$. This was disproved for certain values of $k$ by Dudek and Rö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\ge 162$. Given that the conjecture of Erdő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ödl as an open problem. We solve this problem by proving that $p(4)\ge \frac{1}{4}(1-\frac{1}{4})+\frac{1}{584064}$ and $p(k)>\frac{1}{4}(1-\frac{1}{k})$ for $4\le k\le 15$. We also show that $p(4)\le \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}$

16 pages; Comments are welcome