RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1996 Volume 8, Issue 4, Pages 92–107 (Mi dm550)

This article is cited 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.

UDC: 519.716

Received: 23.10.1996

DOI: 10.4213/dm550


 English version:
Discrete Mathematics and Applications, 1996, 6:6, 569–583

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025