{
  "id": "1811.10567",
  "version": "v1",
  "published": "2018-11-06T11:09:59.000Z",
  "updated": "2018-11-06T11:09:59.000Z",
  "title": "Chromatic numbers of graphs of intersections",
  "authors": [
    "D. Zakharov"
  ],
  "comment": "13 pages, in Russian",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G(n, r, s)$ be a graph whose vertices are all $r$-element subsets of an $n$-element set, in which two vertices are adjacent if they intersect in exactly $s$ elements. In this paper we study chromatic numbers of $G(n, r, s)$. Using recent result of Keevash on existence of designs we deduce an inequality $\\chi(G(n, r, s)) \\le (1+o(1))n^{r-s} \\frac{(r-s-1)!}{(2r-2s-1)!}$ for fixed $r, s$. Also we depelop a new elementary approach and prove that $\\chi(G(n, 4, 2)) \\sim \\frac{n^2}{6}$ without use of Keevash's results.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-11-06T11:09:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "intersections",
      "study chromatic numbers",
      "element subsets",
      "elementary approach",
      "element set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "ru",
      "license": "arXiv",
      "status": "editable"
    }
  }
}