{
  "id": "1107.2639",
  "version": "v1",
  "published": "2011-07-13T19:37:28.000Z",
  "updated": "2011-07-13T19:37:28.000Z",
  "title": "Hall's Condition for Partial Latin Squares",
  "authors": [
    "A. J. W. Hilton",
    "E. R. Vaughan"
  ],
  "comment": "23 pages; 9 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Hall's Condition is a necessary condition for a partial latin square to be completable. Hilton and Johnson showed that for a partial latin square whose filled cells form a rectangle, Hall's Condition is equivalent to Ryser's Condition, which is a necessary and sufficient condition for completability. We give what could be regarded as an extension of Ryser's Theorem, by showing that for a partial latin square whose filled cells form a rectangle, where there is at most one empty cell in each column of the rectangle, Hall's Condition is a necessary and sufficient condition for completability. It is well-known that the problem of deciding whether a partial latin square is completable is NP-complete. We show that the problem of deciding whether a partial latin square that is promised to satisfy Hall's Condition is completable is NP-hard.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-07-13T19:37:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B15"
    ],
    "keywords": [
      "partial latin square",
      "filled cells form",
      "sufficient condition",
      "satisfy halls condition",
      "rysers condition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1107.2639H"
    }
  }
}