{
  "id": "2012.09201",
  "version": "v1",
  "published": "2020-12-16T19:01:11.000Z",
  "updated": "2020-12-16T19:01:11.000Z",
  "title": "Trees and tree-like structures in dense digraphs",
  "authors": [
    "Richard Mycroft",
    "Tássio Naia"
  ],
  "comment": "33 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove that every oriented tree on $n$ vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on $n$ vertices with minimum semidegree at least $n/2+\\mathrm{o}(n)$. This can be seen as a directed graph analogue of a well-known theorem of Koml\\'os, S\\'ark\\\"ozy and Szemer\\'edi. Our result for trees follows from a more general result, allowing the embedding of arbitrary orientations of a much wider class of spanning \"tree-like\" structures, such as a collection of at most $\\mathrm{o}(n^{1/4})$ vertex-disjoint cycles and subdivisions of graphs $H$ with $|H|< n^{(\\log n)^{-1/2}}$ in which each edge is subdivided at least once.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-16T19:01:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20"
    ],
    "keywords": [
      "dense digraphs",
      "tree-like structures",
      "bounded maximum degree appears",
      "minimum semidegree",
      "directed graph analogue"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}