|
This article is cited in 7 scientific papers (total in 7 papers)
Estimates for the number of threshold functions
A. A. Irmatov
Abstract:
We obtain a lower bound and refine Schläfli's
upper bound for the number of threshold functions. As a consequence
it is shown that the assertion that the number of threshold
functions is asymptotically equal to
$$
2\sum_{i=0}^n{2^n-1\choose i}
$$
is equivalent to the assertion that the portion of the collections consisting
of $n-1$ different $(1,-1)$-vectors $v_1,\ldots,v_{n-1}$ of length $n$ such
that $\newspan(v_1,\ldots,v_{n-1})\cap \{1,-1\}^n$ coincides with the set of all
vectors of the form $(\pm v_1,\ldots,\pm v_{n-1})$
tends to 1 as $n \to \infty$. The work was supported by the Russian Foundation for Basic Research,
grant 95-01-00369.
Received: 23.10.1996
Citation:
A. A. Irmatov, “Estimates for the number of threshold functions”, Diskr. Mat., 8:4 (1996), 92–107; Discrete Math. Appl., 6:6 (1996), 569–583
Linking options:
https://www.mathnet.ru/eng/dm550https://doi.org/10.4213/dm550 https://www.mathnet.ru/eng/dm/v8/i4/p92
|
Statistics & downloads: |
Abstract page: | 467 | Full-text PDF : | 219 | First page: | 1 |
|