{
  "id": "1902.00259",
  "version": "v1",
  "published": "2019-02-01T10:12:11.000Z",
  "updated": "2019-02-01T10:12:11.000Z",
  "title": "Ramsey numbers of ordered graphs under graph operations",
  "authors": [
    "Jesse Geneson",
    "Amber Holmes",
    "Xujun Liu",
    "Dana Neidinger",
    "Yanitsa Pehova",
    "Isaac Wass"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "An ordered graph $\\mathcal{G}$ is a simple graph together with a total ordering on its vertices. The (2-color) Ramsey number of $\\mathcal{G}$ is the smallest integer $N$ such that every 2-coloring of the edges of the complete ordered graph on $N$ vertices has a monochromatic copy of $\\mathcal{G}$ that respects the ordering. In this paper we investigate the effect of various graph operations on the Ramsey number of a given ordered graph, and detail a general framework for applying results on extremal functions of 0-1 matrices to ordered Ramsey problems. We apply this method to give upper bounds on the Ramsey number of ordered matchings arising from sum-decomposable permutations, an alternating ordering of the cycle, and an alternating ordering of the tight hyperpath. We also construct ordered matchings on $n$ vertices whose Ramsey number is $n^{q+o(1)}$ for any given exponent $q\\in(1,2)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-02-01T10:12:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D10"
    ],
    "keywords": [
      "ramsey number",
      "graph operations",
      "smallest integer",
      "complete ordered graph",
      "construct ordered matchings"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}