{
  "id": "2007.03986",
  "version": "v1",
  "published": "2020-07-08T09:47:01.000Z",
  "updated": "2020-07-08T09:47:01.000Z",
  "title": "A characterization of 2-threshold functions via pairs of prime segments",
  "authors": [
    "Elena Zamaraeva",
    "Jovisa Zunic"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In this paper we study 2-threshold functions over a two-dimensional rectangular grid also known as intersections of two halfplanes. We provide a characterization for 2-threshold functions by pairs of oriented prime segments with certain properties, which we call proper. To this end, we first show that any proper $2$-threshold function $f$ can be defined by a proper pair of segments. Then we prove that such a representation is unique if $f$ has a true point on the boundary of the grid. Finally, we establish a bijection between almost all proper pairs of segments and almost all $2$-threshold functions. Due to this bijection almost all $2$-threshold functions admit encoding by ordered sets of 4 integer points.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-08T09:47:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "03B50",
      "05A18",
      "52C05",
      "11P21",
      "G.2.1"
    ],
    "keywords": [
      "characterization",
      "proper pair",
      "two-dimensional rectangular grid",
      "integer points",
      "oriented prime segments"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}