{
  "id": "1708.01607",
  "version": "v1",
  "published": "2017-08-04T17:58:30.000Z",
  "updated": "2017-08-04T17:58:30.000Z",
  "title": "Partite Saturation of Complete Graphs",
  "authors": [
    "António Girão",
    "Teeradej Kittipassorn",
    "Kamil Popielarz"
  ],
  "comment": "18 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study the problem of determining the minimum number of edges $sat(n,k,r)$ in a $k$-partite graph with $k$ parts, each of size $n$, such that it is $K_r$-free but the addition of an edge joining any two non-adjacent vertices from different parts creates a $K_r$. Improving on recent results of Ferrara, Jacobson, Pfender and Wenger, and generalizing a recent result of Roberts, we prove that $sat(n,k,r) = \\alpha(k,r)n + o(n)$ where an explicit description of $\\alpha(k,r)$ is given. Moreover, we give the bounds \\[ k(2r-4) \\le \\alpha(k,r) \\le \\begin{cases} (k-1)(4r-k-6) &\\text{ for }r \\le k \\le 2r-3, \\\\(k-1)(2r-3) &\\text{ for }k \\ge 2r-3. \\end{cases} \\] and show that the lower bound is tight for infinitely many values of $r$ and every $k\\geq 2r-1$. This allows us to determine $sat(n,k,r) = k(2r-4)n + C_{k,r}$ up to an additive constant for those values of $k$ and $r$. Along the way, we disprove a conjecture and answer a question of the first set of authors mentioned above.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-04T17:58:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "complete graphs",
      "partite saturation",
      "first set",
      "minimum number",
      "parts creates"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}