Линейная комбинаторика
Название спецкурса на английском языке
Linear combinatorics
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Применение методов линейной алгебры в комбинаторике.
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Гармонический анализ на булевом кубе. Спектральные свойства пороговых функций. Проблема параметров Чжоу (Chow). PAC-обучающий алгоритм для класса пороговых функций. Шумоустойчивость и обучаемость класса линейных пороговых функций. Теорема Переса (Peres, 2004).
Граничные точки пороговых функций. Определяющая выборка и определяющее число для гипотезы из заданного класса. Оценки для определяющего числа гипотезы из класса пороговых функций.
Частично-упорядоченное множество конфигурации гиперплоскостей. Функция Мёбиуса и характеристический полином конфигурации гиперплоскостей. Теорема о поперечном сечении (The Cross-Cut Theorem). Теорема Уитни о характеристическом полиноме конфигурации гиперплоскостей. Функция Мёбиуса геометрической решетки. Теорема Т.Заславского (1975). Алгебро-топологическое описание функции Мёбиуса конфигурации гиперплоскостей.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных ±1-матриц. Теоремы А.А.Ирматова об асимптотике числа пороговых функций, асимптотике вероятности вырожденности ±1-матриц и о подпространствах, порожденных ±1-векторами.
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Гармонический анализ на булевом кубе. Спектральные свойства пороговых функций. Проблема параметров Чжоу (Chow). PAC-обучающий алгоритм для класса пороговых функций. Шумоустойчивость и обучаемость класса линейных пороговых функций. Теорема Переса (Peres, 2004).
Граничные точки пороговых функций. Определяющая выборка и определяющее число для гипотезы из заданного класса. Оценки для определяющего числа гипотезы из класса пороговых функций.
Частично-упорядоченное множество конфигурации гиперплоскостей. Функция Мёбиуса и характеристический полином конфигурации гиперплоскостей. Теорема о поперечном сечении (The Cross-Cut Theorem). Теорема Уитни о характеристическом полиноме конфигурации гиперплоскостей. Функция Мёбиуса геометрической решетки. Теорема Т.Заславского (1975). Алгебро-топологическое описание функции Мёбиуса конфигурации гиперплоскостей.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных ±1-матриц. Теоремы А.А.Ирматова об асимптотике числа пороговых функций, асимптотике вероятности вырожденности ±1-матриц и о подпространствах, порожденных ±1-векторами.
Список источников
L.Babai, P.Frankl. Linear Algebra Methods in Combinatorics. Version 2.1. 2020
Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 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
Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 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-матриц.
День недели
вторник
Время
18:30-20:05
Аудитория
1225
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.