RUS  ENG
Full version
JOURNALS // Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia // Archive

Dokl. RAN. Math. Inf. Proc. Upr., 2020 Volume 492, Pages 89–91 (Mi danma79)

This article is cited in 3 papers

INFORMATICS

Asymptotics of the number of threshold functions and the singularity probability of random $\{\pm1\}$-matrices

A. A. Irmatov

Lomonosov Moscow State University, Moscow, Russian Federation

Abstract: Two results concerning the number $P(2,n)$ of threshold functions and the singularity probability $\mathbb{P}_n$ of random $(n\times n)$ $\{\pm1\}$-matrices are established. The following asymptotics are obtained:
$$ P(2,n)\sim2\binom{2^n-1}{n}\text{ and }\mathbb{P}_n\sim n^2\cdot2^{1-n}\quad n\to\infty. $$


Keywords: threshold function, Bernoulli matrices, Möbius function, supermodular function, combinatorial flag.

UDC: 519.1, 519.7

Presented: A. T. Fomenko
Received: 04.03.2020
Revised: 04.03.2020
Accepted: 19.03.2020

DOI: 10.31857/S2686954320030091


 English version:
Doklady Mathematics, 2020, 101:3, 247–249

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025