{
  "id": "1708.08817",
  "version": "v1",
  "published": "2017-08-29T15:14:51.000Z",
  "updated": "2017-08-29T15:14:51.000Z",
  "title": "On Existentially Complete Triangle-free Graphs",
  "authors": [
    "Shoham Letzter",
    "Julian Sahasrabudhe"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For a positive integer $k$, we say that a graph is $k$-existentially complete if for every $0 \\leq a \\leq k$, and every tuple of distinct vertices $x_1,\\ldots,x_a$, $y_1,\\ldots,y_{k-a}$, there exists a vertex $z$ that is joined to all of the vertices $x_1,\\ldots,x_a$ and none of the vertices $y_1,\\ldots,y_{k-a}$. While it is easy to show that the binomial random graph $G_{n,1/2}$ satisfies this property with high probability for $k \\sim c\\log n$, little is known about the \"triangle-free\" version of this problem; does there exist a finite triangle-free graph $G$ with a similar \"extension property\". This question was first raised by Cherlin in 1993 and remains open even in the case $k=4$. We show that there are no $k$-existentially complete triangle-free graphs with $k >\\frac{8\\log n}{\\log\\log n}$, thus giving the first non-trivial, non-existence result on this \"old chestnut\" of Cherlin. We believe that this result breaks through a natural barrier in our understanding of the problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-29T15:14:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05D40"
    ],
    "keywords": [
      "existentially complete triangle-free graphs",
      "binomial random graph",
      "finite triangle-free graph",
      "high probability",
      "natural barrier"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}