{
  "id": "1512.06371",
  "version": "v1",
  "published": "2015-12-20T13:25:46.000Z",
  "updated": "2015-12-20T13:25:46.000Z",
  "title": "A path Turan problem for infinite graphs",
  "authors": [
    "Xing Peng",
    "Craig Timmons"
  ],
  "comment": "16 pages; Comments are welcome",
  "categories": [
    "math.CO"
  ],
  "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}$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-20T13:25:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "path turan problem",
      "infinite graph",
      "free graphs",
      "upper bound",
      "smallest value"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151206371P"
    }
  }
}