{
  "id": "2004.06097",
  "version": "v1",
  "published": "2020-04-13T17:56:41.000Z",
  "updated": "2020-04-13T17:56:41.000Z",
  "title": "Saturation problems in the Ramsey theory of graphs, posets and point sets",
  "authors": [
    "Gábor Damásdi",
    "Balázs Keszegh",
    "David Malec",
    "Casey Tompkins",
    "Zhiyu Wang",
    "Oscar Zamora"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1964, Erd\\H{o}s, Hajnal and Moon introduced a saturation version of Tur\\'an's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erd\\H{o}s-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets. We also consider semisaturation problems, wherein we allow the family to have the forbidden configuration, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting, we prove a semisaturation version of the Erd\\H{o}s-Szekeres theorem on convex $k$-gons, as well as multiple semisaturation theorems for sequences and posets.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-13T17:56:41.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "ramsey theory",
      "saturation problems",
      "point sets",
      "saturation version",
      "forbidden configuration"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}