{
  "id": "1704.00220",
  "version": "v1",
  "published": "2017-04-01T19:42:43.000Z",
  "updated": "2017-04-01T19:42:43.000Z",
  "title": "The universal triangle-free graph has finite big Ramsey degrees",
  "authors": [
    "Natasha Dobrinen"
  ],
  "comment": "51 pages. Penultimate draft. There will be a final draft in the next month or two with some graphics included",
  "categories": [
    "math.LO",
    "math.CO"
  ],
  "abstract": "The universal homogeneous triangle-free graph $\\mathcal{H}_3$ has finite `big Ramsey degrees': For each finite triangle-free graph $G$, there is a finite number $n(G)$ such that for any coloring $c$ of all copies of $G$ in $\\mathcal{H}_3$ into finitely many colors, there is a subgraph $\\mathcal{H}'$ of $\\mathcal{H}_3$ which is isomorphic to $\\mathcal{H}_3$ in which $c$ takes on no more than $n(G)$ many colors. The proof hinges on the following developments: a new flexible method for constructing trees which code the universal triangle-free graph, called strong coding trees; a new notion of isomorphism type of finite subtrees of a strong coding tree; analogues of the Halpern-L\\\"{a}uchli and Milliken Theorems, obtaining a Ramsey theorem for strict similarity types of finite subtrees of a given strong coding tree; and new notions of subtree envelope. The proof of the analogue of the Halpern-L\\\"{a}uchli theorem for strong coding trees uses forcing techniques, though the proof is in ZFC, building on ideas from Harrington's proof of the Halpern-L\\\"{a}uchli Theorem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-04-01T19:42:43.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "03C15",
      "03E02",
      "03E05",
      "03E75",
      "05C05",
      "03E45"
    ],
    "keywords": [
      "finite big ramsey degrees",
      "universal triangle-free graph",
      "strong coding tree",
      "finite subtrees",
      "strict similarity types"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 51,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}