A path Turan problem for infinite graphs

Xing Peng, Craig Timmons

Published 2015-12-20Version 1

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}$