{
  "id": "2106.05347",
  "version": "v1",
  "published": "2021-06-09T19:26:44.000Z",
  "updated": "2021-06-09T19:26:44.000Z",
  "title": "A note on explicit constructions of designs",
  "authors": [
    "Xizhi Liu",
    "Dhruv Mubayi"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "An $(n,r,s)$-system is an $r$-uniform hypergraph on $n$ vertices such that every pair of edges has an intersection of size less than $s$. Using probabilistic arguments, R\\\"{o}dl and \\v{S}i\\v{n}ajov\\'{a} showed that for all fixed integers $r> s \\ge 2$, there exists an $(n,r,s)$-system with independence number $O\\left(n^{1-\\delta+o(1)}\\right)$ for some optimal constant $\\delta >0$ only related to $r$ and $s$. We show that for certain pairs $(r,s)$ with $s\\le r/2$ there exists an explicit construction of an $(n,r,s)$-system with independence number $O\\left(n^{1-\\epsilon}\\right)$, where $\\epsilon > 0$ is an absolute constant only related to $r$ and $s$. Previously this was known only for $s>r/2$ by results of Chattopadhyay and Goodman",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-09T19:26:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "explicit construction",
      "independence number",
      "uniform hypergraph",
      "optimal constant",
      "probabilistic arguments"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}