{
  "id": "1111.0587",
  "version": "v1",
  "published": "2011-11-02T18:03:12.000Z",
  "updated": "2011-11-02T18:03:12.000Z",
  "title": "Structures and lower bounds for binary covering arrays",
  "authors": [
    "Soohak Choi",
    "Hyun Kwang Kim",
    "Dong Yeol Oh"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A $q$-ary $t$-covering array is an $m \\times n$ matrix with entries from $\\{0, 1, ..., q-1\\}$ with the property that for any $t$ column positions, all $q^t$ possible vectors of length $t$ occur at least once. One wishes to minimize $m$ for given $t$ and $n$, or maximize $n$ for given $t$ and $m$. For $t = 2$ and $q = 2$, it is completely solved by R\\'enyi, Katona, and Kleitman and Spencer. They also show that maximal binary 2-covering arrays are uniquely determined. Roux found the lower bound of $m$ for a general $t, n$, and $q$. In this article, we show that $m \\times n$ binary 2-covering arrays under some constraints on $m$ and $n$ come from the maximal covering arrays. We also improve the lower bound of Roux for $t = 3$ and $q = 2$, and show that some binary 3 or 4-covering arrays are uniquely determined.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-11-02T18:03:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lower bound",
      "binary covering arrays",
      "structures",
      "maximal binary",
      "column positions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1111.0587C"
    }
  }
}