Geodesic
Asymptotics of the number of threshold functions and the singularity probability of random $\{\pm1\}$-matrices
Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 492 (2020), pp. 89-91.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DANMA_2020_492_a18,
     author = {A. A. Irmatov},
     title = {Asymptotics of the number of threshold functions and the singularity probability of random $\{\pm1\}$-matrices},
     journal = {Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleni\^a},
     pages = {89--91},
     publisher = {mathdoc},
     volume = {492},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DANMA_2020_492_a18/}
}
TY  - JOUR
AU  - A. A. Irmatov
TI  - Asymptotics of the number of threshold functions and the singularity probability of random $\{\pm1\}$-matrices
JO  - Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
PY  - 2020
SP  - 89
EP  - 91
VL  - 492
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DANMA_2020_492_a18/
LA  - ru
ID  - DANMA_2020_492_a18
ER  - 
%0 Journal Article
%A A. A. Irmatov
%T Asymptotics of the number of threshold functions and the singularity probability of random $\{\pm1\}$-matrices
%J Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
%D 2020
%P 89-91
%V 492
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DANMA_2020_492_a18/
%G ru
%F DANMA_2020_492_a18
A. A. Irmatov. Asymptotics of the number of threshold functions and the singularity probability of random $\{\pm1\}$-matrices. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 492 (2020), pp. 89-91. http://geodesic.mathdoc.fr/item/DANMA_2020_492_a18/

[1] Schläfli L., Gesammelte Mathematische Abhandlungen I, Verlag Birkhäuser. Springer Basel AG, 1950, 209–212 | MR

[2] Cover T.M., “Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition”, IEEE Transactions on Electronic Computers, 14:3 (1965), 326–334 | DOI | Zbl

[3] Muroga S., “Lower Bounds of the Number of Threshold Functions and a Maximum Weight”, IEEE Transactions on Electronic Computers, EC-14:2 (1965), 136–148 | DOI | Zbl

[4] Yajima S., Ibaraki T., “A Lower Bound of the Number of Threshold Functions”, IEEE Transactions on Electronic Computers, 14:6 (1965), 926–929 | DOI | Zbl

[5] Zuev Yu.A., “Asimptotika logarifma chisla porogovykh funktsii algebry logiki”, DAN, 306:3 (1989), 528–530 | Zbl

[6] Odlyzko A.M., “On Subspaces Spanned by Random Selection of $\pm1$ Vectors”, J. Combin. Theory Ser. A, 47 (1988), 124–133 | DOI | MR | Zbl

[7] Zaslavsky T., Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Mem. Amer. Math. Soc., 154, Amer. Math. Soc., Providence (RI), 1975 | MR | Zbl

[8] Irmatov A.A., “O chisle porogovykh funktsii”, Diskret. matem., 5:3 (1993), 40–43 | MR | Zbl

[9] Komlós J., “On the Determinant of (0,1) Matrices”, Studia Sci. Math. Hungar, 2 (1967), 7–21 | MR | Zbl

[10] Komlós J., “Manuscript (1977)”, Random Graphs, ed. B. Bollobás, Academic Press, N.Y.–L., 1985, 347–350

[11] Kahn J., Komlós J., Szemerédi E., “On the Probability That a Random $\pm1$-Matrix is Singular”, J. Amer. Math. Soc., 8:1 (1995), 223–240 | DOI | MR | Zbl

[12] Tao T., Vu V., “On the Singularity of Random Bernoulli Matrices”, J. Amer. Math. Soc., 20:3 (2007), 603–628 | DOI | MR | Zbl

[13] Bourgain J., Vu V.H., Wood P.M., “On the Singularity Probability of Discrete Random Matrices”, J. Functional Analysis, 258 (2010), 559–663 | DOI | MR

[14] Tikhomirov K., “Singularity of Random Bernoulli Matrices”, Annals of Math., 191:2 (2020), 593–634 | DOI | MR | Zbl

[15] Irmatov A.A., “Arrangement of Hyperplanes and the Number of Threshold Functions”, Acta Applicandae Mathematicae, 68 (2001), 211–226 | DOI | MR | Zbl