{
  "id": "1811.10087",
  "version": "v1",
  "published": "2018-11-25T20:39:38.000Z",
  "updated": "2018-11-25T20:39:38.000Z",
  "title": "A Lower Bound of the Number of Threshold Functions in Terms of Combinatorial Flags on the Boolean Cube",
  "authors": [
    "Anwar Irmatov"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "abstract": "Let $ E=\\{ (1, b_1, \\ldots , b_n)\\in R^{n+1} \\mid \\; b_i= \\pm 1 ,\\; i=1, \\ldots, n \\}$, $E^{\\times n}_{\\ne 0} := \\{ W=(w_{i_1}, \\ldots , w_{i_n}) \\mid w_{i_k}\\in E, \\, k=1, \\ldots, n, \\, dim \\, span(w_{i_1}, \\ldots , w_{i_n}) = n \\},$ and $q^W_l := |span(w_{i_{n-l+1}}, \\ldots , w_{i_n}) \\cap E|.$ Then for any weights $p=(p_1, \\ldots, p_{2^n})$, $p_i\\in R$, $\\sum_{i=1}^{2^n}{p_i} =1$ we have for the number of threshold functions $P(2,n)$ the following lower bound $$P(2, n) \\geq 2\\sum_{W\\in E^{\\times n}_{\\ne 0}}{\\frac{1- p_{i_1} -p_{i_2} - \\cdots - p_{i_{q_n^W}}}{q_n^W\\cdot q_{n-1}^W\\cdots q_1^W}},$$ and the right side of the inequality doesn't depend on the choice of $p$. Here the indices used in the numerator correspond to vectors from $span(w_{i_1}, \\ldots , w_{i_n})\\cap E = \\left\\{w_{i_1}, \\ldots, w_{i_n}, \\ldots w_{i_{q_n^W}}\\right\\}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-11-25T20:39:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "threshold functions",
      "lower bound",
      "boolean cube",
      "combinatorial flags",
      "right side"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}