Линейная комбинаторика
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Гармонический анализ на булевом кубе. Спектральные свойства пороговых функций. Проблема параметров Чжоу (Chow). PAC-обучающий алгоритм для класса пороговых функций. Шумоустойчивость и обучаемость класса линейных пороговых функций. Теорема Переса (Peres, 2004).
Граничные точки пороговых функций. Определяющая выборка и определяющее число для гипотезы из заданного класса. Оценки для определяющего числа гипотезы из класса пороговых функций.
Частично-упорядоченное множество конфигурации гиперплоскостей. Функция Мёбиуса и характеристический полином конфигурации гиперплоскостей. Теорема о поперечном сечении (The Cross-Cut Theorem). Теорема Уитни о характеристическом полиноме конфигурации гиперплоскостей. Функция Мёбиуса геометрической решетки. Теорема Т.Заславского (1975). Алгебро-топологическое описание функции Мёбиуса конфигурации гиперплоскостей.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных ±1-матриц. Теоремы А.А.Ирматова об асимптотике числа пороговых функций, асимптотике вероятности вырожденности ±1-матриц и о подпространствах, порожденных ±1-векторами.
Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 2007
Ryan O'Donnell. Analysis of Boolean Functions. https://doi.org/10.48550/arXiv.2105.10386
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. Volume 51, Number 12 (1945), 898-902
A. M. Odlyzko. On subspaces spanned by random selections of ±1 vectors, J. Combinatorial Theory A, 47 (1988), pp. 124-133
R.P.Stanley. An Introduction to Hyperplane Arrangements, IAS/Park City Mathematics Series, Volume 14, 2004
T.Zaslavsky. Facing Up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Memoirs of the American Mathematical Society, V. 154, Amer. Math. Soc., Providence RI, 1975
А.А. Ирматов. О числе пороговых функций, Дискрет. матем., 1993, том 5, выпуск 3, страницы 40–43
А. А. Ирматов, Ж. Д. Ковиянич. Об асимптотике логарифма числа пороговых функций K-значной логики, Дискрет. матем., 1998, том 10, выпуск 3, страницы 35–56
A.A.Irmatov. Arrangements of Hyperplanes and the Number of Threshold Functions, Acta Applicandae Mathematicae, 2001, Vol.68 (1), pp.211-226
A.A.Irmatov. Singularity of {±1}-matrices and asymptotics of the number of threshold functions. 2020 https://doi.org/10.48550/arXiv.2004.03400 (v.3)
A.A.Irmatov. On linear-combinatorial problems associated with subspaces spanned by {±1}-vectors. 2024 https://doi.org/10.48550/arXiv.2405.05082
Спецкурс посвящен изучению свойств линейных объектов, возникающих в дискретной математике и математической кибернетики таких как, пороговые функции, конфигурации гиперплоскостей, случайные матрицы и других вероятностно-комбинаторными и алгебро-топологическими методами. Будут рассмотрены спектральные свойства пороговых функций; проблема параметров Чжоу; РАС-обучающие алгоритмы для класса пороговых функций. Предполагается изложить последние достижения в оценке числа пороговых функций и числа вырожденных ±1-матриц, полученные рядом авторов, за последние 80 лет, в том числе теоремы об асимптотике числа пороговых функций и асимптотике вероятности вырожденности ±1-матриц.