{
  "id": "2402.16776",
  "version": "v4",
  "published": "2024-02-26T17:45:58.000Z",
  "updated": "2024-08-21T14:40:52.000Z",
  "title": "On the length of directed paths in digraphs",
  "authors": [
    "Yangyang Cheng",
    "Peter Keevash"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Thomass\\'{e} conjectured the following strengthening of the well-known Caccetta-Haggkvist Conjecture: any digraph with minimum out-degree $\\delta$ and girth $g$ contains a directed path of length $\\delta(g-1)$. Bai and Manoussakis \\cite{Bai} gave counterexamples to Thomass\\'{e}'s conjecture for every even $g\\geq 4$. In this note, we first generalize their counterexamples to show that Thomass\\'{e}'s conjecture is false for every $g\\geq 4$. We also obtain the positive result that any digraph with minimum out-degree $\\delta$ and girth $g$ contains a directed path of $2(1-\\frac{2}{g})$. For small $g$ we obtain better bounds, e.g.~for $g=3$ we show that oriented graph with minimum out-degree $\\delta$ contains a directed path of length $1.5\\delta$. Furthermore, we show that each $d$-regular digraph with girth $g$ contains a directed path of length $\\Omega(dg/\\log d)$. Our results give the first non-trivial bounds for these problems.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2024-08-21T14:40:52.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "directed path",
      "minimum out-degree",
      "well-known caccetta-haggkvist conjecture",
      "first non-trivial bounds",
      "regular digraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}