{
  "id": "2004.03400",
  "version": "v1",
  "published": "2020-04-05T21:33:33.000Z",
  "updated": "2020-04-05T21:33:33.000Z",
  "title": "Singularity of $\\{\\pm 1\\}$-matrices and asymptotics of the number of threshold functions",
  "authors": [
    "Anwar A. Irmatov"
  ],
  "comment": "32 pages. This is the full version of the short communication \"Asymptotics of the number of threshold functions and the singularity probability of random $\\{\\pm 1\\}$-matrices\" to appear in the journal \"Doklady Mathematics\", 2020, V.492 (Russian). arXiv admin note: text overlap with arXiv:1811.10087",
  "categories": [
    "math.CO",
    "math.AT",
    "math.PR"
  ],
  "abstract": "Two results concerning the number of threshold functions $P(2, n)$ and the probability ${\\mathbb P}_n$ that a random $n\\times n$ Bernoulli matrix is singular are established. We introduce a supermodular function $\\eta^{\\bigstar}_n : 2^{{\\bf RP}^n}_{fin} \\to \\mathbb{Z}_{\\geq 0},$ defined on finite subsets of ${\\bf RP}^n,$ that allows us to obtain a lower bound for $P(2, n)$ in terms of ${\\mathbb P}_{n+1}.$ This, together with L.Schl\\\"afli's famous upper bound, give us asymptotics $$P(2, n) \\thicksim 2 {2^n-1 \\choose n},\\quad n\\to \\infty.$$ Also, the validity of the long-standing conjecture concerning ${\\mathbb P}_n$ is proved: $$\\mathbb{P}_n \\thicksim n^22^{1-n}, \\quad n\\to \\infty .$$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-05T21:33:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "94C10",
      "15B52",
      "06A07",
      "55U10"
    ],
    "keywords": [
      "threshold functions",
      "asymptotics",
      "singularity",
      "bernoulli matrix",
      "supermodular function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}