Аннотация:
Нахождение асимптотики числа пороговых является одной из важнейших проблем дискретной математики и математической кибернетики (см. А.Д.Коршунов, УМН, 2009, Т.64, В.5(389)). В 19 веке L.Schläfli в эквивалентных терминах получил (около 1850 г.) верхнюю оценку для числа пороговых функций $P(2, n)$:
$$
P(2,n)\leq 2 \sum\limits_{i=0}^n {2^n-1 \choose i}.
$$
С конца 50-х годов прошлого века вопрос о нахождении числа пороговых функций стал одним из центральных вопросов пороговой логики. В ряде статей были получены нижние оценки для P(2, n), близкие по порядку логарифма к верхней оценке L.Schläfli. Наилучшая нижняя оценка в этой серии работ была получена автором в 1993 году:
$$
P \left( 2, n \right) \geq 2^{ n^2 ( 1- \frac{7}{\ln {n}} ) }\cdot P \left( 2, \Big[ \frac{7 (n -1)}{\log_{2} (n -1)} \Big] \right) .
$$
Параллельно нахождению асимптотики числа пороговых функций велись исследования по оценке числа вырожденных $\{\pm 1\}$ (или $\{0,1\}$) $(n\times n)$-матриц.
Пусть $M_n= (a_{ij})$ случайная $(n\times n)$$\{\pm 1\}$-матрица с элементами, являющимися независимыми одинаково распределенными случайными величинами Бернулли: $\Pr(a_{ij}=1)= Pr(a_{ij}=-1)= 1/2$. В 1967 году Komlós J. доказал, что вероятность вырожденности случайной Бернуллиевой $\{0, 1\}$-матрицы с ростом размерности стремится к нулю, что верно и для $\{\pm 1\}$-матриц:
$$
P_n := Pr( \det M_n = 0) = o_n(1).
$$
В 1977 году он улучшил свой результат до верхней оценки
$$
P_n < O\left(\frac{1}{\sqrt{n}}\right).
$$
В 1995 году Kahn J., Komlós J. и Szemerédi E. добились экспоненциального убывания верхней оценки: $(0.999+o_n(1))^n$ . В 2007 году Tao T. и Vu V. получили оценку $(\frac{3}{4}+o_n(1))^n$, а в 2009 году Bourgain J., Vu V.H. и Wood P.M. улучшили ее до $(\frac{\sqrt{2}}{2}+o_n(1))^n$ В 2018 году К. Тихомировым было показано, что
$$
P_n = \left(\frac{1}{2}+o_n(1)\right)^n.
$$
В докладе будет исследовано представление числа пороговых функций в комбинаторно-топологических терминах, вытекающего из работ L.Schläfli, Zaslavsky T., Hall P. и Folkman J., и показана связь числа пороговых функций с числом вырожденных $\{\pm 1\}$-матриц, позволяющая установить следующие асимптотики.
Теорема 1. Асимптотика вероятности $P_n$ равна:
$$
P_n \sim (n-1)^2 2^{1-n},n\to \infty.
$$ Теорема 2. Асимптотика числа пороговых функций равна:
$$
P(2,n) \sim 2 {{2^n - 1}\choose n}, n\to\infty.
$$
Полное изложение результатов можно найти в arXiv:2004.03400v3
Идентификатор для Zoom 817 4069 6665 Код 391118
Обратная связь: