{
  "id": "2109.04944",
  "version": "v1",
  "published": "2021-09-10T15:43:46.000Z",
  "updated": "2021-09-10T15:43:46.000Z",
  "title": "On $3$-graphs with no four vertices spanning exactly two edges",
  "authors": [
    "Lior Gishboliner",
    "István Tomon"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $D_2$ denote the $3$-uniform hypergraph with $4$ vertices and $2$ edges. Answering a question of Alon and Shapira, we prove an induced removal lemma for $D_2$ having polynomial bounds. We also prove an Erd\\H{o}s-Hajnal-type result: every induced $D_2$-free hypergraph on $n$ vertices contains a clique or an independent set of size $n^{c}$ for some absolute constant $c > 0$. In the case of both problems, $D_2$ is the only nontrivial $k$-uniform hypergraph with $k\\geq 3$ which admits a polynomial bound.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-09-10T15:43:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "vertices spanning",
      "polynomial bound",
      "uniform hypergraph",
      "absolute constant",
      "independent set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}